Optimising manufacturing schedules with tailored metrics to reduce unproductive times

Alex Abreu; Helio Yochihiro Fuchigami

doi:10.1590/0103-6513.20250004

Research Article

Optimising manufacturing schedules with tailored metrics to reduce unproductive times

Alex Abreu; Helio Yochihiro Fuchigami

http://dx.doi.org/10.1590/0103-6513.20250004 Production, vol.36, e20250004, 2026

PDF

Downloads: 0

Abstract

Paper aims: This study aims to address a manufacturing scheduling problem where jobs are processed in the same sequence across multiple machines, focusing on minimising unproductive time, including machine idle time and job waiting time.

Originality: The research fills a gap in the literature by extensively comparing metrics and heuristic algorithms for the permutational flow shop scheduling problem, introducing four tailored metrics and evaluating their performance against classic rules.

Research method: The study employed computational experiments with 720 instances from four benchmarks, varying the number of jobs and machines. Performance was assessed based on percentage success and failure, average relative deviation, and computational time. An insertion heuristic algorithm was implemented to improve scheduling solutions.

Main findings: The Longest Last Front Idle Time (LLFIT) heuristic outperformed traditional methods, including the NEH heuristic, consistently ranking in the top three across all metrics. LLFIT demonstrated superior performance in minimising core and front idle times as well as core waiting time.

Implications for theory and practice: The LLFIT heuristic offers an efficient and reliable scheduling solution for practitioners in production and operations management, advancing both theoretical understanding and practical applications in minimising unproductive time in flow shop scheduling.

Keywords

Manufacturing system, Scheduling optimisation, Heuristic algorithm, Unproductive time minimisation, Tailored manufacturing metrics

References

Abreu, A. P., & Fuchigami, H. Y. (2022). An efficiency and robustness analysis of warm-start mathematical models for idle and waiting times optimization in the flow shop. Computers & Industrial Engineering, 166, 107976. https://doi.org/10.1016/j.cie.2022.107976.

Alfieri, A., Garraffa, M., Pastore, E., & Salassa, F. (2023). Permutation flowshop problems minimizing core waiting time and core idle time. Computers & Industrial Engineering, 176, 108983. https://doi.org/10.1016/j.cie.2023.108983.

Alidaee, B., Li, H., Wang, H., & Womer, K. (2021). Integer programming formulations in sequencing with total earliness and tardiness penalties, arbitrary due dates, and no idle time: A concise review and extension. Omega, 103, 102446. https://doi.org/10.1016/j.omega.2021.102446.

Allahverdi, A. (2016). A survey of scheduling problems with no-wait in process. European Journal of Operational Research, 255(3), 665-686. https://doi.org/10.1016/j.ejor.2016.05.036.

Allahverdi, A., Aydilek, H., & Aydilek, A. (2020). No-wait flowshop scheduling problem with separate setup times to minimize total tardiness subject to makespan. Applied Mathematics and Computation, 365, 124688. https://doi.org/10.1016/j.amc.2019.124688.

An, Y. J., Kim, Y. D., & Choi, S. W. (2016). Minimizing makespan in a two-machine flowshop with a limited waiting time constraint and sequence-dependent setup times. Computers & Operations Research, 71, 127-136. https://doi.org/10.1016/j.cor.2016.01.017.

Arviv, K., Stern, H., & Edan, Y. (2016). Collaborative reinforcement learning for a two-robot job transfer flow-shop scheduling problem. International Journal of Production Research, 54(4), 1196-1209. https://doi.org/10.1080/00207543.2015.1057297.

Balogh, A., Garraffa, M., O’Sullivan, B., & Salassa, F. (2022). MILP-based local search procedures for minimizing total tardiness in the No-idle Permutation Flowshop Problem. Computers & Operations Research, 146, 105862. https://doi.org/10.1016/j.cor.2022.105862.

Baraz, D., & Mosheiov, G. (2008). A note on a greedy heuristic for flow-shop makespan minimization with no machine idle-time. European Journal of Operational Research, 184(2), 810-813. https://doi.org/10.1016/j.ejor.2006.11.025.

Bektaş, T., Hamzadayı, A., & Ruiz, R. (2020). Benders decomposition for the mixed no-idle permutation flowshop scheduling problem. Journal of Scheduling, 23(4), 513-523. https://doi.org/10.1007/s10951-020-00637-8.

Birgin, E. G., Ferreira, J. E., & Ronconi, D. P. (2020). A filtered beam search method for the m-machine permutation flowshop scheduling problem minimizing the earliness and tardiness penalties and the waiting time of the jobs. Computers & Operations Research, 114, 104824. https://doi.org/10.1016/j.cor.2019.104824.

Cheng, C. Y., Ying, K. C., Li, S. F., & Hsieh, Y. C. (2019). Minimizing makespan in mixed no-wait flowshops with sequence-dependent setup times. Computers & Industrial Engineering, 130, 338-347. https://doi.org/10.1016/j.cie.2019.02.041.

