Algorithms for common due-date assignment and sequencing on a single machine with sequence-dependent setup times

Abstract

This paper focuses on the single machine sequencing and common due-date assignment problem for the objective of minimizing the sum of the penalties associated with earliness, tardiness and due-date assignment. Unlike the previous research articles on this class of scheduling problem, we consider sequence-dependent setup times that make the problem much more difficult. To solve the problem, a branch and bound algorithm, which incorporates the method to obtain lower and upper bounds as well as a dominance property to reduce the search space, is suggested that gives the optimal solutions for small-sized instances. Heuristic algorithms are suggested to obtain solutions for large-sized problems within a reasonable computation time. The performances of both the optimal and heuristic algorithms, in computational experiments on randomly generated test instances, are reported.

Keywords:

• sequencing
• common due-date assignment
• sequence-dependent setup time

Acknowledgements

This work was supported by the Korea Research Foundation Grant funded by the Korean Government (MOEHRD, Basic Research Promotion Fund) (KRF-2007-331-D00547).