Logo PTI Logo FedCSIS

Position and Communication Papers of the 16th Conference on Computer Science and Intelligence Systems

Annals of Computer Science and Information Systems, Volume 26

Flexible job shop scheduling problem with sequence-dependent transportation constraints and setup times

, ,

DOI: http://dx.doi.org/10.15439/2021F14

Citation: Position and Communication Papers of the 16th Conference on Computer Science and Intelligence Systems, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 26, pages 97102 ()

Full text

Abstract. The study focuses on a variant of a flexible job shop scheduling problem. In addition to the usual constraints such as precedence of operations, time windows, delays, uniqueness of processing, availability of resources and waiting time, possible restrictions of robot movements according to production orders are added.  Thus, we consider additional sequence-dependent setup times as well as sequence-dependent transport and assignment restrictions. We propose a mixed integer programming (MIP) model. We solve it with a general MIP solver and analyze the impact of the instance size on the computation time. We consider real instances as well as randomly generated instances.


  1. J. Zhang, G. Ding, Y. Zou, S. Qin, and J. Fu, “Review of job shop scheduling research and its new perspectives under Industry 4.0,” Journal of Intelligent Manufacturing, vol. 30, no. 4, pp. 1809– 1830, Apr. 2019. http://dx.doi.org/10.1007/s10845-017-1350-2. [Online]. Available: https://doi.org/10.1007/s10845-017-1350-2
  2. 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, Sep. 2016. http://dx.doi.org/10.1016/j.cor.2016.04.006. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S0305054816300764
  3. S. Karimi, Z. Ardalan, B. Naderi, and M. Mohammadi, “Scheduling flexible job-shops with transportation times: Mathematical models and a hybrid imperialist competitive algorithm,” Applied Mathematical Modelling, vol. 41, pp. 667–682, Jan. 2017. http://dx.doi.org/10.1016/j.apm.2016.09.022. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S0307904X16304929
  4. M. Benttaleb, F. Hnaien, and F. Yalaoui, “Two-machine job shop problem under availability constraints on one machine: Makespan minimization,” Computers & Industrial Engineering, vol. 117, pp. 138– 151, Mar. 2018. http://dx.doi.org/10.1016/j.cie.2018.01.028. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S0360835218300354
  5. H. Krim, R. Benmansour, and D. Duvivier, “On the single machine scheduling problem with sequence-dependent setup times and periodic maintenance,” in 2018 5th International Conference on Con- trol, Decision and Information Technologies (CoDIT), Apr. 2018. http://dx.doi.org/10.1109/CoDIT.2018.8394827 pp. 374–378.
  6. S. A. Mansouri, E. Aktas, and U. Besikci, “Green scheduling of a two-machine flowshop: Trade-off between makespan and energy consumption,” European Journal of Operational Research, vol. 248, no. 3, pp. 772–788, Feb. 2016. http://dx.doi.org/10.1016/j.ejor.2015.08.064. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S0377221715008206
  7. S. Assia, E. A. Ikram, A. El Barkany, and E. Biyaali Ahmed, “Two-Machine Job Shop Scheduling Problem Under Availability Constraints on one machine: Total Energy Consumption (TEC) minimization,” 2018.
  8. L. Shen, S. Dauzère-Pérès, and J. S. Neufeld, “Solving the flexible job shop scheduling problem with sequence-dependent setup times,” European Journal of Operational Research, vol. 265, no. 2, pp. 503–516, Mar. 2018. http://dx.doi.org/10.1016/j.ejor.2017.08.021. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S037722171730752X
  9. J. Bezanson, A. Edelman, S. Karpinski, and V. B. Shah, “Julia: A Fresh Approach to Numerical Computing,” SIAM Review, vol. 59, no. 1, pp. 65–98, 2017. http://dx.doi.org/10.1137/141000671. [Online]. Available: http://julialang.org/publications/julia-fresh-approach-BEKS.pdf
  10. [Online]. Available: https://julialang.org/
  11. [Online]. Available: http://www.gurobi.com/