Freitas, M. G., & Fuchigami, H. Y. (2022). A new technology implementation via mathematical modeling for the sequence-dependent setup times of industrial problems. Computers & Industrial Engineering, 172, 108624. https://doi.org/10.1016/j.cie.2022.108624.

Dolan, E. D., & Moré, J. J. (2002). Benchmarking optimization software with performance profiles. Mathematical Programming, 91(2), 201-213. https://doi.org/10.1007/s101070100263.

Fernandez-Viagas, V., & Framinan, J. M. (2014). On insertion tie-breaking rules in heuristics for the permutation flowshop scheduling problem. Computers & Operations Research, 45, 60-67. https://doi.org/10.1016/j.cor.2013.12.012.

Fernandez-Viagas, V., & Framinan, J. M. (2015). A new set of high-performing heuristics to minimise flowtime in permutation flowshops. Computers & Operations Research, 53, 68-80. https://doi.org/10.1016/j.cor.2014.08.004.

Framinan, J. M., Leisten, R., & Rajendran, C. (2003). Different initial sequences for the heuristic of Nawaz, Enscore and Ham to minimize makespan, idletime or flowtime in the static permutation flowshop sequencing problem. International Journal of Production Research, 41(1), 121-148. https://doi.org/10.1080/00207540210161650.

Fuchigami, H. Y., & Abreu, A. P. (2024). Innovative Optimization Algorithms for Large-Sized Industrial Scheduling Problems. Brazilian Archives of Biology and Technology, 67, e24240084. https://doi.org/10.1590/1678-4324-2024240084.

Fuchigami, H. Y., & Prata, B. A. (2023). Coronavirus optimization algorithms for minimizing earliness, tardiness, and anticipation of due dates in permutation flow shop scheduling. Arabian Journal for Science and Engineering, 48(11), 15713-15745. https://doi.org/10.1007/s13369-023-08113-z.

Fuchigami, H. Y., & Rangel, S. (2018). A survey of case studies in production scheduling: Analysis and perspectives. Journal of Computational Science, 25, 425-436. https://doi.org/10.1016/j.jocs.2017.06.004.

Fuchigami, H. Y., Sarker, R., & Rangel, S. (2018). Near-optimal heuristics for just-in-time jobs maximization in flow shop scheduling. Algorithms, 11(4), 43. https://doi.org/10.3390/a11040043.

Fuchigami, H. Y., Severino, M. R., Yamanaka, L., & Oliveira, M. R. (2019, July). A literature review of mathematical programming applications in the fresh agri-food supply chain. InInternational Joint conference on Industrial Engineering and Operations Management(pp. 37-50). Cham: Springer International Publishing.

Geng, D., & Evans, S. (2022). A literature review of energy waste in the manufacturing industry. Computers & Industrial Engineering, 173, 108713. https://doi.org/10.1016/j.cie.2022.108713.

Goncharov, Y., & Sevastyanov, S. (2009). The flow shop problem with no-idle constraints: A review and approximation. European Journal of Operational Research, 196(2), 450-456. https://doi.org/10.1016/j.ejor.2008.03.039.

Gould, N., & Scott, J. (2016). A note on performance profiles for benchmarking software. ACM Transactions on Mathematical Software, 43(2), 1-5. https://doi.org/10.1145/2950048.

Graham, R. L., Lawler, E. L., Lenstra, J. K., & Kan, A. H. (1979). Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics, 5, 287-326. https://doi.org/10.1016/S0167-5060(08)70356-X.

Guo, Y., Huang, M., Wang, Q., & Leon, V. J. (2016). Single-machine rework rescheduling to minimize maximum waiting-times with fixed sequence of jobs and ready times. Computers & Industrial Engineering, 91, 262-273. https://doi.org/10.1016/j.cie.2015.11.021.

Hall, N. G., & Sriskandarajah, C. (1996). A survey of machine scheduling problems with blocking and no-wait in process. Operations Research, 44(3), 510-525. https://doi.org/10.1287/opre.44.3.510.

Hecker, F. T., Stanke, M., Becker, T., & Hitzmann, B. (2014). Application of a modified GA, ACO and a random search procedure to solve the production scheduling of a case study bakery. Expert Systems with Applications, 41(13), 5882-5891. https://doi.org/10.1016/j.eswa.2014.03.047.

Ku, W. Y., & Beck, J. C. (2016). Mixed integer programming models for job shop scheduling: A computational analysis. Computers & Operations Research, 73, 165-173. https://doi.org/10.1016/j.cor.2016.04.006.

Li, X., Wang, Q., & Wu, C. (2008). Heuristic for no-wait flow shops with makespan minimization. International Journal of Production Research, 46(9), 2519-2530. https://doi.org/10.1080/00207540701737997.

