Dynamic scheduling strategy and algorithm for mixed batch scheduling in vacuum freeze-dried fruit processes

• Autorzy: Huang JinDian , Hong YingHan , Lin KeYe

Identyfikatory

DOI

10.30657/pea.2024.30.45

• Języki publikacji: EN

Abstrakty

EN

Vacuum freeze-dried fruit processes consisting of heating and holding are modelled as a mixed batch scheduling with the objective of minimizing the makespan. The jobs differ from each other in job family, size, weight and ready time. The batch processing time is determined by the longest job and the total weight of the jobs in the batch. A mixedinteger linear programming model is developed and tested with small-scale examples. Typical batch scheduling strategies are analysed and a machine based dynamic programming strategy is proposed. The machine-based dynamic scheduling strategy is applied to design improved genetic and particle swarm optimization algorithms, which demonstrate the effectiveness of this strategy. The worst-case ratio of the algorithms using machine dynamic programming strategy are proved. Numerical experiments show that the heuristic algorithm, genetic algorithm, and particle swarm optimization algorithm based on machine dynamic scheduling strategy outperform related algorithms using greedy and job-based dynamic scheduling strategies.

Słowa kluczowe

EN

batch processing machines; scheduling strategy; genetic algorithm; particle swarm optimization algorithm; metaheuristic algorithm

PL

maszyny do przetwarzania wsadowego; strategia harmonogramowania; algorytm genetyczny; algorytm optymalizacji roju cząstek; algorytm metaheurystyczny

• Wydawca: Oficyna Wydawnicza Stowarzyszenia Menedżerów Jakości i Produkcji
• Czasopismo: Production Engineering Archives
• Rocznik: 2024
• Tom: Vol. 30, Iss. 4
• Strony: 477--490
• Opis fizyczny: Bibliogr. 32 poz., rys., tab.

Twórcy

autor

Huang JinDian

• School of Intelligent Manufacturing Industry, Hanshan Normal University, Chaozhou, Guangdong, China

• https://orcid.org/0000-0002-4488-136X

autor

Hong YingHan

• School of Intelligent Manufacturing Industry, Hanshan Normal University, Chaozhou, Guangdong, China

autor

Lin KeYe

• School of Intelligent Manufacturing Industry, Hanshan Normal University, Chaozhou, Guangdong, China

• https://orcid.org/0009-0004-3798-301X

Bibliografia

