Abstract
This research was motivated by a scheduling problem in the dry strip operations of a semiconductor wafer fabrication facility. The machines were modeled as parallel batch processing machines with incompatible job families and dynamic job arrivals, and constraints on the sequence-dependent setup time and the qual-run requirements of advanced process control. The optimization had multiple objectives, the total weighted tardiness (TWT) and makespan, to consider simultaneously. Since the problem is NP-hard, we used an Ant Colony Optimization (ACO) algorithm to achieve a satisfactory solution in a reasonable computation time. A variety of simulation experiments were run to choose ACO parameter values and to demonstrate the performance of the proposed method. The simulation results showed that the proposed ACO algorithm is superior to the common Apparent Tardiness Cost-Batched Apparent Tardiness Cost rule for minimizing the TWT and makespan. The arrival time distribution and the number of jobs strongly affected the ACO algorithm’s performance.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Mathirajan M, Sivakumar AI (2006) A literature review, classification and simple meta-analysis on scheduling of batch processors in semiconductor. Int J Adv Manuf Technol 29(9–10):990–1001. doi:10.1007/s00170-005-2585-1
Chien C-F, Chen C-H (2007) A novel timetabling algorithm for a furnace process for semiconductor fabrication with constrained waiting and frequency-based setups. OR-Spectrum 29:391–419. doi:10.1007/s00291-006-0062-3
Chou F-D, Chang P-C, Wang H-M (2006) A hybrid genetic algorithm to minimize makespan for the single batch machine dynamic scheduling problem. Int J Adv Manuf Technol 31(3–4):350–359. doi:10.1007/s00170-005-0194-7
Gupta A-K, Sivakumar A-I (2007) Controlling delivery performance in semiconductor manufacturing using Look Ahead Batching. Int J Prod Res 45(3):591–613. doi:10.1080/00207540600792226
Erramilli V, Mason S-J (2006) Multiple orders per job compatible batch scheduling. IEEE Trans Electron Packag Manuf 29(4):285–296. doi:10.1109/TEPM.2006.887355
Solomon M, Fowler J-W, Pfund M et al (2002) The inclusion of future arrivals and downstream setups into wafer fabrication batch processing decisions. J Electron Manuf 11(2):149–159. doi:10.1142/S0960313102000370
Mönch L, Zimmermann J, Otto P (2006) Machine learning techniques for scheduling jobs with incompatible families and unequal ready times on parallel batch machines. Eng Appl Artif Intell 19(3):235–245. doi:10.1016/j.engappai.2005.10.001
Liu L-L, Ng C-T, Cheng T-C-E (2007) Scheduling jobs with agreeable processing times and due dates on a single batch processing machine. Theor Comput Sci 374:159–169. doi:10.1016/j.tcs.2006.12.039
Dorigo M (1992) Ottimizzazione, Apprendimento Automatico, ed Algoritmi Basati su Metafora Naturale (Optimization, Learning and Natural Algorithms). Ph.D. thesis, Politecnico di Milano, Italy (in Italian), pp 140
Dorigo M, Stützle T (2004) Ant colony optimization. MIT Press/Bradford Books, Cambridge
Srinivasa Raghavan N-R, Venkataramana M (2006) Scheduling parallel batch processors with incompatible job families using ant colony optimization. Proceedings of the 2006 IEEE International Conference on Automation Science and Engineering, Shanghai, China, Oct 8–10 2006:507–512
Balasubramanian H, Mönch L, Fowler J et al (2004) Genetic algorithm based scheduling of parallel batch machines with incompatible job families to minimize total weighted tardiness. Int J Prod Res 42(8):1621–1638. doi:10.1080/00207540310001636994
Cai Y-W, Kutanoglu E, Hesenbein J et al (2007) Single-machine scheduling problem with advanced process control constraints. AEC/APC Symposium XIX, Indian Wells, CA, USA
Patel N-S (2004) Lot allocation and process control in semiconductor manufacturing—a dynamic game approach. Proceedings of 43rd IEEE Conference on Decision and Control, Volume 4, Nassau, Bahamas, Dec 14–17 2004: 4243–4248
Mönch L, Balasubramanian H, Fowler J-W et al (2005) Heuristic scheduling of jobs on parallel batch machines with incompatible job families and unequal ready times. Comput Oper Res 32(11):2731–2750. doi:10.1016/j.cor.2004.04.001
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Li, L., Qiao, F. & Wu, Q.D. ACO-based multi-objective scheduling of parallel batch processing machines with advanced process control constraints. Int J Adv Manuf Technol 44, 985–994 (2009). https://doi.org/10.1007/s00170-008-1904-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00170-008-1904-8