A Mixed Integer Linear Programming Model for Flexible Job Shop Scheduling Problem

Authors: Mohsen Ziaee

Abstract:

In this paper, a mixed integer linear programming (MILP) model is presented to solve the flexible job shop scheduling problem (FJSP). This problem is one of the hardest combinatorial problems. The objective considered is the minimization of the makespan. The computational results of the proposed MILP model were compared with those of the best known mathematical model in the literature in terms of the computational time. The results show that our model has better performance with respect to all the considered performance measures including relative percentage deviation (RPD) value, number of constraints, and total number of variables. By this improved mathematical model, larger FJS problems can be optimally solved in reasonable time, and therefore, the model would be a better tool for the performance evaluation of the approximation algorithms developed for the problem.

Keywords: Scheduling, flexible job shop, makespan, mixed integer linear programming.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1316788

References:

[1] A. S. Jain, S. Meeran, Deterministic job-shop scheduling: Past, present and future, European Journal of Operational Research 113 (2) (1999) 390–434.
[2] A.S. Jain, S. Meeran, A state-of-the-art review of job-shop scheduling techniques, Technical report, Department of Applied Physics, Electronic and Mechanical Engineering, University of Dundee: Dundee, UK (1998) 1–48.
[3] J. Blazewicz, W. Domschke, E. Pesch, The job shop scheduling problem: Conventional and new solution techniques, European Journal of Operational Research 93 (1996) 1–33.
[4] K. Baker, Introduction to sequencing and scheduling, NewYork: Wiley (1974).
[5] M. Pinedo, Scheduling: theory, algorithms and systems, Englewood cliffs, NJ: Prentice-Hall (2002).
[6] M. R. Garey, D. S. Johnson, R. Sethi, The complexity of flow shop and job-shop scheduling, Mathematics of Operations Research 1 (2) (1976) 117–129.
[7] T.-C. Chiang, H.-J. Lin, A simple and effective evolutionary algorithm for multiobjective flexible job shop scheduling, International Journal of Production Economics 141 (2013) 87–98.
[8] Y. Yuan, H. Xu, Flexible job shop scheduling using hybrid differential evolution algorithms, Computers & Industrial Engineering 65 (2013) 246–260.
[9] J.-Q. Li, Q.-K. Pan, M. F. Tasgetiren, A discrete artificial bee colony algorithm for the multi-objective flexible job-shop scheduling problem with maintenance activities, Applied Mathematical Modelling 38 (2013) 1111–1132.
[10] J.-q. Li, Q.-k. Pan, Chemical-reaction optimization for flexible job-shop scheduling problems with maintenance activity, Applied Soft Computing 12 (2012) 2896–2912.
[11] Y. Yuan, H. Xu, J. Yang, A hybrid harmony search algorithm for the flexible job shop scheduling problem, Applied Soft Computing 13 (2013) 3259–3272.
[12] Y. Unlu, S. J. Mason, Evaluation of mixed integer programming formulations for non-preemptive parallel machine scheduling problems, Computers and Industrical Engineering 58 (2010) 785–800.
[13] C. H. Pan, A study of integer programming formulations for scheduling problems, International Journal of Systems Science 28 (1) (1997) 33–41.
[14] C. Özgüven, L. Ozbakır, Y. Yavuz, Mathematical models for job-shop scheduling problems with routing and process plan flexibility, Applied Mathematical Modelling 34 (2010) 1539–1548.
[15] P. Fattahi, M. S. Mehrabad, F. Jolai, Mathematical modeling and heuristic approaches to flexible job shop scheduling problems, Journal of Intelligent Manufacturing 18 (2007) 331–342.
[16] Y. Demir, K. Isleyen, Evaluation of mathematical models for flexible job-shop scheduling problems, Applied mathematical modeling 37 (2013) 977–988.
[17] LINDO Systems Inc., LINGO User’s Guide, LINDO Systems Inc.: Chicago (1999).
[18] D. C. Montgomery, Design and analysis of experiments, Fifth ed., NewYork: John Wiley & Sons (2000).
[19] A. S. Manne, On the job-shop scheduling problem, Operations Research 8 (1960) 219–223.
[20] H. M. Wagner, An integer linear programming model for machine scheduling, Naval Research Logistics Quarterly 6 (1959) 131–140.
[21] E. H. Bowman, The scheduling sequence problem, Operations Research 7 (1959) 621–624.
[22] S. French, Sequencing and scheduling: an introduction to the mathematics of the job-shop, Chichester, UK: Ellis Horwood (1982).
[23] J. M. Wilson, Alternative formulations of a flow-shop scheduling problem, OR Journal (Journal of the Operational Research Society) 40(4) (1989) 395–9.
[24] C.-J. Liao, C.-T. You, Improved formulation for the job-shop scheduling problem, Journal of the Operational Research Society 43(11) (1992) 1047–54.
[25] G. L. Nemhauser, L. A. Wolsey, Integer and Combinatorial Optimization, John Wiley, New York (1988).
[26] Z. Zhu, R. B. Heady, Minimizing the sum of earliness/tardiness in multi-machine scheduling: a mixed integer programming approach, Computers & Industrial Engineering 38 (2000) 297–305.