Minimizing weighted earliness and tardiness penalties in single-machine scheduling with idle time permitted

Abstract

In this paper, a single-machine scheduling problem with weighted earliness and tardiness penalties is considered. Idle time between two adjacent jobs is permitted and due dates of jobs could be unequal. The dominance rules are utilized to develop a relationship matrix, which allows a branch-and-bound algorithm to eliminate a high percentage of infeasible solutions. After combining this matrix with a branching strategy, a procedure to solve the problem is proposed. (C) 2002 Wiley Periodicals, Inc.