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: Flow shop, Total tardiness, Time lags, MILP models, Valid inequalities,

Abstract :

In this paper, we consider the problem of scheduling on two-machine permutation flowshop with minimal time lags between consecutive operations of each job. The aim is to find a feasible schedule that minimizes the total tardiness. This problem is known to be NP-hard in the strong sense. We propose two mixed-integer linear programming (MILP) models and two types of valid inequalities which aim to tighten the models’ representations. One of them is based on dominance rules from the literature. Then, we provide the results of extensive computational experiments used to measure the performance of the proposed MILP models. They are shown to be able to solve optimally instances until the size 40-job and even several larger problem classes, with up to 60 jobs. Furthermore, we can distinguish the effect of the minimal time lags and the inclusion of the valid inequalities in the basic MILP model on the results.

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