Scheduling unrelated parallel machines in semiconductor manufacturing by problem reduction and local search heuristics
详细信息 查看全文
- 作者：I-Lin Wang (1)
Yi-Chi Wang (2)
Chih-Wei Chen (1) - 关键词：Scheduling ; Mixed integer programming ; Dispatching rule ; Local search
- 刊名：Flexible Services and Manufacturing Journal
- 出版年：2013
- 出版时间：September 2013
- 年：2013
- 卷：25
- 期：3
- 页码：343-366
- 全文大小：466KB
- 参考文献：1. Altendorfer K, Kabelka B, St?her W (2007) A new dispatching rule for optimizing machine utilization at a semiconductor test field. In: Advance semiconductor manufacturing conference IEEE/SEMI, pp 188-93
2. Arzi Y, Raviv D (1998) Dispatching in a workstation belonging to a re-entrant production line under sequence-dependent set-up times. Prod Plan Control 9:690-99 CrossRef
3. Balakrishnan N, Kanet JJ, Sridharan SV (1999) Early/Tardy scheduling with sequence dependent setups on uniform parallel machines. Comput Oper Res 26:127-41 CrossRef
4. Bank J, Werner F (2001) Heuristic algorithms for unrelated parallel-machine scheduling with a common due date, release dates, and linear earliness and tardiness penalties. Math Comput Model 33:363-83 CrossRef
5. Bilge ü, K?rac F, Kurtulan M, Pekgün P (2004) A Tabu search algorithm for parallel machine total tardiness problem. Comput Oper Res 31:397-14 CrossRef
6. Bixby R, Burda R, Miller D (2006) Short-interval detailed production scheduling in 300?mm semiconductor manufacturing using mixed integer and constraint programming. In: Advance semiconductor manufacturing conference IEEE/SEMI, pp 148-54
7. Blackstone JH, Phillips DT, Hogg GL (1982) A state-of-the-art survey of dispatching rules for manufacturing job shop operations. Int J Prod Res 20:27-5 CrossRef
8. Dabbas R, Fowler JW (2003) A new scheduling approach using combined dispatching criteria in wafer fabs. IEEE Trans Semicond Manuf 16(3):501-10
9. Haupt R (1999) A survey of priority rule-based scheduling. OR Spectr 11:3-6
10. Hochbaum DS, Landy D (1997) Scheduling semiconductor burn-in operations to minimize total flowtime. Oper Res 45:874-85 CrossRef
11. Jula P, Leachman RC (2010) Coordinated multistage scheduling of parallel batch-processing machines under multiresource constraints. Oper Res 58:933-47 CrossRef
12. Kim CO, Shin HJ (2003) Scheduling jobs on parallel machines: a restricted Tabu search approach. Int J Adv Manuf Technol 22:278-87 CrossRef
13. Kim YD, Lee DH, Kim JU (1998) A simulation study on lot release control, mask scheduling, and batch scheduling in semiconductor wafer fabrication facilities. J Manuf Syst 17:107-17 CrossRef
14. Kim SS, Shin HJ, Eom DH, Kim CO (2003) A due date density-based categorising heuristic for parallel machines scheduling. Int J Adv Manuf Technol 22:753-60 CrossRef
15. Kurz ME, Askin RG (2001) Heuristic scheduling of parallel machines with sequence-dependent set-up times. Int J Prod Res 39:3747-769 CrossRef
16. Lee YH, Bhaskaran K, Pinedo M (1997) A heuristic to minimize the total weighted tardiness with sequence dependent setups. IIE Trans 29:45-2 CrossRef
17. Lee YH, Park JK, Kim SY (2002) Experimental study on input and bottleneck scheduling for a semiconductor fabrication line. IIE Trans 34:179-90
18. Logendran R, McDonell B, Smucker B (2007) Scheduling unrelated parallel machines with sequence-dependent setups. Comput Oper Res 34:3420-438 CrossRef
19. Ovacik IM, Uzsoy R (1995) Rolling horizon procedures for dynamic parallel machine scheduling with sequence-dependent setup times. Int J Prod Res 33:3173-192 CrossRef
20. Pinedo M (1995) Scheduling theory algorithm and systems. Prentice Hall Englewood Cliffs, New Jersey
21. Schutten JMJ (1996) List scheduling revisited. Oper Res Lett 18:167-70 CrossRef
22. Sivrikaya-Serifoglu F, Ulusoy G (1999) Parallel machine scheduling with earliness and tardiness penalties. Comput Oper Res 26:773-87 CrossRef
23. Wang C, Ghenniwa H, Shen W (2005) Heuristic scheduling algorithm for flexible manufacturing systems with partially overlapping machine capabilities. Mechatron Autom IEEE Int Conf 3:1139-144
24. Zhu X, Wilhelm WE (2006) Scheduling and lot sizing with sequence-dependent setup: a literature review. IIE Trans 38:987-007 CrossRef - 作者单位：I-Lin Wang (1)
Yi-Chi Wang (2)
Chih-Wei Chen (1)
1. Department of Industrial and Information Management, National Cheng Kung University, No. 1 University Rd, Tainan, 701, Taiwan
2. Department of Industrial Engineering and Systems Management, Feng Chia University, No. 100, Wenhwa Rd., Taichung, 40724, Taiwan - ISSN：1936-6590
文摘
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.