AccScience Publishing / IJOCTA / Online First / DOI: 10.36922/IJOCTA026140054
Submit to IJOCTA
Cite this article
5
Download
48
Views
Related Info Links
Google Scholar
More by Authors Links
Rinto Yusriski
Journal Browser
Volume | Year
Issue
Search
Forthcoming Issue
Current Issue
View All
News and Announcements
View All
RESEARCH ARTICLE

Minimizing total actual flow time for multi-job batch scheduling on identical machines with a common due date

Rinto Yusriski1* ,  Andri Rachmat Kumalasian Nasution1 ,  Mohd Azlan Suhaimi2
Show Less
1 Department of Industrial Engineering, Faculty of Manufacturing Technology, Universitas Jenderal Achmad Yani, Bandung, Indonesia
2 Advanced Manufacturing Research Group, Faculty of Mechanical Engineering, Universiti Teknologi Malaysia, Skudai, Johor, Malaysia
IJOCTA, 026140054 https://doi.org/10.36922/IJOCTA026140054
Received: 5 April 2026 | Revised: 2 June 2026 | Accepted: 9 June 2026 | Published online: 8 July 2026
© 2026 by the Author(s). This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution -Noncommercial 4.0 International License (CC-by the license) ( https://creativecommons.org/licenses/by-nc/4.0/ )
Download PDF
XML
Cite
Abstract

Batch-processing on identical parallel machines is widely used in discrete manufacturing to reduce setup frequency and maintain coordinated material flow. This paper studies a discrete multi-job batch scheduling problem with job-dependent setup times and the objective of minimizing total actual flow time. Several jobs with integer demands must be assigned to parallel machines and completed by a single common due date. The scheduling decisions include assigning jobs to machines, determining the number and batch sizes, and sequencing the resulting batches under a backward just-in-time scheduling approach. An exact Branch-and-Bound (B&B) algorithm is developed for this problem. Feasible solutions are evaluated using a backwards-packed scheduling procedure, while horizon-based feasibility screening and an allocation-level lower bound are used to prune the search tree. A numerical example and computational experiments show that the algorithm can find globally optimal solutions for small- to medium-sized cases. This makes the proposed B&B a useful exact benchmark for future heuristic development.

Keywords
Batch scheduling
Parallel machines
Branch-and-Bound
Common due date
Total actual flow time
Funding
This research was supported by the Internal Research Funding Scheme of Universitas Jenderal Achmad Yani (UNJANI), Indonesia, as stipulated in Rector’s Decree No. Skep/188/ Unjani/VI/2025 regarding the determination of internal research funding 2025.
Conflict of interest
The authors declare that there are no conflicts of interest with any person, institution, or organization related to the content of this manuscript.
References
  1. Liu L, Yan C-B, Li J. Modeling, analysis, and improvement of batch-discrete manufacturing systems: A systems approach. IEEE Trans Autom Sci Eng. 2022;19(3):1567–1585. https://doi.org/10.1109/TASE.2021.3127048
  2. Shakeri Z, Benfriha K, Varmazyar M, Talhi E, Quenehan A. Production scheduling with multi-robot task allocation in a real industry 4.0 setting. Sci Rep. 2025;15(1):1795. https://doi.org/10.1038/s41598-024-84240-3
  3. Muñoz FT, Ulloa-Navarro J. A make-to-order capacitated lot-sizing model with parallel machines, eligibility constraints, extra shifts, and backorders. Mathematics. 2025;13(11):1798. https://doi.org/10.3390/math13111798
  4. Puka R, Skalna I, Duda J, Derlecki T. EPO extension of dispatching rules to minimize effects of time uncertainty in production scheduling. Appl Sci. 2025;15(13):7408. https://doi.org/10.3390/app15137408
  5. Dey BK, Pareek S, Tayyab M, Sarkar B. Autonomation policy to control WIP inventory in a smart production system. Int J Prod Res. 2021;59(4):1258–1280. https://doi.org/10.1080/00207543.2020.1722325
  6. Sarkar B, Mridha B, Pareek S. A sustainable smart multi-type biofuel manufacturing with the optimum energy utilization under flexible production. J Clean Prod. 2022;332:129869. https://doi.org/10.1016/j.jclepro.2021.129869
  7. Sarkar B, Guchhait R, Sarkar M. A sustainable electric vehicle smart production with WIP inventory of outsourced spare parts. J Ind Inf Integr. 2026;49:100998. https://doi.org/10.1016/j.jii.2025.100998
  8. Halim AH, Miyazaki S, Ohta H. Batch-scheduling problems to minimize actual flow times of parts through the shop under JIT environment. Eur J Oper Res. 1994;72(3):529–544. https://doi.org/10.1016/0377-2217(94)90421-9
  9. Hidayat NP, Aribowo W, Halim AH. A single batch processor scheduling model with additional setup times to minimize total actual flowtime of parts of multiple items. J Phys Conf Ser. 2021;1858(1):012019.

https://doi.org/10.1088/1742-6596/1858/1/012019

  1. Suryadhini PP, Sukoyo, Suprayogi, Halim AH. A batch scheduling model for a three-stage flow shop with job and batch processors considering a sampling inspection to minimize expected total actual flow time. J Ind Eng Manag. 2021;14(3):520–537. https://doi.org/10.3926/jiem.3438
  2. Yusriski R, Sukoyo, Samadhi TMA, Halim AH. Integer batch scheduling problems for a single machine with simultaneous effect of learning and forgetting to minimize total actual flow time. Int J Ind Eng Comput. 2015;6(3):365–378. https://doi.org/10.5267/j.ijiec.2015.2.005
  3. Yusriski R, Sukoyo, Samadhi TMA, Halim AH. An integer batch scheduling model considering learning, forgetting, and deterioration effects for a single machine to minimize total inventory holding cost. IOP Conf Ser Mater Sci Eng. 2018;319:012038.

https://doi.org/10.1088/1757-899X/319/1/012038

  1. Yusriski R, Astuti B, Biksono D, Wardani TA. A single machine multi-job integer batch scheduling problem with multi due date to minimize total actual flow time. Decis Sci Lett. 2021;10(3):231– 240. https://doi.org/10.5267/j.dsl.2021.4.002
  2. Rahmawati S, Masruroh NA, Rifai AP. Integrated production and delivery batching for simultaneous multi-job scheduling in multi-factory environments: Modeling, linearization, and optimization. Prod Eng. 2026;20:4. https://doi.org/10.1007/s11740-025-01398-z
  3. Mao Z, Cao T, Fu E, Fang K, Huang D. An adaptive hybrid neighbourhood search algorithm for order acceptance and batch scheduling problem in additive manufacturing. Int J Prod Res. 2025;1–25. https://doi.org/10.1080/00207543.2025.2516189
  4. Yusriski R. Application of the overlapping method to the flow shop scheduling problem to minimize the makespan. Int J Technol Energy. 2025;1(3):107–122. https://doi.org/10.71364/ijte.v1i3.14
  5. Badri SA, Ghazanfari M, Makui A. An integrated model for product mix problem and scheduling considering overlapped operations. Decis Sci Lett. 2014;3(4):523–534. https://doi.org/10.5267/j.dsl.2014.5.006
  6. Kurniawan D, Yusriski R, Isnaini MM, Ma’ruf A, Halim AH. A flow shop batch scheduling model with pre-processing and time-changing effects to minimize total actual flow time. J Ind Eng Manag. 2024;17(2):542–561. https://doi.org/10.3926/jiem.7134
  7. Sibarani AA, Setyaningrum DT, Waluyu S. Multi-item flow shop batch scheduling with two stages dedicated machines to minimize total actual flow time. Int J Integr Eng. 2025;17(1):140–153. https://doi.org/10.30880/ijie.2025.17.01.012
  8. Sibarani AA, Prabowoputra DM, Melita P. Modeling batch scheduling in a three-stage flow shop with multi-item on batch-job-batch processors to minimize total actual flow time. Ind Eng Manag Syst. 2025;24(2):188–201. https://doi.org/10.7232/iems.2025.24.2.188
  9. Maulidya R, Suprayogi, Wangsaputra R, Halim AH. Batch scheduling of unique and common components for a three-stage hybrid flow shop processing different product types with multiple due dates to minimize total actual flow time. In: Intelligent Engineering and Management for Industry 4.0. Springer; 2022:13–24. https://doi.org/10.1007/978-3-030-94683-8_2
  10. Suryadhini PP, Sukoyo, Suprayogi. A batch scheduling model for a three-stage flowshop with batch processor and heterogeneous job processor to minimize total actual flowtime. In: Intelligent Engineering and Management for Industry 4.0. Springer; 2022:1–12. https://doi.org/10.1007/978-3-030-94683-8_1
  11. Yusriski R, Nasution ARK, Lukas L, Wijayanti L, Octaviani S. A two-machine flow shop batch scheduling model to minimize total actual flow time. J Tek Ind. 2023;25(2):179–194. https://doi.org/10.9744/jti.25.2.179-194
  12. Medeiros JMF, Subramanian A, Queiroga E. Population-based iterated local search for batch scheduling on parallel machines with incompatible job families, release dates, and tardiness penalties. Optim Lett. 2025;19(1):193–210. https://doi.org/10.1007/s11590-024-02116-x
  13. Yang H, Du Y, Li Y, Qian W, Hu B. A heuristic mutation based genetic algorithm for fast parallel scheduling of steel cold rolling. Chin J Mech Eng. 2025;38:100. https://doi.org/10.1186/s10033-025-01271-1
  14. Zhang L, Li S, Geng Z, Chen R, Xu J. Multiple parallel-batch machines scheduling with additive resource assignment and machine available times. Discrete Appl Math. 2026;379:675–684. https://doi.org/10.1016/j.dam.2025.09.035
  15. Mazdeh MM, Heydari M, Karamouzian A. An integrated model of scheduling, batch delivery and supplier selection in a make-to-order manufacturing system. Decis Sci Lett. 2016;5(2):189–200. https://doi.org/10.5267/j.dsl.2015.12.005
  16. Zahedi Z, Salim A, Yusriski R, Haris H. Optimization of an integrated batch production and maintenance scheduling on flow shop with two machines. Int J Ind Eng Comput. 2019;10(2):225–238. https://doi.org/10.5267/j.ijiec.2018.7.001
  17. Chen Y, Xu L, Rauf M, Li P, Mumtaz J. Multi-objective artificial bee colony algorithm for energy-efficient scheduling of unrelated parallel batch processing machines with flexible preventive maintenance. Int J Ind Eng Comput. 2025;16(3):619–640. https://doi.org/10.5267/j.ijiec.2025.4.008
  18. Fang W, Wang Z, Luo D. Research on integrated optimization of order allocation and lot-sizing sequencing for mixed-model parallel assembly lines using improved intelligent optimization algorithm. Int J Ind Eng Comput. 2026;17(1):31– 50. https://doi.org/10.5267/j.ijiec.2025.12.004
  19. ElWakil M, Lersteau C, Shen W, Sabry I. Optimising batch scheduling on non-identical parallel machines: Lower bounds, MIP, branch-and-price, and heuristics. Int J Prod Res. 2025;63(24):9722–9747. https://doi.org/10.1080/00207543.2025.2524521
  20. Santos MEP, Silva YLTV, Araújo MCB de. An adaptive local search for large-scale parallel machine scheduling in textile production with release dates and sequence-dependent setup times. Int J Ind Eng Comput. 2025;16(3):693–708. https://doi.org/10.5267/j.ijiec.2025.4.004
  21. Ou J, Li W. Scheduling mixed batch machines with inclusive processing set restrictions and non-identical capacities. Eur J Oper Res. 2026;328(2):407–414. https://doi.org/10.1016/j.ejor.2025.07.012
  22. Sun T, Wang J-Q, Fan G-Q, Liu Z. Generalized parallel batch scheduling: Batch processing time non-decreasing in job width and thickness. Omega. 2026;103558. https://doi.org/10.1016/j.omega.2026.103558
  23. Fan G-Q, Wang J-Q, Liu Z. A scheduling game on parallel batch machines with setup cost. J Sched. 2026;29:143–156. https://doi.org/10.1007/s10951-025-00863-y
  24. Huang Y, Zhou B. A Tabu-Bi-label hybridized branch and price algorithm for just-in-time material handling scheduling problems of mixed-model assembly lines with electric vehicle recharging requirements. J Heuristics. 2025;31(3):27. https://doi.org/10.1007/s10732-025-09563-4
  25. Ozturkoglu O. Identical parallel machine scheduling with nonlinear deterioration and multiple rate modifying activities. Int J Optim Control Theor Appl. 2017;7(2):167–176. https://doi.org/10.11121/ijocta.01.2017.00328
  26. Demir HI, Canpolat O. Integrated process planning, WSPT scheduling and WSLK due-date assignment using genetic algorithms and evolutionary strategies. Int J Optim Control Theor Appl. 2018;8(1):73–83. https://doi.org/10.11121/ijocta.01.2018.00412
  27. Karakaş E, Özpalamutçu H. A genetic algorithm for fuzzy order acceptance and scheduling problem. Int J Optim Control Theor Appl. 2019;9(2):186– 196. https://doi.org/10.11121/ijocta.01.2019.00711
  28. Arık OA. Optimal policies for minimizing total job completion times and deviations from common due dates in unrelated parallel machine scheduling. OPSEARCH. 2024;61(3):1654–1680. https://doi.org/10.1007/s12597-024-00750-8
  29. Mor B, Shapira D, Sonn N. Minimizing the total weighted earliness–tardiness about a non-restrictive common due date with optional job rejection on single and multiple machines. Comput Appl Math. 2026;45(5):217. https://doi.org/10.1007/s40314-025-03586-0
  30. Yang Y, Ding H, He W. Online budget allocation maximization problem on two uniform machines with a common due date. In: International Computing and Combinatorics Conference. Vol 15983. Springer; 2026:346–357. https://doi.org/10.1007/978-981-95-0215-8_26
  31. Kucukkoc I. Scheduling of distributed additive manufacturing machines considering carbon emissions. Int J Optim Control Theor Appl. 2024;14(1):20–31. https://doi.org/10.11121/ijocta.1444
  32. Huertas JA, Hentenryck PV. Parallel Batch Scheduling with Incompatible Job Families via Constraint Programming. IEEE Trans Semicond Manufact. 2025;38(4):901-916. https://doi.org/10.1109/TSM.2025.3601510
  33. Rolim GA, Tomazella CP, Nagano MS. On the integration of reinforcement learning and simulated annealing for the parallel batch scheduling problem with setups. Eur J Oper Res. 2025;326(2):220–233. https://doi.org/10.1016/j.ejor.2025.04.042
  34. Sun T, Wang JQ, Fan GQ, Liu Z. Submodular batch scheduling on parallel machines. Nav Res Logist. 2025;72(2):242–259. https://doi.org/10.1002/nav.22221
  35. Shahvari O, Logendran R, Tavana M. An efficient model-based branch-and-price algorithm for unrelated-parallel machine batching and scheduling problems. J Sched. 2022;25(5):589– 621. https://doi.org/10.1007/s10951-022-00729-7
  36. Li Y, Côté JF, Callegari-Coelho L, Wu P. Novel formulations and logic-based benders decomposition for the integrated parallel machine scheduling and location problem. INFORMS J Comput. 2022;34(2):1048–1069. https://doi.org/10.1287/ijoc.2021.1113
  37. Chen J. Branch-and-price algorithms for parallel machine scheduling with machine usage costs. Doctoral dissertation. Université Gustave Eiffel; Université de Technologie de Hefei; 2025. Accessed July, 8, 2026. https://theses.hal.science/ tel-05473231v1/document
  38. Yusriski R, Nasution ARK, Isnaini MM, Halim AH. A batch scheduling model on unrelated parallel machines with resource constraints and sequence-dependent setup time to minimize total actual flow time. J Ind Eng Manag. 2026;19(1):58– 81. https://doi.org/10.3926/jiem.8710
Share
Back to top
An International Journal of Optimization and Control: Theories & Applications, Electronic ISSN: 2146-5703 Print ISSN: 2146-0957, Published by AccScience Publishing
We use cookies on our website to ensure you get the best experience.
Read more about our cookies here
Accept