TY - JOUR
T1 - Scheduling unrelated parallel machines in semiconductor manufacturing by problem reduction and local search heuristics
AU - Wang, I. Lin
AU - Wang, Yi Chi
AU - Chen, Chih Wei
N1 - Funding Information:
Acknowledgments I-Lin Wang was partially supported by the National Science Council of Taiwan under Grant:NSC 100-2410-H-006-006-MY2. Yi-Chi Wang was partially supported by the National Science Council of Taiwan under Grant:NSC 100-2221-E-035-076-MY3.
Funding Information:
Yi-Chi Wang is an Associate Professor in the Department of Industrial Engineering and Systems Management at Feng Chia University. He received his B.S. in Mechanical Engineering from Tatung Institute of Technology, Taiwan, 1993, M.S. in Manufacturing Engineering from Syracuse University, New York, and his Ph.D. degree in Industrial Engineering from Mississippi State University in 2003. His major research interests are in areas of agent-based manufacturing systems, joint replenishment problems, supply chain system simulation, and metal cutting optimization. He has conducted several research projects funded by National Science Council of Taiwan and has published over 40 articles in refereed journals and conference proceedings. Dr. Wang was the co-founder of the Society of Lean Enterprise Systems of Taiwan (SLEST). He currently serves as the secretary of SLEST. In 2011, he co-chaired the 21st International Conference on Flexible Automation and Intelligent Manufacturing, hosted in Taiwan. He is a member of SME, IIE, and CIIE.
PY - 2013/9
Y1 - 2013/9
N2 - We investigate a difficult scheduling problem in a semiconductor manufacturing process that seeks to minimize the number of tardy jobs and makespan with sequence-dependent setup time, release time, due dates and tool constraints. We propose a mixed integer programming (MIP) formulation which treats tardy jobs as soft constraints so that our objective seeks the minimum weighted sum of makespan and heavily penalized tardy jobs. Although our polynomial-sized MIP formulation can correctly model this scheduling problem, it is so difficult that even a feasible solution can not be calculated efficiently for small-scale problems. We then propose a technique to estimate the upper bound for the number of jobs processed by a machine, and use it to effectively reduce the size of the MIP formulation. In order to handle real-world large-scale scheduling problems, we propose an efficient dispatching rule that assigns a job of the earliest due date to a machine with least recipe changeover (EDDLC) and try to re-optimize the solution by local search heuristics which involves interchange, translocation and transposition between assigned jobs. Our computational experiments indicate that EDDLC and our proposed reoptimization techniques are very efficient and effective. In particular, our method usually gives solutions very close to the exact optimum for smaller scheduling problems, and calculates good solutions for scheduling up to 200 jobs on 40 machines within 10 min.
AB - We investigate a difficult scheduling problem in a semiconductor manufacturing process that seeks to minimize the number of tardy jobs and makespan with sequence-dependent setup time, release time, due dates and tool constraints. We propose a mixed integer programming (MIP) formulation which treats tardy jobs as soft constraints so that our objective seeks the minimum weighted sum of makespan and heavily penalized tardy jobs. Although our polynomial-sized MIP formulation can correctly model this scheduling problem, it is so difficult that even a feasible solution can not be calculated efficiently for small-scale problems. We then propose a technique to estimate the upper bound for the number of jobs processed by a machine, and use it to effectively reduce the size of the MIP formulation. In order to handle real-world large-scale scheduling problems, we propose an efficient dispatching rule that assigns a job of the earliest due date to a machine with least recipe changeover (EDDLC) and try to re-optimize the solution by local search heuristics which involves interchange, translocation and transposition between assigned jobs. Our computational experiments indicate that EDDLC and our proposed reoptimization techniques are very efficient and effective. In particular, our method usually gives solutions very close to the exact optimum for smaller scheduling problems, and calculates good solutions for scheduling up to 200 jobs on 40 machines within 10 min.
UR - http://www.scopus.com/inward/record.url?scp=84879008848&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84879008848&partnerID=8YFLogxK
U2 - 10.1007/s10696-012-9150-7
DO - 10.1007/s10696-012-9150-7
M3 - Article
AN - SCOPUS:84879008848
SN - 1936-6582
VL - 25
SP - 343
EP - 366
JO - Flexible Services and Manufacturing Journal
JF - Flexible Services and Manufacturing Journal
IS - 3
ER -