A branch-and-bound algorithm for minimizing the sum of maximum earliness and tardiness with unequal release times
- 21 May 2009
- journal article
- research article
- Published by Taylor & Francis in Engineering Optimization
- Vol. 41 (6) , 521-536
Abstract
This article addresses the problem of minimizing the sum of maximum earliness and tardiness on a single machine with unequal release times. It is proven that this problem is NP-hard in the strong sense and a branch-and-bound algorithm is developed as an exact method. In the proposed algorithm, modified dispatching rules based on different release times are proposed as the upper bound, while a procedure considering preemption assumption is used to obtain a good lower bound. Also, dominance rules based on no unforced idle time, adjacent pairwise interchanges in the base problem, and job blocks are used to fathom the nodes. In order to evaluate the efficiency of the proposed algorithm, 4,860 instances were randomly generated, varying from 7 to 1,000 jobs. It is shown that the branch-and-bound algorithm was capable of optimally solving 94.1% of the instances, showing its efficiency in solving all problem sizes.Keywords
This publication has 25 references indexed in Scilit:
- A survey of the state-of-the-art of common due date assignment and scheduling researchEuropean Journal of Operational Research, 2002
- A composite heuristic for the single machine early/tardy job scheduling problemComputers & Operations Research, 1998
- Bicriteria scheduling problem involving total tardiness and total earliness penaltiesInternational Journal of Production Economics, 1991
- Sequencing with Earliness and Tardiness Penalties: A ReviewOperations Research, 1990
- Dynamic Programming State-Space Relaxation for Single-Machine SchedulingJournal of the Operational Research Society, 1988
- The one-machine sequencing problemEuropean Journal of Operational Research, 1982
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey1979
- Complexity of Machine Scheduling Problems1977
- Sequencing with due‐dates and early start times to minimize maximum tardinessNaval Research Logistics Quarterly, 1974
- A Dynamic Programming Approach to Sequencing ProblemsJournal of the Society for Industrial and Applied Mathematics, 1962