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.
References
[1]
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
[2]
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
[3]
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
[4]
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
[5]
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.
[6]
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
[7]
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
[8]
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
[9]
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
[10]
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.
[11]
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
![\"\"](\"Edit_41010f25-7ca5-482c-89be-790fad4616e1.png\")
