Logo PTI Logo FedCSIS

Communication Papers of the 19th Conference on Computer Science and Intelligence Systems (FedCSIS)

Annals of Computer Science and Information Systems, Volume 41

Job Shop Scheduling with Integer Programming, Shifting Bottleneck, and Decision Diagrams: A Computational Study

,

DOI: http://dx.doi.org/10.15439/2024F9975

Citation: Communication Papers of the 19th Conference on Computer Science and Intelligence Systems (FedCSIS), M. Bolanowski, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 41, pages 69–76 ()

Full text

Abstract. We study heuristic algorithms for job shop scheduling problems. We compare classical approaches, such as the shifting bottleneck heuristic with novel strategies using decision diagrams. Balas' local refinement is used to improve feasible solutions. Heuristic approaches are combined with Mixed Integer Programming and Constraint Programming approaches. We discuss our results via computational experiments.

References

  1. P. Martin and D. B. Shmoys, “A new approach to computing optimal schedules for the job-shop scheduling problem,” in Integer Programming and Combinatorial Optimization, W. H. Cunningham, S. T. McCormick, and M. Queyranne, Eds. Springer Berlin Heidelberg, 1996, vol. 1084, pp. 389–403. ISBN 978-3-540-61310-7 978-3-540-68453-4. [Online]. Available: http://link.springer.com/10.1007/3-540-61310-2_29
  2. Y. P. Gupta, M. C. Gupta, and C. R. Bector, “A review of scheduling rules in flexible manufacturing systems,” International Journal of Computer Integrated Manufacturing, vol. 2, no. 6, pp. 356–377, Nov. 1989. http://dx.doi.org/10.1080/09511928908944424. [Online]. Available: http://www.tandfonline.com/doi/abs/10.1080/09511928908944424
  3. S. S. Panwalkar and W. Iskander, “A Survey of Scheduling Rules,” Operations Research, vol. 25, no. 1, pp. 45–61, Feb. 1977. http://dx.doi.org/10.1287/opre.25.1.45
  4. A. Allahverdi, “The third comprehensive survey on scheduling problems with setup times/costs,” European Journal of Operational Research, vol. 246, no. 2, pp. 345–378, Oct. 2015. http://dx.doi.org/10.1016/j.ejor.2015.04.004. [Online]. Available: https://linkinghub.elsevier.com/retrieve/pii/S0377221715002763
  5. N. Grigoreva, “Worst-case analysis of an approximation algorithm for single machine scheduling problem,” in Proceedings of the 16th Conference on Computer Science and Intelligence Systems, ser. FedCSIS 2021. IEEE, Sep. 2021. http://dx.doi.org/10.15439/2021f66. ISSN 2300-5963
  6. E. Balas, “Machine Sequencing Via Disjunctive Graphs: An Implicit Enumeration Algorithm,” Operations Research, vol. 17, no. 6, pp. 941–957, Dec. 1969. http://dx.doi.org/10.1287/opre.17.6.941
  7. W.-Y. Ku and J. C. Beck, “Mixed integer programming models for job shop scheduling: A computational analysis,” Computers & Operations Research, vol. 73, pp. 165–173, 2016. http://dx.doi.org/10.1016/j.cor.2016.04.006
  8. G. Da Col and E. C. Teppan, “Industrial-size job shop scheduling with constraint programming,” Operations Research Perspectives, vol. 9, p. 100249, 2022. http://dx.doi.org/10.1016/j.orp.2022.100249
  9. B. Naderi, R. Ruiz, and V. Roshanaei, “Mixed-integer programming vs. constraint programming for shop scheduling problems: New results and outlook,” INFORMS Journal on Computing, vol. 35, no. 4, pp. 817–843, 2023. http://dx.doi.org/10.1287/ijoc.2023.1287
  10. C.-H. Pan, “A study of integer programming formulations for scheduling problems,” International Journal of Systems Science, vol. 28, no. 1, pp. 33–41, Jan. 1997. http://dx.doi.org/10.1080/00207729708929360. [Online]. Available: http://www.tandfonline.com/doi/abs/10.1080/00207729708929360
  11. D. Bergman, A. A. Cire, W.-J. Van Hoeve, and J. Hooker, Decision Diagrams for Optimization, ser. Artificial Intelligence: Foundations, Theory, and Algorithms. Springer International Publishing, 2016. ISBN 978-3-319-42847-5 978-3-319-42849-9. [Online]. Available: http://link.springer.com/10.1007/978-3-319-42849-9
  12. Michael L. Pinedo, Scheduling: Theory, Algorithms, and Systems. Springer International Publishing, 2022. ISBN 978-3-031-05920-9 978-3-031-05921-6. [Online]. Available: https://link.springer.com/10.1007/978-3-031-05921-6
  13. Gurobi Optimization, LLC, Gurobi Optimizer Reference Manual, 2023. [Online]. Available: https://www.gurobi.com
  14. IBM, IBM ILOG CPLEX Optimization Studio, 2023. [Online]. Available: https://www.ibm.com/products/ilog-cplex-optimization-studio
  15. J. N. Hooker, “Job Sequencing Bounds from Decision Diagrams,” in Principles and Practice of Constraint Programming, J. C. Beck, Ed. Springer International Publishing, 2017, vol. 10416, pp. 565– 578. ISBN 978-3-319-66157-5 978-3-319-66158-2. [Online]. Available: http://link.springer.com/10.1007/978-3-319-66158-2_36
  16. ——, “Improved Job Sequencing Bounds from Decision Diagrams,” in Principles and Practice of Constraint Programming, T. Schiex and S. De Givry, Eds. Springer International Publishing, 2019, vol. 11802, pp. 268–283. ISBN 978-3-030-30047-0 978-3-030-30048-7. [Online]. Available: http://link.springer.com/10.1007/978-3-030-30048-7_16
  17. D. Bergman, A. A. Cire, and W.-J. Van Hoeve, “Lagrangian bounds from decision diagrams,” Constraints, vol. 20, no. 3, pp. 346–361, Jul. 2015. http://dx.doi.org/10.1007/s10601-015-9193-y. [Online]. Available: http://link.springer.com/10.1007/s10601-015-9193-y
  18. P. Van Den Bogaerdt and M. De Weerdt, “Multimachine scheduling lower bounds using decision diagrams,” Operations Research Letters, vol. 46, no. 6, pp. 616–621, Nov. 2018. http://dx.doi.org/10.1016/j.orl.2018.11.003. [Online]. Available: https://linkinghub.elsevier.com/retrieve/pii/S016763771830227X
  19. ——, “Lower Bounds for Uniform Machine Scheduling Using Decision Diagrams,” in Integration of Constraint Programming, Artificial Intelligence, and Operations Research, L.-M. Rousseau and K. Stergiou, Eds. Springer International Publishing, 2019, vol. 11494, pp. 565–580. ISBN 978-3-030-19211-2 978-3-030-19212-9. [Online]. Available: http://link.springer.com/10.1007/978-3-030-19212-9_38
  20. M. P. Castro, A. A. Cire, and J. C. Beck, “Decision Diagrams for Discrete Optimization: A Survey of Recent Advances,” INFORMS Journal on Computing, vol. 34, no. 4, pp. 2271–2295, Jul. 2022. http://dx.doi.org/10.1287/ijoc.2022.1170
  21. X. Gillard, V. Coppé, P. Schaus, and A. A. Cire, “Improving the filtering of branch-and-bound mdd solver,” in Integration of Constraint Programming, Artificial Intelligence, and Operations Research, P. J. Stuckey, Ed. Cham: Springer International Publishing, 2021. doi: 10.1007/978-3-030-78230-6_15. ISBN 978-3-030-78230-6 pp. 231–247.
  22. J. Adams, E. Balas, and D. Zawack, “The Shifting Bottleneck Procedure for Job Shop Scheduling,” Management Science, vol. 34, no. 3, pp. 391–401, Mar. 1988. http://dx.doi.org/10.1287/mnsc.34.3.391
  23. Pablo Ariño, Job Shop Library. [Online]. Available: https://github.com/Pabloo22/job_shop_lib
  24. T. Yasumasa, JSPLIB-Benchmark instances for the job-shop scheduling problem. [Online]. Available: https://github.com/tamy0612/JSPLIB
  25. E. Balas, N. Simonetti, and A. Vazacopoulos, “Job shop scheduling with setup times, deadlines and precedence constraints,” Journal of Scheduling, vol. 11, no. 4, pp. 253–262, Aug. 2008. http://dx.doi.org/10.1007/s10951-008-0067-7. [Online]. Available: http://link.springer.com/10.1007/s10951-008-0067-7
  26. É. D. Taillard, “Parallel Taboo Search Techniques for the Job Shop Scheduling Problem,” ORSA Journal on Computing, vol. 6, no. 2, pp. 108–117, May 1994. http://dx.doi.org/10.1287/ijoc.6.2.108
  27. E. Nowicki and C. Smutnicki, “An Advanced Tabu Search Algorithm for the Job Shop Problem,” Journal of Scheduling, vol. 8, no. 2, pp. 145–159, Apr. 2005. http://dx.doi.org/10.1007/s10951-005-6364-5. [Online]. Available: http://link.springer.com/10.1007/s10951-005-6364-5
  28. J. Carlier, “The one-machine sequencing problem,” European Journal of Operational Research, vol. 11, no. 1, pp. 42–47, 1982.
  29. M. Sinai and T. Tamir, “Minimizing tardiness in a scheduling environment with jobs’ hierarchy,” in Proceedings of the 16th Conference on Computer Science and Intelligence Systems, ser. FedCSIS 2021. IEEE, Sep. 2021. http://dx.doi.org/10.15439/2021f36. ISSN 2300-5963
  30. M. Horn, J. Maschler, G. R. Raidl, and E. Rönnberg, “A*-based construction of decision diagrams for a prize-collecting scheduling problem,” Computers & Operations Research, vol. 126, p. 105125, 2021. http://dx.doi.org/10.1016/j.cor.2020.105125
  31. B. Jurisch, “Lower bounds for the job-shop scheduling problem on multi-purpose machines,” Discrete Applied Mathematics, vol. 58, no. 2, pp. 145–156, 1995. http://dx.doi.org/10.1016/0166-218X(93)E0124-H
  32. T. Achterberg and T. Berthold, “Hybrid branching,” Lecture Notes in Computer Science, p. 309–311, 2009. http://dx.doi.org/10.1007/978-3-642-01929-6_23
  33. T. Hadzic, J. N. Hooker, B. O’Sullivan, and P. Tiedemann, “Approximate Compilation of Constraints into Multivalued Decision Diagrams,” in Principles and Practice of Constraint Programming, P. J. Stuckey, Ed. Springer Berlin Heidelberg, 2008, vol. 5202, pp. 448–462. ISBN 978-3-540-85957-4 978-3-540-85958-1. [Online]. Available: http://link.springer.com/10.1007/978-3-540-85958-1_30