Scheduling parallel batch processing machines: A case study in the semiconductor industry

Year 2024, , 90 - 105, 18.07.2024

Şeyda Topaloğlu Yıldız , Ezgi Güleç

https://doi.org/10.56554/jtom.1260796

Abstract

This paper presents a mathematical programming-based solution approach for the scheduling problem of batch-processing parallel machines with eligibility constraints. A case study has been presented in the semiconductor industry, where the ovens are scheduled for the underfill cure operation of products. The case includes constraints, such as oven-product eligibility restrictions, loading constraints for the batching of products for ovens, daily production requirements, and oven capacity constraints. In this study, we also assess the difference between creating batches of a single product type or different product types to be allocated to the ovens. The case study results have shown that the proposed models, in comparison to the current situation, increase the occupancy rate of ovens. The execution of the models aids the company in gaining visibility on the scheduling of ovens and successfully managing the production plan and order commitment. The proposed models have been effective and supportive of the semiconductor company.

Keywords

batch processing, scheduling, parallel machines, mixed-integer programming, case study

References

• Ahmadi, J. H., Ahmadi, R. H., Dasu, S., & Tang, C. S. (1992). Batching and scheduling jobs on batch and discrete processors. Operations research, 40(4), 750-763.
• Arroyo, J. E. C., & Leung, J. Y. T. (2017). Scheduling unrelated parallel batch processing machines with nonidentical job sizes and unequal ready times. Computers & Operations Research, 78, 117-128. http://dx.doi.org/10.1016/j.cor.2016.08.015
• Baker, K. R., & Trietsch, D. (2009). Safe scheduling: Setting due dates in single machine problems. European Journal of Operational Research, 196(1), 69-77. http://doi.org/10.1016/j.ejor.2008.02.009
• Beldar, P., Moghtader, M., Giret, A., & Ansaripoor, A. H. (2022). Non-identical parallel machines batch processing problem with release dates, due dates and variable maintenance activity to minimize total tardiness. Computers & Industrial Engineering, 168, 108135. http://doi.org/10.1016/j.cie.2022.108135
• Chandru, V., Lee, C. Y., & Uzsoy, R. (1993). Minimizing total completion time on a batch processing machine with job families. Operations Research Letters, 13(2), 61-65.
• Chang, P. Y., Damodaran*, P., & Melouk, S. (2004). Minimizing makespan on parallel batch processing machines. International Journal of Production Research, 42(19), 4211-4220. http://doi.org/10.1080/00207540410001711863
• Cheng, B., Yang, S., Hu, X., & Chen, B. (2012). Minimizing makespan and total completion time for parallel batch processing machines with non-identical job sizes. Applied Mathematical Modelling, 36(7), 3161-3167. http://doi.org/10.1016/j.apm.2011.09.061
• Chou, F. D. (2007). A joint GA+ DP approach for single burn-in oven scheduling problems with makespan criterion. The International Journal of Advanced Manufacturing Technology, 35, 587-595. https://doi.org/10.1007/s00170-006-0738-5
• Chou, F. D. (2013). Minimising the total weighted tardiness for non-identical parallel batch processing machines with job release times and non-identical job sizes. European Journal of Industrial Engineering, 7(5), 529-557. http://doi.org/10.1504/EJIE.2013.057380
• Damodaran, P., & Chang, P. Y. (2008). Heuristics to minimize makespan of parallel batch processing machines. The International Journal of Advanced Manufacturing Technology, 37, 1005-1013. http://doi.org /10.1007/s00170-007-1042-8
• Fowler, J. W., & Mönch, L. (2022). A survey of scheduling with parallel batch (p-batch) processing. European Journal of Operational Research, 298(1), 1-24. http://doi.org/10.1016/j.ejor.2021.06.012 Ikura, Y., & Gimple, M. (1986). Efficient scheduling algorithms for a single batch processing machine. Operations Research Letters, 5(2), 61-65.
• Jia, Z. H., Huo, S. Y., Li, K., & Chen, H. P. (2019). Integrated scheduling on parallel batch processing machines with non-identical capacities. Engineering Optimization. https://doi.org/10.1080/0305215X.2019.1613388
• Ji, B., Xiao, X., Yu, S. S., & Wu, G (2023). A Hybrid Large Neighborhood Search Method for Minimizing Makespan on unrelated Parallel Batch Processing Machines with Incompatible Job Families. Sustainability, 15(5), 3934. https://doi.org/10.3390/su15053934
• Kashan, A. H., Karimi, B., & Jenabi, M. (2008). A hybrid genetic heuristic for scheduling parallel batch processing machines with arbitrary job sizes. Computers & Operations Research, 35(4), 1084-1098. http://doi.org/10.1016/j.cor.2006.07.005
• Kempf, K. G., Uzsoy, R., & Wang, C. S. (1998). Scheduling a single batch processing machine with secondary resource constraints. Journal of Manufacturing Systems, 17(1), 37-51. http://doi.org/10.1016/S0278- 6125(98)80008-3
• Lee, C. Y., Uzsoy, R., & Martin-Vega, L. A. (1992). Efficient algorithms for scheduling semiconductor burn-in operations. Operations Research, 40(4), 764-775.
• Lee, C. Y. (1999). Minimizing makespan on a single batch processing machine with dynamic job arrivals. International Journal of Production Research, 37(1), 219-236. http://doi.org/10.1080/002075499192020
• Li, L., Qiao, F., & Wu, Q. D. (2009). ACO-based multi-objective scheduling of parallel batch processing machines with advanced process control constraints. The International Journal of Advanced Manufacturing Technology, 44, 985-994. http://doi.org /10.1007/s00170-008-1904-8
• Liu, H., Yuan, J., & Li, W. (2016). Online scheduling of equal length jobs on unbounded parallel batch processing machines with limited restart. Journal of Combinatorial Optimization, 31(4), 1609-1622. http://doi.org/10.1007/s10878-015-9844-3
• Mathirajan, M., & Sivakumar, A. I. (2006). A literature review, classification and simple meta-analysis on scheduling of batch processors in semiconductor. The International Journal of Advanced Manufacturing Technology, 29, 990-1001. https://doi.org/ 10.1007/s00170-005-2585-1
• Nguyen, A. H., & Sheen, G. J. (2023). A decomposition-based heuristic algorithm for parallel batch processing problem with time window constraint. International Journal of Industrial Engineering: Theory, Applications and Practice, 30(2).
• Ozturk, O. (2020). A truncated column generation algorithm for the parallel batch scheduling problem to minimize total flow time. European Journal of Operational Research, 286(2), 432-443. https://doi.org/10.1016/j.ejor.2020.03.044
• Song, C. (2022). A Self-Adaptive Multiobjective Differential Evolution Algorithm for the Unrelated Parallel Batch Processing Machine Scheduling Problem. Mathematical Problems in Engineering. https://doi.org/10.1155/2022/5056356
• Tai, Y. T., & Lai, C. M. (2011). The liquid crystal injection scheduling problem (LCISP). International Journal of Production Research, 49(2), 467-484. https://doi.org/10.1080/00207540903443261
• Uzsoy, R. (1994). Scheduling a single batch processing machine with non-identical job sizes. The International Journal of Production Research, 32(7), 1615-1635.
• Wang, H. M., & Chou, F. D. (2010). Solving the parallel batch-processing machines with different release times, job sizes, and capacity limits by metaheuristics. Expert Systems with Applications, 37(2), 1510-1521. http://dx.doi.org/10.1016/j.eswa.2009.06.070
• Zhou, S., Liu, M., Chen, H., & Li, X. (2016). An effective discrete differential evolution algorithm for scheduling uniform parallel batch processing machines with non-identical capacities and arbitrary job sizes. International Journal of Production Economics, 179, 1-11. https://doi.org/10.1016/j.ijpe.2016.05.014