In this paper, we study an earliness–tardiness scheduling problem for a single machine that is motivated by process conditions found in semiconductor wafer fabrication facilities (wafer fabs). In modern 300-mm wafer fabs, front opening unified pods (FOUPs) transfer wafers. The number of FOUPs is limited to avoid a congestion of the Automated Material Handling System. Several orders can be grouped in one FOUP. A nonrestrictive common due date for all the orders is assumed. Only orders that belong to the same family can be processed together in a single FOUP at the same time. We present a Mixed Integer Linear Programming (MILP) formulation for this problem. Moreover, we show that this scheduling problem is NP-hard. We propose several simple heuristics based on dispatching rules and assignment strategies from bin packing. Moreover, genetic algorithms are designed that assign the orders to the set of early and tardy orders, respectively. In addition, a random key genetic algorithm (RKGA) is described that proposes order sequences. The different algorithms are hybridized with job formation and sequencing heuristics. A more specialized algorithm that is based on the generalized assignment problem is presented for the special case of a single order family. Results of computational experiments based on randomly generated problem instances are presented. They demonstrate that the genetic algorithms perform well with respect to solution quality and computing time under a broad range of experimental conditions.
Mots clés : Scheduling, multiple orders per job, common due date, semiconductor manufacturing
@article{RO_2018__52_4-5_1329_0,
author = {Rocholl, Jens and M\"onch, Lars},
title = {Hybrid algorithms for the earliness{\textendash}tardiness single-machine multiple orders per job scheduling problem with a common due date},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {1329--1350},
publisher = {EDP-Sciences},
volume = {52},
number = {4-5},
year = {2018},
doi = {10.1051/ro/2018029},
mrnumber = {3884164},
zbl = {1411.90084},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ro/2018029/}
}
TY - JOUR AU - Rocholl, Jens AU - Mönch, Lars TI - Hybrid algorithms for the earliness–tardiness single-machine multiple orders per job scheduling problem with a common due date JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2018 SP - 1329 EP - 1350 VL - 52 IS - 4-5 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro/2018029/ DO - 10.1051/ro/2018029 LA - en ID - RO_2018__52_4-5_1329_0 ER -
%0 Journal Article %A Rocholl, Jens %A Mönch, Lars %T Hybrid algorithms for the earliness–tardiness single-machine multiple orders per job scheduling problem with a common due date %J RAIRO - Operations Research - Recherche Opérationnelle %D 2018 %P 1329-1350 %V 52 %N 4-5 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ro/2018029/ %R 10.1051/ro/2018029 %G en %F RO_2018__52_4-5_1329_0
Rocholl, Jens; Mönch, Lars. Hybrid algorithms for the earliness–tardiness single-machine multiple orders per job scheduling problem with a common due date. RAIRO - Operations Research - Recherche Opérationnelle, Tome 52 (2018) no. 4-5, pp. 1329-1350. doi : 10.1051/ro/2018029. http://www.numdam.org/articles/10.1051/ro/2018029/
[1] and , A survey of automated material handling systems in 300-mm semiconductor fabs. IEEE Trans. Semicond. Manuf. 19 (2006) 112–120. | DOI
[2] , Genetic algorithm and random keys for sequencing and optimization. ORSA J. Comput. 6 (1994) 154–160. | DOI | Zbl
[3] , , , , , , and , Modeling and analysis of semiconductor manufacturing in a shrinking world: challenges and successes. Eur. J. Ind. Eng. 5 (2011) 254–271. | DOI
[4] and , Multiple orders per job compatible batch scheduling. IEEE Trans. Electron. Packag. Manuf. 29 (2006) 285–296. | DOI
[5] and , Multiple orders per job batch scheduling with incompatible jobs. Ann. Oper. Res. 159 (2008) 245–260. | DOI | MR | Zbl
[6] and , Wafer logistics and automated material handling systems, in Handbook of Semiconductor Manufacturing Technology. Marcel Dekker Inc. (2000) 1067–1102.
[7] and , Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979). | MR | Zbl
[8] , Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, Reading (1989). | Zbl
[9] and , Biased random-key genetic algorithms for combinatorial optimization. J. Heuristics 17 (2011) 487–525. | DOI
[10] , and , A survey of the state-of-the-art of common due date assignment and scheduling research. Eur. J. Oper. Res. 139 (2002) 1–25. | DOI | MR | Zbl
[11] , , and
[12] and , Earliness-tardiness scheduling problems I: weighted deviation of completion times about a common due date.Oper. Res. 39 (1991) 836–846. | DOI | MR | Zbl
[13] and Column generation heuristics for multiple machine, multiple orders per job scheduling problems. Ann. Oper. Res. 159 (2008) 261–273. | DOI | MR | Zbl
[14] , , and , Integrated heuristics for scheduling multiple order jobs in a complex job shop. Int. J. Metaheuristics 1 (2010) 158–180. | DOI | MR | Zbl
[15] and , Semiconductor manufacturing scheduling of jobs containing multiple orders on identical parallel machines. Int. J. Prod. Res. 47 (2009) 2565–2585. | DOI | Zbl
[16] , Minimizing the average deviation of job completion times about a common due date. Nav. Res. Logist. 28 (1981) 643–651. | DOI | Zbl
[17] , and , Minimzing makespan with multiple-orders-per-job in a two-machine flowshop. Eur. J. Oper. Res. 182 (2007) 63–79. | DOI | MR | Zbl
[18] , , and , Earliness–tardiness minimization on scheduling a batch processing machine with non-identical job sizes. Comput. Ind. Eng. 87 (2015) 590–599. | DOI
[19] and , Knapsack Problems: Algorithms and Computer Implementations. Wiley & Sons, Chichester (1990). | MR | Zbl
[20] and , Scheduling multiple orders per job in a single machine to minimize total completion time. Eur. J. Oper. Res. 207 (2010) 70–77. | DOI | MR | Zbl
[21] , , and , The Single Machine Multiple Orders per Job Scheduling Problem. Technical Report, ASUIE-ORPS-2004-04, Arizona State University, Tempe (2004).
[22] , Genetic Algorithms + Data Structures = Evolution Programs, 3rd edition. Springer, Berlin (1996). | DOI | Zbl
[23] and , Decomposition heuristics for minimizing earliness-tardiness on parallel burn-in ovens with a common due date. Comput. Oper. Res. 34 (2007) 3380–3396. | DOI | Zbl
[24] , and , Minimizing earliness and tardiness on a single burn-in oven with a common due date and a maximum available tardiness constraint. OR Spectr. 28 (2006) 177–198. | DOI | MR | Zbl
[25] , , , and , A survey of problems, solution techniques, and future challenges in scheduling semiconductor manufacturing operations. J. Sched. 14 (2011) 583–595. | DOI | MR
[26] , , and , Multiple orders per job formation and release strategies in large scale wafer fabs: a simulation study. J. Simul. 5 (2011) 25–43. | DOI
[27] , and , Production Planning and Control for Wafer Fabrication Facilities: Modeling, Analysis, and Systems. Springer, New York (2013). | DOI
[28] , and A survey of semiconductor supply chain models part I: semiconductor supply chains, strategic network design, and supply chain simulation. To appear in: Int. J. Prod. Res. Doi: (2017). | DOI
[29] , A literature survey on the design approaches and operational issues of automated wafer-transport systems for wafer fabs. Prod. Plan. Control 17 (2006) 648–663. | DOI
[30] , and , Exact and heuristic algorithms for the just-in-time scheduling problem in a batch processing system. Comput. Oper. Res. 80 (2017) 173–183. | DOI | MR | Zbl
[31] , Scheduling: Theory, Algorithms, and Systems, 5th edition. Springer, New York (2016). | DOI | MR
[32] and , Metaheuristic scheduling of 300-mm lots containing multiple orders. IEEE Trans. Semicond. Manuf. 18 (2005) 633–643. | DOI
[33] and , Modelling the dynamics of a steady state genetic, in Vol. 5 of Foundations of Genetic Algorithms, edited by and . Springer (1999) 57–68.
[34] , and , A single-machine, single-wafer-processing, multiple-lots-per-carrier scheduling problem to minimize the sum of lot completion times. Comput. Oper. Res. 39 (2012) 1411–1418. | DOI | MR | Zbl
[35] , and , Minimising makespan for a two-machine, flow shop, single-wafer-processing, multiple-jobs-per-carrier scheduling problem. Int. J. Plan. Sched. 1 (2012) 171–208.
[36] and , Genetic algorithms to solve a single machine multiple orders per job scheduling problem, in Proc. of the 2010 Winter Simulation Conference (2010) 2493–2503. | DOI
[37] and , Grouping genetic algorithms for solving single machine multiple orders per job scheduling problems. Ann. Oper. Res. 235 (2015) 709–739. | DOI | MR | Zbl
[38] , A study of reproduction in generational and steady-state genetic algorithms, in Vol. 1 of Foundations of Genetic Algorithms, edited by . Morgan Kaufmann Publishers (1991) 94–101. | MR
[39] , and , A hybrid scheduling approach for a two-stage flexible flow shop with batch processing machines. J. Sched. 21 (2018) 209–226. | DOI | MR | Zbl
[40] and , Forming and scheduling jobs with capacitated containers in semiconductor manufacturing: single machine problem. Ann. Oper. Res. 159 (2008) 5–24. | DOI | MR | Zbl
[41] , Galib: A C++ Library of Genetic Algorithms Components. Available at Website: http://lancet.mit.edu/ga/ (2017).
[42] , Individual comparisons by ranking methods. Biometrics 1 (1945) 80–83. | DOI
Cité par Sources :
