In this paper, we study the multi-machine scheduling problem with earliness and tardiness penalties and sequence dependent setup times. This problem can be decomposed into two subproblems—sequencing and timetabling. Sequencing focuses on assigning each job to a ﬁxed machine and determine the job sequence on each machine. We call such assignment a semi-schedule. Timetabling focuses on ﬁnding an executable schedule from the semi-schedule via idle-time insertion. Sequencing is strongly NP-hard in general. Although timetabling is polynomial-time solvable, it can become a computational bottleneck if the procedure is executed many times within a larger framework. This paper makes two contributions. We ﬁrst propose a quantum improvement to the computational efﬁciency of the timetabling algorithm. We then apply it within a squeaky wheel optimization framework to solve the sequencing and overall problem. Finally, we demonstrate the strength of our proposed algorithms by experiments.
Earliness-tardiness, Meta-heuristics, Scheduling, Squeaky wheel
Artificial Intelligence and Robotics | Computer Sciences | Operations Research, Systems Engineering and Industrial Engineering
Intelligent Systems and Decision Analytics
Annals of Operations Research
FENG, Guang and LAU, Hoong Chuin.
Efficient algorithms for machine scheduling problems with earliness and tardiness penalties. (2007). Annals of Operations Research. 159, (1), 83-95. Research Collection School Of Information Systems.
Available at: http://ink.library.smu.edu.sg/sis_research/1195
Copyright Owner and License
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.