1. MMC
  2. All Volumes and Issues
  3. Volume 12, Number 4, 2025
  4. An Iterative Greedy Algorithm Involving a Q-Learning Mechanism for Solving the Permutation Flow Shop Scheduling Problem with Sequence-Dependent Setup Times

An Iterative Greedy Algorithm Involving a Q-Learning Mechanism for Solving the Permutation Flow Shop Scheduling Problem with Sequence-Dependent Setup Times

MMC.
2025;
Volume 12, Number 4
: pp. 1393–1405
https://doi.org/10.23939/mmc2025.04.1393
Received: May 08, 2025
Revised: December 08, 2025
Accepted: December 10, 2025

Mesmar K., Lebbar M., Allali K.  An Iterative Greedy Algorithm Involving a Q-Learning Mechanism for Solving the Permutation Flow Shop Scheduling Problem with Sequence-Dependent Setup Times.  Mathematical Modeling and Computing. Vol. 12, No. 4, pp. 1393–1405 (2025)

Authors:
  1. K. Mesmar
  2. M. Lebbar
  3. K. Allali
1
ROSDM Research Team, LISTD – Laboratory of Systems Engineering and Digital Transformation, ENSMR Rabat
2
ROSDM Research Team, LISTD – Laboratory of Systems Engineering and Digital Transformation, ENSMR Rabat
3
Laboratory of Mathematics, Computer Science and Applications, FST Mohammedia, Hassan II University

This paper proposes a novel hybrid framework, Q-IG, to solve the permutation flow shop scheduling problem with sequence-dependent setup times (PFSP-SDST).  Recent advancements in learning-based methods demonstrate significant potential in addressing flow shop scheduling, yet they often struggle with the enormous solution space and the design of effective reward functions.  To overcome these challenges, Q-IG integrates the iterated greedy metaheuristic (IG) with Q-learning.  It begins by applying the Nawaz–Enscore–Ham (NEH) heuristic to generate high-quality initial solutions.  During each IG iteration, the schedules are partially destroyed and reconstructed, and Q-learning is used to guide the selection of neighborhood moves that are expected to minimize makespan.  We evaluated both standalone IG and the Q-IG hybrid in the Taillard benchmark suite, measuring performance through a relative percentage deviation from the best-known makespan.  The results demonstrate that Q-IG outperforms its competitors, confirming its effectiveness for PFSP-SDST and highlighting the promise of incorporating Q-learning into traditional metaheuristic approaches.

