MILP models and valid inequalities for the two-machine permutation flowshop scheduling problem with minimal time lags

Subject Areas : Mathematical Optimization

Imen Hamdi ¹ , Saïd Toumi ²

1 - MODILS Lab, Faculty of Economics and Management, University of Sfax, Sfax, Tunisia|High Institute of Transport and Logistics, University of Sousse, Sousse, Tunisia
2 - MODILS Lab, Faculty of Economics and Management, University of Sfax, Sfax, Tunisia|High Institute of Transport and Logistics, University of Sousse, Sousse, Tunisia|Department of Business Administration, College of Business Administartion, Majmaah University, Al Majmaah, Saudi Arabia

Received: 2020-10-09 Accepted : 2020-10-09 Published : 2020-06-01

Keywords:

References:

Chu C, Proth JM (1996) Single machine scheduling with chain structured precedence constraints and separation time windows. IEEE Trans Robot Autom 12(6):835–844
Dell’Amico M (1996) Shop problems with two machines and time lags. J Oper Res 44(5):777–787
Deppner F (2004) Ordonnancement d’atelier avec contraintes temporelles entre operations. Ph.D. Thesis, Institut National Polytechnique de Lorraine
Dhouib E, Teghem J, Moalla Loukil T (2013) Lexicographic optimization of a permutation fow shop scheduling problem with time lag constraints. Int Trans Oper Res 20(2):213–232
Fondrevelle J, Oulamara A, Portmann MC (2006) Permutation fowshop scheduling problems with maximal and minimal time lags. Comput Oper Res 33(6):1540–1556
Foulds LR, Wilson JM (2005) Scheduling operations for the harvesting of renewable resources. J Food Eng 70(3):281–292
Graham R, Lawler E, Lenstra JK, Rinnooy Kan AHG (1979) Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann Discrete Math 5:287–326
Hamdi I, Loukil T (2017) The permutation fowshop scheduling problem with exact time lags to minimize the total earliness and tardiness. Int J Oper Res 28(1):70–86
Hamdi I, Loukil T (2015a) Minimizing total tardiness in the permutation fowshop scheduling problem with minimal and maximal time lags. Oper Res Int J 15(1):95–114
Hamdi I, Loukil T (2015b) Upper and lower bounds for the permutation fowshop scheduling problem with minimal time lags. Optim Lett 9(3):465–482
Hamdi I, Oulamara A, Loukil T (2015) A branch and bound algorithm to minimize total tardiness in the two machine fowshop problem with minimal time lags. Int J Oper Res 23(4):387–405
Hamdi I, Loukil T (2011) Minimizing the makespan in the permutation fowshop problem with minimal and maximal time lags. In: Proceeding of the 2011 IEEE international conference of communications, computing and control applications (CCCA’11) 03-05 Mars 2011 a Hammamet, Tunisie

Huang JD, Liu1 JJ, Chen QX and Mao N (2013) Mixed integer fomulation to tardiness objectives in a fow shop with two batchesprocessing machines and release date. In: CIE43 proceedings, 16–18 October 2013, The University of Hong Kong
Keshavarz T, Salmasi N, Varmazyar M (2019) Flowshop sequencedependent group scheduling with minimisation of weighted earliness and tardiness. Eur J Ind Eng 13(1):54–80
Kharbeche M, Haouari M (2013) MIP models for minimizing total tardiness in a two-machine fow shop. J Oper Res Soc
64(5):690–707
Kim YD (1993) A new branch-and-bound algorithm for minimizing mean tardiness in two-machine fowshops. Comput Oper Res 20(4):391–401
Moreno-Camacho CA, Montoya-Torres JR, Vélez-Gallego MC (2018) A comparison of mixed-integer linear programming models for workforce scheduling with position-dependent processing times. Eng Optim 50(6):917–932
Pan JC-H, Fan ET (1997) Two-machine fowshop scheduling to minimize total tardiness. Int J Syst Sci 28(4):405–414
Pan JC-H, Chen J-S and Chao C-M (2002) Minimizing tardiness in a two-machine fowshop. Comput Oper Res 29(7):869–885

Ronconi DP, Birgin EG (2012) Mixed-integer programming models for fowshop scheduling problems minimizing the total earliness and tardiness. Just-in-Time Syst 23:91–105
Schaller J (2005) Note on minimizing total tardiness in a twomachine fowshop. Comput Oper Res 32(12):3273–3281
Yu W, Hoogeveen H, Lenstra JK (2004) Minimising makespan in a two machine fowshop with delays and unit time operations is NP-hard. J Sched 7(5):333–348