Parsamanesh, A., Sahraeian, R. (2015). Solving Single Machine Sequencing to Minimize Maximum Lateness Problem Using Mixed Integer Programming. Journal of Quality Engineering and Production Optimization, 1(1), 33-42. doi: 10.22070/jqepo.2015.187

Amir Hossein Parsamanesh; Rashed Sahraeian. "Solving Single Machine Sequencing to Minimize Maximum Lateness Problem Using Mixed Integer Programming". Journal of Quality Engineering and Production Optimization, 1, 1, 2015, 33-42. doi: 10.22070/jqepo.2015.187

Parsamanesh, A., Sahraeian, R. (2015). 'Solving Single Machine Sequencing to Minimize Maximum Lateness Problem Using Mixed Integer Programming', Journal of Quality Engineering and Production Optimization, 1(1), pp. 33-42. doi: 10.22070/jqepo.2015.187

Parsamanesh, A., Sahraeian, R. Solving Single Machine Sequencing to Minimize Maximum Lateness Problem Using Mixed Integer Programming. Journal of Quality Engineering and Production Optimization, 2015; 1(1): 33-42. doi: 10.22070/jqepo.2015.187

Solving Single Machine Sequencing to Minimize Maximum Lateness Problem Using Mixed Integer Programming

^{}Department of Industrial Engineering, University College of Engineering, Shahed University, Tehran, Iran

Abstract

Despite existing various integer programming for sequencing problems, there is not enough information about practical values of the models. This paper considers the problem of minimizing maximum lateness with release dates and presents four different mixed integer programming (MIP) models to solve this problem. These models have been formulated for the classical single machine problem, namely sequenceposition (SP), disjunctive (DJ), linear ordering (LO) and hybrid (HY). The main focus of this research is on studying the structural properties of minimizing maximum lateness in a single machine using MIP formulations. This comparison helps us know the characteristics and priority of different models in minimizing maximum lateness. Regarding to these characteristics and priorities, while solving the lateness problem in the procedure of solving a real-world problem, we apply the lateness model which yields in solution in shortest period of time and try not to use formulations which never lead to solution for large-scale problems. Beside single machine, these characteristics are applicable to more complicated machine environment. We generate a set of test problems in an attempt to solve the formulations, using CPLEX software. According to the computational results, a detailed comparison between proposed MIP formulations is reported and discussed in order to determine the best formulation which is computationally efficient and structurally parsimonious to solve the considering problem. Among the four presented formulations, sequence-position (SP) has the most efficient computational time to find the optimal solution.

1. Pinedo, M., & Hadavi, K. Scheduling: Theory, Algorithms and systems development, in operations research proceedings 1991, W. Gaul, et al., Editors. 1992, Springer Berlin Heidelberg. p. 35-42.

2. Wagner, H.M.( 1959). An integer linear-programming model for machine scheduling. Naval Research Logistics Quarterly, 6(2):p. 131-140.

3. Manne, A.S.( 1960). On the job-shop scheduling problem. Operations Research, 8(2) pp. 219--223.

4. Blazewicz, J., M. Dror, & Weglarz, J.( 1991). Mathematical programming formulations for machine scheduling: A survey.European Journal of Operational Research, 51(3) pp. 283-300.

5. Queyranne, M., & Schulz, A.S. Polyhedral approaches to machine scheduling.Technical report 408/1994. Department of

Mathematics, Technical University of Berlin, Berlin, Germany, 1994.

6. Unlu, Y. and Mason, S.J. ( 2010). Evaluation of mixed integer programming formulations for non-preemptive parallel machine scheduling problems.Computers & Industrial Engineering, 58(4) pp. 785-800.

7. Baker, K.R. & B. Keller. ( 2010). Solving the single-machine sequencing problem using integer programming. Computers & Industrial Engineering, 59(4) pp. 730-735.

8. Herr, O., and Goel, A. ( 2014). Comparison of two integer programming formulations for a single machine family scheduling problem to minimize total tardiness. Procedia CIRP, 19(0) pp. 174-179.

9. Bahalke, U., et al. ( 2010). Genetic and tabusearchalgorithmsforthesingle machinescheduling problemwith sequence-dependent set-uptimes and deteriorating jobs. International Journal of Engineering, 23 pp. 227-234

10. Sels, V. & Vanhoucke, M. ( 2012). A hybrid genetic algorithm for the single machine maximum lateness problem with release times and family setups. Computers & Operations Research, 39(10) pp. 2346-2358.

11. Lu, C.-C., Lin, S-W., and Ying ,K.-C. ( 2012). Robust scheduling on a single machine to minimize total flow time. Computers & Operations Research, 39(7) pp. 1682-1691.

12. Moghaddam, A., F. Yalaoui, L.& Amodeo. ( 2015). Efficient meta-heuristics based on various dominance criteria for a singlemachine bi-criteria scheduling problem with rejection. Journal of Manufacturing Systems, 34(0) pp. 12-22.

13. Senthilvel, A.N., Maheswari, S.U., and Hemamalini, T. (2014). Heuristic robust algorithm to optimize sequencing of jobs on a single machine. Procedia Materials Science, 5(0) p. 1473-1481.

14. Graham, R.L., et al.(1979). Optimization and approximation in deterministic sequencing and scheduling: a survey, in Annals of Discrete Mathematics, E.L.J. P.L. Hammer and B.H. Korte, Editors, Elsevier. p. 287-326.

15. Lenstra, J.K., Rinnooy Kan, A.H.G., and Brucker, P. (1977) . Complexity of machine scheduling problems, in Annals of Discrete Mathematics, E.L.J.B.H.K. P.L. Hammer and G.L. Nemhauser, Editors, Elsevier. p. 343-362.

16. Balas, E., On the facial structure of scheduling polyhedra, in Mathematical Programming Essays in Honor of George B. Dantzig Part I, R.W. Cottle, Editor. 1985, Springer Berlin Heidelberg, p. 179-218.

17. Queyranne, M., and Wang,Y. (1991). Single-machine scheduling polyhedra with precedence constraints. Math Operation Research, 16(1) p. 1-20.

18. Dyer, M.E. and Wolsey, L.A. ( 1990). Formulating the single machine sequencing problem with release dates as a mixed integer program. Discrete Applied Mathematics, 26(2–3) p. 255-270.