Single machine scheduling with sequence-dependent family setups to minimize maximum lateness

Abstract

Motivated by a real-life scheduling problem in a steel wire factory in China, this paper considers the single machine scheduling problem with sequence-dependent family setup times to minimize maximum lateness. In view of the NP-hard nature of the problem, structural (dominance and neighbourhood) properties of the problem are described and used in the tabu search algorithms to find optimal or near-optimal schedules. These proposed structural properties quickly exclude unpromising and/or non-improving neighbours from further search. Empirical results on the randomly generated and real-life problem instances from a factory in China show that the proposed heuristic algorithms utilizing the structural properties can obtain optimal or near optimal solutions with a reasonable computational effort.

Keywords:

• single machine
• sequence-dependent family setup times
• maximum lateness or tardiness
• structural properties
• tabu search
• empirical results

Acknowledgements

This work is partially supported by 973 Program of China under 2002CB312205, National Science Foundation of China under 60574077 and 60874071, 863 Program of China under 2007AA04Z102. Constructive comments on an earlier version of the paper from anonymous reviewers helped improve the presentation of this paper.