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

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

1. 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.
2. 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
3. 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
4. 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
5. 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.
6. 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
7. 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
8. 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

9. 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
10. 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
11. 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.
12. 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
13. 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
14. 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
15. 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
16. Lee, C. Y., Uzsoy, R., & Martin-Vega, L. A. (1992). Efficient algorithms for scheduling semiconductor burn-in operations. Operations Research, 40(4), 764-775.
17. 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
18. 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
19. 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
20. 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
21. 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).
22. 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
23. 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
24. 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
25. Uzsoy, R. (1994). Scheduling a single batch processing machine with non-identical job sizes. The International Journal of Production Research, 32(7), 1615-1635.
26. 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
27. 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