• 1. Aloulou, M.A., Bouzaiene, A., Dridi, N., Vanderpooten, D., 2014 A bicriteria two-machine flow-shop serial-batching scheduling problem with bounded batch size. Journal of Scheduling, 17(1), 17-29.
• 2. Arroyo, J.E.C., Leung, J.Y.T., 2017. Scheduling unrelated parallel batch pro-cessing machines with non-identical job sizes and unequal ready times. Computers & Operations Research, 78, 117-128.
• 3. Chai, X., Li, W., Ng, C.T., Cheng, T.C.E., 2023. Approximation algorithms for batch scheduling with processing set restrictions. Journal of Schedul-ing, 26, 523–533.
• 4. Chen, R.B., Lu, L.F., Yuan, J.J., Zhang, L.Q., 2020. Improved Approximation Algorithm for Scheduling on a Serial Batch Machine with Split-Allowed Delivery. Journal of the Operations Research Society of China, 8(1), 133-143.
• 5. Cheng, B., Yang, S., Hu, X., Chen, B., 2012. Minimizing makespan and total completion time for parallel batch processing machines with non-identi-cal job sizes. Applied Mathematical Modelling, 36(7), 3161-3167.
• 6. Chung, S.H., Tai, Y.T., Pearn, W.L., 2009. Minimising makespan on parallel batch processing machines with non-identical ready time and arbitrary job sizes. International Journal of Production Research, 47(18), 5109-5128.
• 7. Damodaran, P., Velez-Gallego, M.C., 2010. Heuristics for makespan minimi-zation on parallel batch processing machines with unequal job ready times. International Journal of Advanced Manufacturing Technology, 49, 1119-1128.
• 8. Geng, Z., Yuan. J., Yuan, J., 2018. Scheduling with or without precedence relations on a serial-batch machine to minimize makespan and maximum cost. Applied Mathematics and Computation, 332, 1-18.
• 9. Graham, R.L., Lawler, E.L., Lenstra, J.K., Rinnooy-Kan, A.H.G., 1979. Op-timization and approximation in deterministic sequencing and schedul-ing: a survey. Annals of Discrete Mathematics, 5, 287-326.
• 10. He, C., Xu, C.Q., Lin, H., 2020. Serial-batching scheduling with two agents to minimize makespan and maximum cost. Journal of Scheduling, 23(5), 609-617.
• 11. He, C., Lin, H., 2021. Improved algorithms for two-agent scheduling on an unbounded serial-batching machine. Discrete Optimization, 41, 1572-5286.
• 12. Huang, J.Y., Wang, L., Jiang, Z.B., 2020. A method combining rules with genetic algorithm for minimizing makespan on a batch processing ma-chine with preventive maintenance. International Journal of Production Research, 58(13), 4086-4102.
• 13. Hulett, M., Damodaran, P., Amouie, M., 2017. Scheduling Non-identical Par-allel Batch Processing Machines to Minimize Total Weighted Tardiness Using Particle Swarm Optimization. Computers & Industrial Engineer-ing, 113(11), 425-436.
• 14. Jiang, W., Shen, Y.L., Liu, L.X., Zhao, X.C., Shi, L., 2022. A new method for a class of parallel batch machine scheduling problem. Flexible Services and Manufacturing Journal, 34, 518–550.
• 15. Lee, C.Y., Uzsoy, R., Martin-Vega, L.A., 1992. Efficient algorithms for scheduling semiconductor burn-in operations. Operations Re-search, 40(4), 764-775.
• 16. Li, S., 2017. Parallel batch scheduling with inclusive processing set re-strictions and non-identical capacities to minimize makespan. European Journal of Operational Research, 260(1), 12-20.
• 17. Li, S.S., Zhang, Y.Z., 2014. Serial batch scheduling on uniform parallel ma-chines to minimize total completion time. Information Processing Let-ters, 114(12), 692-695.
• 18. Li, X.L., Li, Y.P., Wang, Y., 2017. Minimising makespan on a batch pro-cessing machine using heuristics improved by an enumeration scheme. International Journal of Production Research, 55(1), 176-186.
• 19. Li, Y.J. and Li, S.G., 2020. Scheduling jobs with sizes and delivery times on identical parallel batch machines. Theoretical Computer Science, Vol.841, pp.1-9.
• 20. Muter, B., 2020. Exact algorithms to minimize makespan on single and par-allel batch processing machines. European Journal of Operational Re-search. 285(2), 470-483.
• 21. Mohammad, Y., Mozhgan, M., Amir, H.A., 2020. Semi-permutation-based genetic algorithm for order acceptance and scheduling in two-stage as-sembly problem. Neural Computing and Applications, 32(30), 2989-3003.
• 22. Pei, J., Liu, X.B., Pardalos, P.M., Li, K., Fan, W.J., Migdalas, A., 2017. Sin-gle-machine serial-batching scheduling with a machine availability con-straint, position-dependent processing time, and time-dependent set-up time. Optimization Letters, 11(7), 1257-1271.
• 23. Rim, Z., Imed, E.B., Abderrazek, J., 2019. A two-level particle swarm opti-mization algorithm for the flexible job shop scheduling problem. Swarm Intelligence, 13(2), 145–168.
• 24. Uzunoglu, A., Gahm, C., Tuma, A., 2023. A machine learning enhanced multi-start heuristic to efficiently solve a serial-batch scheduling prob-lem. Annals of Operations Research, 1-22.
• 25. Shabtay, D., 2014. The single machine serial batch scheduling problem with rejection to minimize total completion time and total rejection cost. Eu-ropean Journal of Operational Research, 233(1), 64-74.
• 26. Shi, Z., Huang, Z., Shi, L., 2018. Customer order scheduling on batch pro-cessing machines with incompatible job families, International Journal of Production Research, 56(1-2), 795-808.
• 27. Song, L.B., Liu, C., Shi, H.B., Zhu, J., 2022. An Improved Immune Genetic Algorithm for Solving the Flexible Job Shop Scheduling Problem with Batch Processing. Wireless Communications and Mobile Computing, pp.1-17.
• 28. Sun, X.Y., Shen, W.M., Vogel-Heuser, B., 2023. A hybrid genetic algorithm for distributed hybrid blocking flowshop scheduling problem. Journal of Manufacturing Systems, 390-405.
• 29. Wang, J.Q., Fan, G., Liu, Z. 2020. Mixed batch scheduling on identical ma-chines. Journal of Scheduling, 23, 487–496.
• 30. Willy, C.S., Byung, S.K., 2024. Particle swarm optimization for integrated scheduling problem with batch additive manufacturing and batch direct-shipping delivery. Computers and Operations Research, 161, 106430.
• 31. Zhang, X., Li, X., Wang, J. 2017. Local search algorithm with path relinking for single batch-processing machine scheduling problem. Neural Compu-ting and Applications, 28(1), 313-326.
• 32. Zheng, S.X., Xie, N.M., Wu, Q., 2021. Single batch machine scheduling with dual setup times for autoclave molding manufacturing. Computers & Op-erations Research, 133(9), 1-23.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa nr POPUL/SP/0154/2024/02 w ramach programu "Społeczna odpowiedzialność nauki II" - moduł: Popularyzacja nauki (2025).