Unrelated parallel machine scheduling with setup times subject to job release and expired times

• Main Author: Chen, Changyu
• Other Authors: Wu Kan
• Format: Thesis-Master by Coursework
• Language: English
• Published: Nanyang Technological University 2020
• Subjects: Engineering::Industrial engineering::Operations research; Engineering::Manufacturing
• Online Access: https://hdl.handle.net/10356/142943
• Institution: Nanyang Technological University

This research is motivated by a scheduling problem arising in the ion implantation process of wafer fabrication. The author models the scheduling problem as the problem of scheduling unrelated parallel machines with sequence-dependent setup times subject to job release time and expired time of allowing a job processed on a certain machine, defined as: R|{r_j,e_{ij},ST}_{sd}|C_{max}. The objective is firstly maximizing the number of processed jobs, then minimizing the maximum completion time (makespan), and finally minimizing the maximum completion times of the non-bottleneck machines. The author proposes a mixed integer programming (MIP) model and an adapted hybrid tabu search (TS) algorithm to acquire approximate feasible solutions. The MIP model has two phases and attempts to achieve the first two objectives. The hybrid TS algorithm has three phases and attempts to achieve all the three objectives. Computational results in a set of real instances demonstrate that the maximum number of processed jobs can be acquired within a short time (average 8 seconds). By comparison of the two approaches, the TS outperforms the MIP model with regard to solution quality and computational time for the second objective, minimizing the makespan. Furthermore, the third phase of the hybrid TS algorithm shows the effectiveness to further enhance the utilization of the equipment in ion implantation.