Publication Type
Journal Article
Version
acceptedVersion
Publication Date
3-2022
Abstract
This research is motivated by a scheduling problem arising in the ion implantation process of wafer fabrication. The ion implementation scheduling problem is modeled as an unrelated parallel machine scheduling (UPMS) problem with sequence-dependent setup times that are subject to job release time and expiration time of allowing a job to be processed on a specific machine, defined as: R|rj,eij,STsd|Cmax. The objective is first to maximize the number of processed jobs, then minimize the maximum completion time (makespan), and finally minimize the maximum completion times of the non-bottleneck machines. A mixed-integer programming (MIP) model is proposed as a solution approach and adopts a 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 three objectives. In a real setting, computational results demonstrate that the maximum number of processed jobs can be acquired within a short time utilizing the hybrid TS algorithm (average 8 s). By comparing the two approaches, the TS outperforms the MIP model regarding solution quality and computational time for the second objective, minimizing the makespan. Furthermore, the third phase of the hybrid TS algorithm shows the effectiveness further to enhance the utilization of the ion implantation equipment.
Keywords
Scheduling, Unrelated parallel machines, Setup times, Expired times, Job release, Wafer fabrication, Mixed integer programming, Tabu search
Discipline
Operations Research, Systems Engineering and Industrial Engineering | Theory and Algorithms
Publication
Computers and Industrial Engineering
Volume
165
First Page
1
Last Page
11
ISSN
0360-8352
Identifier
10.1016/j.cie.2021.107915
Publisher
Elsevier
Citation
CHEN, Changyu; FATHI, Madhi; KHAKIFIROOZ, Marzieh; and WU, Kan.
Hybrid tabu search algorithm for unrelated parallel machine scheduling in semiconductor fabs with setup times, job release, and expired times. (2022). Computers and Industrial Engineering. 165, 1-11.
Available at: https://ink.library.smu.edu.sg/sis_research/6956
Copyright Owner and License
Authors
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
https://doi.org/10.1016/j.cie.2021.107915
Included in
Operations Research, Systems Engineering and Industrial Engineering Commons, Theory and Algorithms Commons