iterated greedy
Q-learning; permutation flow shop scheduling (PFSP)
sequence-dependent setup times (SDST)
makespan
  1. Pinedo M., Hadavi K.  Scheduling: theory, algorithms and systems development.  Operations Research Proceedings 1991.  35–42 (1992).
  2. Lenstra J. K., Rinnooy Kan A. H. G.  Complexity of vehicle routing and scheduling problems.  Networks.  11 (2), 221–227 (1981).
  3. Luh P. B., Gou L., Zhang Y., Nagahora T., Tsuji M., Yoneda K., Hasegawa T., Kyoya Y., Kano T.  Job shop scheduling with group-dependent setups, finite buffers, and long time horizon.  Annals of Operations Research.  76, 233–259 (1998).
  4. Kim S. C., Bobrowski P. M.  Impact of sequence-dependent setup time on job shop scheduling performance.  The International Journal of Production Research.  32 (7), 1503–1520 (1994).
  5. Johnson S. M.  Optimal two-and three-stage production schedules with setup times included.  Naval Research Logistics Quarterly.  1 (1), 61–68 (1954).
  6. Corwin B. D., Esogbue A. O.  Two machine flow shop scheduling problems with sequence dependent setup times: A dynamic programming approach.  Naval Research Logistics Quarterly.  21 (3), 515–524 (1974).
  7. Gupta J. N. D.  Search algorithm for the generalized flowshop scheduling problem.  Computers & Operations Research.  2 (2), 83–90 (1975).
  8. Srikar B. N., Ghosh S.  A MILP model for the $n$-job, $M$-stage flowshop with sequence dependent set-up times.  International Journal of Production Research.  24, 1459–1474 (1986).
  9. Stafford E. F. Jr, Tseng F. T.  On the Srikar-Ghosh MILP model for the iVx M SDST flowshop problem.  International Journal of Production Research.  28 (10), 1817–1830 (1990).
  10. Ríos-Mercado R. Z., Bard J. F.  Computational experience with a branch-and-cut algorithm for flowshop scheduling with setups.  Computers & Operations Research.  25 (5), 351–366 (1998).
  11. Rios-Mercado R. Z., Bard J. F.  A branch-and-bound algorithm for permutation flow shops with sequence-dependent setup times.  IIE Transactions.  31 (8), 721–731 (1999).
  12. Garey M. R., Johnson D. S., Sethi R.  The Complexity of Flowshop and Jobshop Scheduling.  Mathematics of Operations Research.  1 (2), 117–129 (1976).
  13. Nawaz M., Enscore E. E. Jr., Ham I.  A heuristic algorithm for the $m$-machine, $n$-job flow-shop sequencing problem.  Omega.  11 (1), 91–95 (1983).
  14. Campbell H. G., Dudek R. A., Smith M. L.  A Heuristic Algorithm for the $n$ Job, $m$ Machine Sequencing Problem.  Management Science.  16 (10), B-579–B-697 (1970).
  15. Szwarc W., Gupta J. N. D.  A flow-shop problem with sequence-dependent additive setup times.  Naval Research Logistics (NRL).  34 (5), 619–627 (1987).
  16. Simons J. V. Jr.  Heuristics in flow shop scheduling with sequence dependent setup times.  Omega.  20 (2), 215–225 (1992).
  17. Das S. R., Gupta J. N. D., Khumawala B. M.  A savings index heuristic algorithm for flowshop scheduling with sequence dependent set-up times.  Journal of the Operational Research Society.  46 (11), 1365–1373 (1995).
  18. Ruiz R., Maroto C.  A comprehensive review and evaluation of permutation flowshop heuristics.  European Journal of Operational Research.  165 (2), 479–494 (2005).
  19. Osman I. H., Potts C. N.  Simulated annealing for permutation flow-shop scheduling.  Omega.  17 (6), 551–557 (1989).
  20. Widmer M., Hertz A.  A new heuristic method for the flow shop sequencing problem.  European Journal of Operational Research.  41 (2), 186–193 (1989).
  21. Reeves C. R.  A genetic algorithm for flowshop sequencing.  Computers & Operations Research.  22 (1), 5–13 (1995).
  22. Lei D.  A genetic algorithm for flexible job shop scheduling with fuzzy processing time.  International Journal of Production Research.  48 (10), 2995–3013 (2010).
  23. Engin O., Ceran G., Yilmaz M. K.  An efficient genetic algorithm for hybrid flow shop scheduling with multiprocessor task problems.  Applied Soft Computing.  11 (3), 3056–3065 (2011).
  24. Mirsanei H. S., Zandieh M., Moayed M. J., Khabbazi M. R.  A simulated annealing algorithm approach to hybrid flow shop scheduling with sequence-dependent setup times.  Journal of Intelligent Manufacturing.  22, 965–978 (2011).
  25. Defersha F. M., Obimuyiwa D., Yimer A. D.  Mathematical model and simulated annealing algorithm for setup operator constrained flexible job shop scheduling problem.  Computers & Industrial Engineering.  171, 108487 (2022).
  26. Qin H.-X., Han Y.-Y., Zhang B., Meng L.-L., Liu Y.-P., Pan Q.-K., Gong D.-W.  An improved iterated greedy algorithm for the energy-efficient blocking hybrid flow shop scheduling problem.  Swarm and Evolutionary Computation.  69, 100992 (2022).
  27. Han X., Han Y., Chen Q., Li J., Sang H., Liu Y., Pan Q., Nojima Y.  Distributed Flow Shop Scheduling with Sequence-Dependent Setup Times Using an Improved Iterated Greedy Algorithm.  Complex System Modeling and Simulation.  1 (3), 198–217 (2021).
  28. Chen X., Li J., Wang Z., Li J., Gao K.  A genetic programming based cooperative evolutionary algorithm for flexible job shop with crane transportation and setup times.  Applied Soft Computing.  169, 112614 (2024).
  29. Mou J., Duan P., Gao L., Liu X., Li J.  An effective hybrid collaborative algorithm for energy-efficient distributed permutation flow-shop inverse scheduling.  Future Generation Computer Systems.  128, 521–537 (2022).
  30. Sun K., Zheng D., Song H., Cheng Z., Lang X., Yuan W., Wang J.  Hybrid genetic algorithm with variable neighborhood search for flexible job shop scheduling problem in a machining system.  Expert Systems with Applications.  215, 119359 (2023).
  31. Wang L., Wang S., Zheng X.  A hybrid estimation of distribution algorithm for unrelated parallel machine scheduling with sequence-dependent setup times.  IEEE/CAA Journal of Automatica Sinica.  3 (3), 235–246 (2016).
  32. Li J.-Q., Du Y., Gao K.-Z., Duan P.-Y., Gong D.-W., Pan Q.-K., Suganthan P. N.  A hybrid iterated greedy algorithm for a crane transportation flexible job shop problem.  IEEE Transactions on Automation Science and Engineering.  19 (3), 2153–2170 (2021).
  33. Benkalai I., Rebaine D., Gagné C., Baptiste P.  Improving the migrating birds optimization metaheuristic for the permutation flow shop with sequence-dependent set-up times.  International Journal of Production Research.  55 (20), 6145–6157 (2017).
  34. Ríos-Mercado R. Z., Bard J. F.  Heuristics for the flow line problem with setup costs.  European Journal of Operational Research.  110 (1), 76–98 (1998).
  35. Shiue Y.-R., Lee K.-C., Su C.-T.  Real-time scheduling for a smart factory using a reinforcement learning approach.  Computers & Industrial Engineering.  125, 604–614 (2018).
  36. Marchesano M. G., Guizzi G., Santillo L. S., Vespoli S.  A Deep Reinforcement Learning approach for the throughput control of a Flow-Shop production system.  IFAC-PapersOnLine.  54 (1), 61–66 (2021).
  37. Yang Y., Qian B., Hu R., Zhang D.  Deep Reinforcement Learning Algorithm for Permutation Flow Shop Scheduling Problem.  Intelligent Computing Methodologies. 473–483 (2022).
  38. Li H., Gao K., Duan P., Li J.-Q., Zhang L.  An Improved Artificial Bee Colony Algorithm With Q-Learning for Solving Permutation Flow-Shop Scheduling Problems.  IEEE Transactions on Systems, Man, and Cybernetics: Systems.  53 (5), 2684–2693 (2022).
  39. Du Y., Li J., Li C., Duan P.  A Reinforcement Learning Approach for Flexible Job Shop Scheduling Problem With Crane Transportation and Setup Times.  IEEE Transactions on Neural Networks and Learning Systems.  35 (4), 5695–5709 (2022).
  40. Kool W., Van Hoof H., Welling M.  Attention, learn to solve routing problems!  Preprint ArXiv:1803.08475 (2018).
  41. Liu Z., Wang Y., Liang X., Ma Y., Feng Y., Cheng G., Liu Z.  A graph neural networks-based deep Q-learning approach for job shop scheduling problems in traffic management.  Information Sciences.  607, 1211–1223 (2022).
  42. Li J., Li J., Gao K., Duan P.  A hybrid graph-based imitation learning method for a realistic distributed hybrid flow shop with family setup time.  IEEE Transactions on Systems, Man, and Cybernetics: Systems.  54 (12), 7291–7304 (2024).
  43. Ruiz R., Stützle T.  A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem.  European Journal of Operational Research.  177 (3), 2033–2049 (2007).
  44. Kaelbling L. P., Littman M. L., Moore A. W.  Reinforcement learning: A survey.  Journal of Artificial Intelligence Research.  4, 237–285 (1996).
  45. Wauters T., Verbeeck K., De Causmaecker P., Vanden Berghe G.  Boosting Metaheuristic Search Using Reinforcement Learning.  Hybrid Metaheuristics. 433–452 (2013).
  46. Sutton R. S., Barto A. G.  Reinforcement learning: An introduction.  MIT Press Cambridge (1998).
  47. Watkins C.  Learning from delayed rewards.  King's College, Cambridge United Kingdom (1989).