Hybrid tabu search algorithm for unrelated parallel machine scheduling in semiconductor fabs with setup times, job release, and expired times

Changyu Chen, Mahdi Fathi, Marzieh Khakifirooz, Kan Wu*

*Corresponding author for this work

Research output: Contribution to journalJournal Article peer-review

15 Scopus citations

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.

Original languageEnglish
Article number107915
JournalComputers and Industrial Engineering
Volume165
DOIs
StatePublished - 03 2022

Bibliographical note

Publisher Copyright:
© 2022 Elsevier Ltd

Keywords

  • Expired times
  • Job release
  • Mixed integer programming
  • Scheduling
  • Setup times
  • Tabu search
  • Unrelated parallel machines
  • Wafer fabrication

Fingerprint

Dive into the research topics of 'Hybrid tabu search algorithm for unrelated parallel machine scheduling in semiconductor fabs with setup times, job release, and expired times'. Together they form a unique fingerprint.

Cite this