Research ArticleOpen AccessGoogle Scholar indexed
Identical Machine Scheduling Problem with Sequence-Dependent Setup Times: MILP Formulations Computational Study
Chaire Connected Innovation, ICD-LOSI, Université de Technologie de Troyes, Troyes, France
Chaire Connected Innovation, ICD-LOSI, Université de Technologie de Troyes, Troyes, France
- 1 Chaire Connected Innovation, ICD-LOSI, Université de Technologie de Troyes, Troyes, France
- 2 Chaire Connected Innovation, ICD-LOSI, Université de Technologie de Troyes, Troyes, France
American Journal of Operations Research·Volume 11 (2021)·Pages 15–34·Published 13 January 2021·DOI10.4236/ajor.2021.111002
Copy link · social · email
Abstract
This work aims to give a systematic construction of the two families of mixed-integer-linear-programming (MILP) formulations, which are graph- based and sequence-based, of the well-known scheduling problem . Two upper bounds of job completion times are introduced. A numerical test result analysis is conducted with a two-fold objective 1) testing the performance of each solving methods, and 2) identifying and analyzing the tractability of an instance according to the instance structure in terms of the number of machines, of the jobs setup time lengths and of the jobs release date distribution over the scheduling horizon.
KeywordsIdentical Machine Scheduling ProblemRelease DateSequence Dependent Setup Time
- Graham, R.L., Lawler, E.L., Lenstra, J.K. and Kan, A.R. (1979) Optimization and Approximation in Deterministic Sequencing and Scheduling: A Survey. Annals of Discrete Mathematics, 5, 287-326. https://doi.org/10.1016/S0167-5060(08)70356-X
- Allahverdi, A. (2015) The Third Comprehensive Survey on Scheduling Problems with Setup Times/Costs. European Journal of Operational Research, 246, 345-378. https://doi.org/10.1016/j.ejor.2015.04.004
- Guinet, A. (1993) Scheduling Sequence-Dependent Jobs on Identical Parallel Machines to Minimize Completion Time Criteria. The International Journal of Production Research, 31, 1579-1594. https://doi.org/10.1080/00207549308956810
- Nessah, R., Chu, C. and Yalaoui, F. (2007) An Exact Method for Problem. Computers & Operations Research, 34, 2840-2848. https://doi.org/10.1016/j.cor.2005.10.017
- Fowler, J.W., Horng, S.M. and Cochran, J.K. (2003) A Hybridized Genetic Algorithm to Solve Parallel Machine Scheduling Problems with Sequence Dependent Setups. International Journal of Industrial Engineering: Theory Applications and Practice, 10, 232-243.
- Montoya-Torres, J.R., Soto-Ferrari, M., Gonzalez-Solano, F. and Alfonso-Lizarazo, E.H. (2009) Machine Scheduling with Sequence-Dependent Setup Times Using a Randomized Search Heuristic. 2009 International Conference on Computers & Industrial Engineering, Troyes, 6-9 July 2009, 28-33. https://doi.org/10.1109/ICCIE.2009.5223742
- Lin, S.-W., Lee, Z.-J., Ying, K.-C. and Lu, C.-C. (2011) Minimization of Maximum Lateness on Parallel Machines with Sequence-Dependent Setup Times and Job Release Dates. Computers & Operations Research, 38, 809-815. https://doi.org/10.1016/j.cor.2010.09.020
- Kurz, M. and Askin, R. (2001) Heuristic Scheduling of Parallel Machines with Sequence-Dependent Set-Up Times. International Journal of Production Research, 39, 3747-3769. https://doi.org/10.1080/00207540110064938
- Anderson, B.E., Blocher, J.D., Bretthauer, K.M. and Venkataramanan, M.A. (2013) An Efficient Network-Based Formulation for Sequence Dependent Setup Scheduling on Parallel Identical Machines. Mathematical and Computer Modelling, 57, 483-493. https://doi.org/10.1016/j.mcm.2012.06.029
- Nogueira, T.H., De Carvalho, C. and Ravetti, M.G. (2014) Analysis of Mixed Integer Programming Formulations for Single Machine Scheduling Problems with Sequence Dependent Setup Times and Release Dates. Optimization Online, 39.
- Yalaoui, F. and Chu, C. (2002) Parallel Machine Scheduling to Minimize Total Tardiness. International Journal of Production Economics, 76, 265-279. https://doi.org/10.1016/S0925-5273(01)00175-X