Efficient algorithms for machine scheduling problems with earliness and tardiness penalties

• Main Authors: FENG, Guang, LAU, Hoong Chuin
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2007
• Subjects: Earliness-tardiness; Meta-heuristics; Scheduling; Squeaky wheel; Artificial Intelligence and Robotics; Computer Sciences; Operations Research, Systems Engineering and Industrial Engineering
• Online Access: https://ink.library.smu.edu.sg/sis_research/1195; https://ink.library.smu.edu.sg/context/sis_research/article/2194/viewcontent/AOR08_EarlinessTardiness.pdf
• Institution: Singapore Management University

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 fixed machine and determine the job sequence on each machine. We call such assignment a semi-schedule. Timetabling focuses on finding 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 first propose a quantum improvement to the computational efficiency 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.