Skip to main content
SpringerLink
Log in

A mixed integer linear programming modelling for the flexible cyclic jobshop problem

  • S.I.: Project Management and Scheduling 2018
  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

This paper addresses the Cyclic Jobshop Problem in a flexible context. The flexibility feature means that machines are able to perform several kinds of tasks. Hence, a solution of the scheduling problem does not only concern the starting times of the elementary tasks, but also the assignment of these tasks to a unique machine. The objective considered in this paper is the minimisation of the cycle time of a periodic schedule. We formulate the problem as a Mixed Integer Linear Problem and propose a Benders decomposition method along with a heuristic procedure to speed up the solving of large instances. It consists in reducing the number of machines available for each task. Results of numerical experiments on randomly generated instances show that the MILP modelling has trouble solving difficult instances, while our decomposition method is more efficient for solving such instances. Our heuristic procedure provides good estimates for difficult instances.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9

Similar content being viewed by others

References

  • Benders, J. F. (1962). Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik, 4(1), 238–252.

    Article  Google Scholar 

  • Błażewicz, J., Domschke, W., & Pesch, E. (1996). The job shop scheduling problem: Conventional and new solution techniques. European Journal of Operational Research, 93(1), 1–33.

    Article  Google Scholar 

  • Bożejko, W., Gnatowski, A., Klempous, R., Affenzeller, M., Beham, A. (2016). Cyclic scheduling of a robotic cell. In Cognitive Infocommunications (CogInfoCom), 2016 7th IEEE international conference on, IEEE, pp. 000379–000384.

  • Bożejko, W., Pempera, J., & Wodecki, M. (2017). A fine-grained parallel algorithm for the cyclic flexible job shop problem. Archives of Control Sciences, 27(2), 169–181.

    Article  Google Scholar 

  • Brucker, P., & Kampmeyer, T. (2008a). Cyclic job shop scheduling problems with blocking. Annals of Operations Research, 159(1), 161–181.

    Article  Google Scholar 

  • Brucker, P., & Kampmeyer, T. (2008b). A general model for cyclic machine scheduling problems. Discrete Applied Mathematics, 156(13), 2561–2572.

    Article  Google Scholar 

  • Brucker, P., Burke, E. K., & Groenemeyer, S. (2012). A mixed integer programming model for the cyclic job-shop problem with transportation. Discrete Applied Mathematics, 160(13–14), 1924–1935.

    Article  Google Scholar 

  • Carlier, J., & Chrétienne, P. (1988). Problèmes d’ordonnancement: modélisation, complexité, algorithmes. Paris: Masson.

    Google Scholar 

  • Chretienne, P., et al. (1991). The basic cyclic scheduling problem with deadlines. Discrete Applied Mathematics, 30(2–3), 109–123.

    Article  Google Scholar 

  • Dell’Amico, M., & Trubian, M. (1993). Applying tabu search to the job-shop scheduling problem. Annals of Operations Research, 41(3), 231–252.

    Article  Google Scholar 

  • Draper, D. L., Jonsson, A. K., Clements, D. P., Joslin, D. E. (1999). Cyclic scheduling. In IJCAI, Citeseer, pp. 1016–1021.

  • Elmi, A., & Topaloglu, S. (2017). Cyclic job shop robotic cell scheduling problem: Ant colony optimization. Computers & Industrial Engineering, 111, 417–432.

    Article  Google Scholar 

  • Fink, M., Rahhou, T. B., & Houssin, L. (2012). A new procedure for the cyclic job shop problem. IFAC Proceedings Volumes, 45(6), 69–74.

    Article  Google Scholar 

  • Gao, J., Sun, L., & Gen, M. (2008). A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems. Computers & Operations Research, 35(9), 2892–2907.

    Article  Google Scholar 

  • Garey, M., & Johnson, D. (1979). Computers and intractability. New York: WII Freeman and Company.

  • Gomes, M., Barbosa-Povoa, A., & Novais, A. (2005). Optimal scheduling for flexible job shop operation. International Journal of Production Research, 43(11), 2323–2353.

  • Hamaz, I., Houssin, L., & Cafieri, S. (2018a). A robust basic cyclic scheduling problem. EURO Journal on Computational Optimization, 6(3), 291–313.

    Article  Google Scholar 

  • Hamaz, I., Houssin, L., & Cafieri, S. (2018b). The Cyclic Job Shop Problem with uncertain processing times. In 16th International conference on project management and scheduling (PMS 2018), Rome, Italy.

  • Hanen, C. (1994). Study of a NP-hard cyclic scheduling problem: The recurrent job-shop. European Journal of Operational Research, 72(1), 82–101.

    Article  Google Scholar 

  • Hanen, C., & Munier, A. (1995). A study of the cyclic scheduling problem on parallel processors. Discrete Applied Mathematics, 57(2–3), 167–192.

    Article  Google Scholar 

  • Hillion, H. P., & Proth, J. M. (1989). Performance evaluation of job-shop systems using timed event-graphs. IEEE Transactions on Automatic Control, 34(1), 3–9.

    Article  Google Scholar 

  • Houssin, L. (2011). Cyclic jobshop problem and (max, plus) algebra. In World IFAC Congress (IFAC 2011), pp. 2717–2721.

    Article  Google Scholar 

  • Ioachim, I., & Soumis, F. (1995). Schedule efficiency in a robotic production cell. International Journal of Flexible Manufacturing Systems, 7(1), 5–26.

    Article  Google Scholar 

  • Jalilvand-Nejad, A., & Fattahi, P. (2015). A mathematical model and genetic algorithm to cyclic flexible job shop scheduling problem. Journal of Intelligent Manufacturing, 26(6), 1085–1098.

    Article  Google Scholar 

  • Jamili, A., Shafia, M. A., & Tavakkoli-Moghaddam, R. (2011). A hybrid algorithm based on particle swarm optimization and simulated annealing for a periodic job shop scheduling problem. The International Journal of Advanced Manufacturing Technology, 54(1–4), 309–322.

    Article  Google Scholar 

  • Kampmeyer, T. (2006). Cyclic scheduling problems.

  • Karp, R. M., & Orlin, J. B. (1981). Parametric shortest path algorithms with an application to cyclic staffing. Discrete Applied Mathematics, 3(1), 37–45.

    Article  Google Scholar 

  • Kats, V., & Levner, E. (1996). Polynomial algorithms for scheduling of robots. Intelligent Scheduling of Robots and FMS, pp. 77–100.

  • Kim, H. J., Lee, J. H. (2018). Cyclic robot scheduling for 3D printer-based flexible assembly systems. Annals of Operations Research, pp. 1–21.

  • Korbaa, O., Camus, H., & Gentina, J. C. (2002). A new cyclic scheduling algorithm for flexible manufacturing systems. International Journal of Flexible Manufacturing Systems, 14(2), 173–187.

    Article  Google Scholar 

  • Levner, E., & Kats, V. (1998). A parametric critical path problem and an application for cyclic scheduling. Discrete Applied Mathematics, 87(1–3), 149–158.

    Article  Google Scholar 

  • Magnanti, T. L., & Wong, R. T. (1981). Accelerating benders decomposition: Algorithmic enhancement and model selection criteria. Operations research, 29(3), 464–484.

    Article  Google Scholar 

  • Papadakos, N. (2008). Practical enhancements to the Magnanti–Wong method. Operations Research Letters, 36(4), 444–449.

    Article  Google Scholar 

  • Quinton, F., Hamaz, I., & Houssin, L. (2018). Algorithms for the flexible cyclic jobshop problem. In 14th IEEE international conference on automation science and engineering, CASE 2018, Munich, Germany, August 20–24, 2018, pp. 945–950.

  • Rossi, A., & Dini, G. (2007). Flexible job-shop scheduling with routing flexibility and separable setup times using ant colony optimisation method. Robotics and Computer-Integrated Manufacturing, 23(5), 503–516.

    Article  Google Scholar 

  • Roundy, R. (1992). Cyclic schedules for job shops with identical jobs. Mathematics of Operations Research, 17(4), 842–865.

    Article  Google Scholar 

  • Saidi-Mehrabad, M., & Fattahi, P. (2007). Flexible job shop scheduling with tabu search algorithms. The International Journal of Advanced Manufacturing Technology, 32(5–6), 563–570.

    Article  Google Scholar 

  • Schutten, J. M. (1998). Practical job shop scheduling. Annals of Operations Research, 83, 161–178.

    Article  Google Scholar 

  • Serafini, P., & Ukovich, W. (1989). A mathematical model for periodic scheduling problems. SIAM Journal on Discrete Mathematics, 2(4), 550–581.

    Article  Google Scholar 

  • Song, J. S., & Lee, T. E. (1998). Petri net modeling and scheduling for cyclic job shops with blocking. Computers & Industrial Engineering, 34(2), 281–295.

    Article  Google Scholar 

  • Thomalla, C. S. (2001). Job shop scheduling with alternative process plans. International Journal of Production Economics, 74(1), 125–134.

    Article  Google Scholar 

  • Xia, W., & Wu, Z. (2005). An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems. Computers & Industrial Engineering, 48(2), 409–425.

    Article  Google Scholar 

  • Zhang, H., Collart-Dutilleul, S., & Mesghouni, K. (2015). Cyclic scheduling of flexible job-shop with time window constraints and resource capacity constraints. IFAC-PapersOnLine, 48(3), 816–821.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. LAAS-CNRS, Université de Toulouse, CNRS, UPS, Toulouse, France

    Félix Quinton & Laurent Houssin

  2. LIRMM UMR 5506, Université de Montpellier, 34932, Montpelier Cedex 5, France

    Idir Hamaz

Authors
  1. Félix Quinton
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Idir Hamaz
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Laurent Houssin
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Laurent Houssin.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Quinton, F., Hamaz, I. & Houssin, L. A mixed integer linear programming modelling for the flexible cyclic jobshop problem. Ann Oper Res 285, 335–352 (2020). https://doi.org/10.1007/s10479-019-03387-9

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10479-019-03387-9

Keywords

Search

Navigation