Parallel Batch Processor Machine Scheduling Using Multi-Population SPEA-II Algorithm
##plugins.themes.bootstrap3.article.main##
Abstract
The increasing competition in the industrial sector requires companies to provide more optimal services, particularly in terms of production speed by increasing machine utilization. This can be achieved by implementing parallel batch scheduling. In conventional scheduling, a machine is only able to handle one job at a time, whereas in parallel batch scheduling, a machine can process a group of jobs simultaneously based on its capacity. Flexible Job Shop with parallel batch processor has been studied by several researchers, but the objective function has generally been limited to minimizing makespan. This research aims to minimize multi objective function that are energy consumption and makespan by using the Modified Strength Pareto Evolutionary Algorithm-II (SPEA2). Modifications of the algorithm are conducted by applying multi-population that run in parallel so that the optimization process can avoid local optima. The results of the research show that Multi-Population SPEA2 provides more optimal results compared to classical SPEA2 and benchmarks from previous research.
##plugins.themes.bootstrap3.article.details##
How to Cite
Tampubolon, F. R., Siagian, S. M., Samaria Chrisna HS, Rischa Devita, & Sitinjak , A. A. (2025). Parallel Batch Processor Machine Scheduling Using Multi-Population SPEA-II Algorithm . International Journal of Basic and Applied Science, 14(1), 1–11. https://doi.org/10.35335/ijobas.v14i1.653
References
M. L. R. Varela, G. D. Putnik, V. K. Manupati, G. Rajyalakshmi, J. Trojanowska, and J. Machado, “Integrated process planning and scheduling in networked manufacturing systems for I4.0: a review and framework proposal,” Wirel. Networks, vol. 27, no. 3, pp. 1587–1599, 2021, doi: 10.1007/s11276-019-02082-8.
V. T’Kindt and J.-C. Billaut, Multicriteria Scheduling, Second. Springer.
M. Karim, O. Hamlaoui, and H. Hadda, “Regular articles A simulated annealing metaheuristic approach to hybrid flow shop scheduling problem,” Adv. Ind. Manuf. Eng., vol. 9, no. December 2023, p. 100144, 2024, doi: 10.1016/j.aime.2024.100144.
G. Da Col and E. C. Teppan, “Industrial-size job shop scheduling with constraint programming,” Oper. Res. Perspect., vol. 9, no. March, p. 100249, 2022, doi: 10.1016/j.orp.2022.100249.
S. Dauzère-Pérès, J. Ding, L. Shen, and K. Tamssaouet, “The flexible job shop scheduling problem: A review,” Eur. J. Oper. Res., vol. 314, no. 2, pp. 409–432, 2024, doi: 10.1016/j.ejor.2023.05.017.
O. Ozturk, “When serial batch scheduling involves parallel batching decisions: A branch and price scheme,” Comput. Oper. Res., vol. 137, no. July 2020, p. 105514, 2022, doi: 10.1016/j.cor.2021.105514.
J. Xu, J. Q. Wang, and Z. Liu, “Parallel batch scheduling: Impact of increasing machine capacity,” Omega (United Kingdom), vol. 108, p. 102567, 2022, doi: 10.1016/j.omega.2021.102567.
Y. Li, A. Wang, and S. Zhang, “A Batch Scheduling Technique of Flexible Job-Shop Based on Improved Genetic Algorithm,” 2022 IEEE Int. Conf. Mechatronics Autom. ICMA 2022, pp. 1463–1467, 2022, doi: 10.1109/ICMA54519.2022.9856332.
A. Ham, “Flexible job shop scheduling problem for parallel batch processing machine with compatible job families,” Appl. Math. Model., vol. 45, pp. 551–562, 2017, doi: 10.1016/j.apm.2016.12.034.
L. Song, C. Liu, and H. Shi, “Discrete particle swarm algorithm with Q-Learning for solving flexible job shop scheduling problem with parallel batch processing machine,” J. Phys. Conf. Ser., vol. 2303, no. 1, pp. 1–11, 2022, doi: 10.1088/1742-6596/2303/1/012022.
B. Ji, S. Zhang, S. S. Yu, and B. Zhang, “Mathematical Modeling and A Novel Heuristic Method for Flexible Job-Shop Batch Scheduling Problem with Incompatible Jobs,” Sustain., vol. 15, no. 3, 2023, doi: 10.3390/su15031954.
L. Xue, S. Zhao, A. Mahmoudi, and M. R. Feylizadeh, “Flexible job-shop scheduling problem with parallel batch machines based on an enhanced multi-population genetic algorithm,” Complex Intell. Syst., vol. 10, no. 3, pp. 4083–4101, 2024, doi: 10.1007/s40747-024-01374-7.
O. A. Olanrewaju, F. Luiz, and P. Krykhtine, “Minimum-Energy Scheduling of Flexible Job-Shop Through Optimization and Comprehensive Heuristic,” 2024.
M. Danishvar, S. Danishvar, E. Katsou, S. A. Mansouri, and A. Mousavi, “Energy-Aware Flowshop Scheduling: A Case for AI-Driven Sustainable Manufacturing,” IEEE Access, vol. 9, pp. 141678–141692, 2021, doi: 10.1109/ACCESS.2021.3120126.
H. Terbrack and T. Claus, “Computers & Industrial Engineering The generalized energy-aware flexible job shop scheduling model : A constraint programming approach,” Comput. Ind. Eng., vol. 204, no. March, p. 111065, 2025, doi: 10.1016/j.cie.2025.111065.
S. Christian, B. Daniela, and G. Guido, “A memetic NSGA ‑ II for the multi ‑ objective flexible job shop scheduling problem with real ‑ time energy tariffs,” Flex. Serv. Manuf. J., vol. 36, no. 4, pp. 1530–1570, 2024, doi: 10.1007/s10696-023-09517-7.
D. Alemão, A. D. Rocha, and J. Barata, “Smart manufacturing scheduling approaches—systematic review and future directions,” Appl. Sci., vol. 11, no. 5, pp. 1–20, 2021, doi: 10.3390/app11052186.
P. K. Shukla, C. Hirsch, and H. Schmeck, “Towards a Deeper Understanding of Trade-offs Using Multi-objective Evolutionary Algorithms,” no. Mcdm, pp. 396–397, 2012.
F. Luan, H. Zhao, S. Qiang, Y. He, and B. Tang, “Sustainable Computing : Informatics and Systems Enhanced NSGA-II for multi-objective energy-saving flexible job shop scheduling,” vol. 39, no. April 2022, pp. 0–2, 2023.
S. Larraín, L. Pradenas, I. Pulkkinen, and F. Santander, “Multiobjective optimization of a continuous kraft pulp digester using SPEA2,” Comput. Chem. Eng., vol. 143, 2020, doi: 10.1016/j.compchemeng.2020.107086.
I. Huseyinov and A. Bayrakdar, “Performance Evaluation of NSGA-III and SPEA2 in Solving a Multi-Objective Single-Period Multi-Item Inventory Problem,” UBMK 2019 - Proceedings, 4th Int. Conf. Comput. Sci. Eng., no. 4, pp. 531–535, 2019, doi: 10.1109/UBMK.2019.8907139.
Z. Zhao, B. Liu, C. Zhang, and H. Liu, “An improved adaptive NSGA-II with multi-population algorithm,” pp. 569–580, 2019.
S. Zhou, M. Jin, and N. Du, “Energy-efficient scheduling of a single batch processing machine with dynamic job arrival times,” Energy, vol. 209, 2020, doi: 10.1016/j.energy.2020.118420.
D. Li, Q. Hou, M. Zhao, and Z. Wu, “Reliable Task Planning of Networked Devices as a Multi-Objective Problem Using NSGA-II and Reinforcement Learning,” IEEE Access, vol. 10, pp. 6684–6695, 2022, doi: 10.1109/ACCESS.2022.3141912.
P. Brandimarte, “Routing and scheduling in a flexible job shop by tabu search,” Ann. Oper. Res., vol. 41, no. 3, pp. 157–183, 1993, doi: 10.1007/BF02023073.
V. T’Kindt and J.-C. Billaut, Multicriteria Scheduling, Second. Springer.
M. Karim, O. Hamlaoui, and H. Hadda, “Regular articles A simulated annealing metaheuristic approach to hybrid flow shop scheduling problem,” Adv. Ind. Manuf. Eng., vol. 9, no. December 2023, p. 100144, 2024, doi: 10.1016/j.aime.2024.100144.
G. Da Col and E. C. Teppan, “Industrial-size job shop scheduling with constraint programming,” Oper. Res. Perspect., vol. 9, no. March, p. 100249, 2022, doi: 10.1016/j.orp.2022.100249.
S. Dauzère-Pérès, J. Ding, L. Shen, and K. Tamssaouet, “The flexible job shop scheduling problem: A review,” Eur. J. Oper. Res., vol. 314, no. 2, pp. 409–432, 2024, doi: 10.1016/j.ejor.2023.05.017.
O. Ozturk, “When serial batch scheduling involves parallel batching decisions: A branch and price scheme,” Comput. Oper. Res., vol. 137, no. July 2020, p. 105514, 2022, doi: 10.1016/j.cor.2021.105514.
J. Xu, J. Q. Wang, and Z. Liu, “Parallel batch scheduling: Impact of increasing machine capacity,” Omega (United Kingdom), vol. 108, p. 102567, 2022, doi: 10.1016/j.omega.2021.102567.
Y. Li, A. Wang, and S. Zhang, “A Batch Scheduling Technique of Flexible Job-Shop Based on Improved Genetic Algorithm,” 2022 IEEE Int. Conf. Mechatronics Autom. ICMA 2022, pp. 1463–1467, 2022, doi: 10.1109/ICMA54519.2022.9856332.
A. Ham, “Flexible job shop scheduling problem for parallel batch processing machine with compatible job families,” Appl. Math. Model., vol. 45, pp. 551–562, 2017, doi: 10.1016/j.apm.2016.12.034.
L. Song, C. Liu, and H. Shi, “Discrete particle swarm algorithm with Q-Learning for solving flexible job shop scheduling problem with parallel batch processing machine,” J. Phys. Conf. Ser., vol. 2303, no. 1, pp. 1–11, 2022, doi: 10.1088/1742-6596/2303/1/012022.
B. Ji, S. Zhang, S. S. Yu, and B. Zhang, “Mathematical Modeling and A Novel Heuristic Method for Flexible Job-Shop Batch Scheduling Problem with Incompatible Jobs,” Sustain., vol. 15, no. 3, 2023, doi: 10.3390/su15031954.
L. Xue, S. Zhao, A. Mahmoudi, and M. R. Feylizadeh, “Flexible job-shop scheduling problem with parallel batch machines based on an enhanced multi-population genetic algorithm,” Complex Intell. Syst., vol. 10, no. 3, pp. 4083–4101, 2024, doi: 10.1007/s40747-024-01374-7.
O. A. Olanrewaju, F. Luiz, and P. Krykhtine, “Minimum-Energy Scheduling of Flexible Job-Shop Through Optimization and Comprehensive Heuristic,” 2024.
M. Danishvar, S. Danishvar, E. Katsou, S. A. Mansouri, and A. Mousavi, “Energy-Aware Flowshop Scheduling: A Case for AI-Driven Sustainable Manufacturing,” IEEE Access, vol. 9, pp. 141678–141692, 2021, doi: 10.1109/ACCESS.2021.3120126.
H. Terbrack and T. Claus, “Computers & Industrial Engineering The generalized energy-aware flexible job shop scheduling model : A constraint programming approach,” Comput. Ind. Eng., vol. 204, no. March, p. 111065, 2025, doi: 10.1016/j.cie.2025.111065.
S. Christian, B. Daniela, and G. Guido, “A memetic NSGA ‑ II for the multi ‑ objective flexible job shop scheduling problem with real ‑ time energy tariffs,” Flex. Serv. Manuf. J., vol. 36, no. 4, pp. 1530–1570, 2024, doi: 10.1007/s10696-023-09517-7.
D. Alemão, A. D. Rocha, and J. Barata, “Smart manufacturing scheduling approaches—systematic review and future directions,” Appl. Sci., vol. 11, no. 5, pp. 1–20, 2021, doi: 10.3390/app11052186.
P. K. Shukla, C. Hirsch, and H. Schmeck, “Towards a Deeper Understanding of Trade-offs Using Multi-objective Evolutionary Algorithms,” no. Mcdm, pp. 396–397, 2012.
F. Luan, H. Zhao, S. Qiang, Y. He, and B. Tang, “Sustainable Computing : Informatics and Systems Enhanced NSGA-II for multi-objective energy-saving flexible job shop scheduling,” vol. 39, no. April 2022, pp. 0–2, 2023.
S. Larraín, L. Pradenas, I. Pulkkinen, and F. Santander, “Multiobjective optimization of a continuous kraft pulp digester using SPEA2,” Comput. Chem. Eng., vol. 143, 2020, doi: 10.1016/j.compchemeng.2020.107086.
I. Huseyinov and A. Bayrakdar, “Performance Evaluation of NSGA-III and SPEA2 in Solving a Multi-Objective Single-Period Multi-Item Inventory Problem,” UBMK 2019 - Proceedings, 4th Int. Conf. Comput. Sci. Eng., no. 4, pp. 531–535, 2019, doi: 10.1109/UBMK.2019.8907139.
Z. Zhao, B. Liu, C. Zhang, and H. Liu, “An improved adaptive NSGA-II with multi-population algorithm,” pp. 569–580, 2019.
S. Zhou, M. Jin, and N. Du, “Energy-efficient scheduling of a single batch processing machine with dynamic job arrival times,” Energy, vol. 209, 2020, doi: 10.1016/j.energy.2020.118420.
D. Li, Q. Hou, M. Zhao, and Z. Wu, “Reliable Task Planning of Networked Devices as a Multi-Objective Problem Using NSGA-II and Reinforcement Learning,” IEEE Access, vol. 10, pp. 6684–6695, 2022, doi: 10.1109/ACCESS.2022.3141912.
P. Brandimarte, “Routing and scheduling in a flexible job shop by tabu search,” Ann. Oper. Res., vol. 41, no. 3, pp. 157–183, 1993, doi: 10.1007/BF02023073.
Copyright and Licensing
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.