Liu, W., Jin, Y., & Price, M. (2016). A new Nawaz–Enscore–Ham-based heuristic for permutation flow-shop problems with bicriteria of makespan and machine idle time. Engineering Optimization, 48(10), 1808-1822. https://doi.org/10.1080/0305215X.2016.1141202.

Maassen, K., Hipp, A., & Perez-Gonzalez, P. (2019). Constructive heuristics for the minimization of core waiting time in permutation flow shop problems. In Proceedings of the 2019 International Conference on Industrial Engineering and Systems Management, IESM 2019 (pp. 1-6). New York: IEEE. https://doi.org/10.1109/IESM45758.2019.8948147.

Maassen, K., Perez-Gonzalez, P., & Günther, L. C. (2020). Relationship between common objective functions, idle time and waiting time in permutation flow shop scheduling. Computers & Operations Research, 121, 104965. https://doi.org/10.1016/j.cor.2020.104965.

Martinez, C., Espinouse, M. L., & Di Mascolo, M. (2019). Re-planning in home healthcare: A decomposition approach to minimize idle time for workers while ensuring continuity of care. IFAC-PapersOnLine, 52(13), 654-659. https://doi.org/10.1016/j.ifacol.2019.11.104.

Moreno, A., Munari, P., & Alem, D. (2019). A branch-and-benders-cut algorithm for the crew scheduling and routing problem in road restoration. European Journal of Operational Research, 275(1), 16-34. https://doi.org/10.1016/j.ejor.2018.11.004.

Nagano, M. S., Rossi, F. L., & Martarelli, N. J. (2019). High-performing heuristics to minimize flowtime in no-idle permutation flowshop. Engineering Optimization, 51(2), 185-198. https://doi.org/10.1080/0305215X.2018.1444163.

Nawaz, M., Enscore Junir, E. E., & Ham, I. (1983). A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega, 11(1), 91-95. https://doi.org/10.1016/0305-0483(83)90088-9.

Prata, B., Nagano, M. S., Fróes, N. J. M., & de Abreu, L. R. (2023). The seeds of the neh algorithm: An overview using bibliometric analysis. Operations Research Forum, 4(4), 98. https://doi.org/10.1007/s43069-023-00276-7.

Ruiz, R., & Stützle, T. (2007). A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. European Journal of Operational Research, 177(3), 2033-2049. https://doi.org/10.1016/j.ejor.2005.12.009.

Ruiz, R., Vallada, E., & Fernández-Martínez, C. (2009). Scheduling in flowshops with no-idle machines. In U.K. Chakraborty (Eds.), Computational intelligence in flow shop and job shop scheduling(pp. 21-51). Berlin: Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-642-02836-6_2.

Sanchez-de-los Reyes, P., Perez-Gonzalez, P., & Framinan, J. M. (2022). Permutation flowshop scheduling problem with total core idle time minimization. IFAC-PapersOnLine, 55(10), 187-191. https://doi.org/10.1016/j.ifacol.2022.09.388.

Sharma, M., Sharma, S., & Sharma, M. (2020). No-wait flowshop scheduling problem with bicriteria of idle time and makespan. InSoft Computing: Theories and Applications. Proceedings of SoCTA, 2018, 549-557.

Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2), 278-285. https://doi.org/10.1016/0377-2217(93)90182-M.

Tyagi, N., Varshney, R. G., & Chandramouli, A. B. (2013). Six decades of flowshop scheduling research. International Journal of Scientific and Engineering Research, 4(9), 854-864.

Vallada, E., Ruiz, R., & Framinan, J. M. (2015). New hard benchmark for flowshop scheduling problems minimising makespan. European Journal of Operational Research, 240(3), 666-677. https://doi.org/10.1016/j.ejor.2014.07.033.

Vallada, E., Ruiz, R., & Minella, G. (2008). Minimising total tardiness in the m-machine flowshop problem: A review and evaluation of heuristics and metaheuristics. Computers & Operations Research, 35(4), 1350-1373. https://doi.org/10.1016/j.cor.2006.08.016.

Yadav, A., & Agrawal, S. (2019). Minimize idle time in two sided assembly line balancing using exact search approach. In ACM International Conference Proceeding Series (pp. 220-227). New York: Association for Computing Machinery. https://doi.org/10.1145/3335550.3335591.

Ye, H., Li, W., & Abedini, A. (2017). An improved heuristic for no-wait flow shop to minimize makespan. Journal of Manufacturing Systems, 44, 273-279. https://doi.org/10.1016/j.jmsy.2017.04.007.

Yuan, J., Ng, C. T., & Cheng, T. C. E. (2020). Scheduling with release dates and preemption to minimize multiple max-form objective functions. European Journal of Operational Research, 280(3), 860-875. https://doi.org/10.1016/j.ejor.2019.07.072.

Submitted date:
03/16/2025

Accepted date:
11/30/2025

Optimising manufacturing schedules with tailored metrics to reduce unproductive times

Alex Abreu; Helio Yochihiro Fuchigami

Abstract

Keywords

References

Links

Share

Production