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

Hamdi, Imen; Toumi, Saïd A icle MILP models and alid inequali ies o he wo-machine pe mu a ion lowshop scheduling p oblem wi h minimal ime lags Jou nal o Indus ial Enginee ing In e na ional P o ided in Coope a ion wi h: Islamic Azad Uni e si y (IAU), Teh an Sugges ed Ci a ion: Hamdi, Imen; Toumi, Saïd (2019) : MILP models and alid inequali ies o he wo-machine pe mu a ion lowshop scheduling p oblem wi h minimal ime lags, Jou nal o Indus ial Enginee ing In e na ional, ISSN 2251-712X, Sp inge , Heidelbe g, Vol. 15, Iss. S1, pp. 223-229, h ps://doi.o g/10.1007/s40092-019-00331-1 This Ve sion is a ailable a : h ps://hdl.handle.ne /10419/267664 S anda d-Nu zungsbedingungen: Die Dokumen e au EconS o dü en zu eigenen wissenscha lichen Zwecken und zum P i a geb auch gespeiche und kopie we den. Sie dü en die Dokumen e nich ü ö en liche ode komme zielle Zwecke e iel äl igen, ö en lich auss ellen, ö en lich zugänglich machen, e eiben ode ande wei ig nu zen. So e n die Ve asse die Dokumen e un e Open-Con en -Lizenzen (insbesonde e CC-Lizenzen) zu Ve ügung ges ell haben soll en, gel en abweichend on diesen Nu zungsbedingungen die in de do genann en Lizenz gewäh en Nu zungs ech e. Te ms o use: Documen s in EconS o may be sa ed and copied o you pe sonal and schola ly pu poses. You a e no o copy documen s o public o comme cial pu poses, o exhibi he documen s publicly, o make hem publicly a ailable on he in e ne , o o dis ibu e o o he wise use he documen s in public. I he documen s ha e been made a ailable unde an Open Con en Licence (especially C ea i e Commons Licences), you may exe cise u he usage igh s as speci ied in he indica ed licence. h ps://c ea i ecommons.o g/licenses/by/4.0/ Vol.:(0123456789) 1 3 Jou nal o Indus ial Enginee ing In e na ional (2019) 15 (Suppl 1):S223–S229 h ps://doi.o g/10.1007/s40092-019-00331-1 ORIGINAL RESEARCH MILP models and alid inequali ies o  he wo‑machine pe mu a ion lowshop scheduling p oblem wi hminimal ime lags ImenHamdi1,2· SaïdToumi1,2,3 Recei ed: 10 May 2019 / Accep ed: 10 Oc obe 2019 / Published online: 22 Oc obe 2019 © The Au ho (s) 2019 Abs ac In his pape , we conside he p oblem o scheduling on wo-machine pe mu a ion lowshop wi h minimal ime lags be ween consecu i e ope a ions o each job. The aim is o ind a easible schedule ha minimizes he o al a diness. This p oblem is known o be NP-ha d in he s ong sense. We p opose wo mixed-in ege linea p og amming (MILP) models and wo ypes o alid inequali ies which aim o igh en he models’ ep esen a ions. One o hem is based on dominance ules om he li e a u e. Then, we p o ide he esul s o ex ensi e compu a ional expe imen s used o measu e he pe o mance o he p oposed MILP models. They a e shown o be able o sol e op imally ins ances un il he size 40-job and e en se e al la ge p oblem classes, wi h up o 60 jobs. Fu he mo e, we can dis inguish he e ec o he minimal ime lags and he inclusion o he alid inequali ies in he basic MILP model on he esul s. Keywo ds Flowshop· To al a diness· Time lags· MILP models· Valid inequali ies In oduc ion This pape add esses he wo-machine pe mu a ion lowshop scheduling p oblem wi h minimal ime lags whe e he objec- i e is minimizing he o al a diness. This en i onmen is cha ac e ized by n jobs ( i∈{1, …,n}) being p ocessed non- p eemp i ely on wo machines M1 and M2 in his o de acco ding o a p ocessing ime ai on M1 and bi on M2. Fo each job, an amoun o ime mus be elapsed be o e he p o- cessing o he second ope a ion on he second machine. This ime mus be g ea e han o equal o a non-nega i e minimal ime lag alue deno ed 𝜃min i . Each job has a due da e di . Acco ding o he s anda d no a ion p o ided by G aham e  al. (1979), he conside ed p oblem is deno ed as F 2 � 𝜃 min i �∑ i T i . In es iga ing his p oblem is mo i a ed by i s p ac ical ele ance o he p oduc ion en i onmen s. The ime lags cons ain s a e used equen ly in bo h se ice and indus- ial ields. Fo example in he chemis y ield, he chemical eac ions wi h di e en p ocessing imes may be ep esen ed by ime lags (Chu and P o h 1996). Also, such cons ain s appea du ing he sequence o ha es ing ope a ions in he ag icul u e ield (Foulds and Wilson 2005). As well as in a aining cen e o which he sequence o modules augh mus equi e some empo al cons ain s. Many o he eal examples a e gi en by Deppne (2004). Since he publica ion o Dell’Amico (1996) o his o igi- nal pape on he wo-machine lowshop and jobshop wi h ime lags, his p oblem has a ac ed an e e -g owing a en- ion in he ope a ions esea ch ield. Then, his s udy was ex ended o conside a ious p oblems wi h ime lags while op imizing di e en c i e ia. I is wo h no ing ha he g ea majo i y o he esea ches add ess he makespan objec i e (Fond e elle e al. 2006; Yu e al. 2004; Hamdi and Loukil 2011) in spi e ha he due da e-based c i e ia a e he mos me in he eal si ua ions. In e es ingly, hese c i e ia and mainly he o al a di- ness c i e ion is conside ed widely wi h he classical wo- machine lowshop p oblem whe e mos o he esea ches a e * Imen Hamdi [email p o ec ed] Saïd Toumi [email p o ec ed] 1 MODILS Lab, Facul y o Economics andManagemen , Uni e si y o S ax, S ax, Tunisia 2 High Ins i u e o T anspo andLogis ics, Uni e si y o Sousse, Sousse, Tunisia 3 Depa men o Business Adminis a ion, College o Business Adminis a ion, Majmaah Uni e si y, AlMajmaah, SaudiA abia S224 Jou nal o Indus ial Enginee ing In e na ional (2019) 15 (Suppl 1):S223–S229 1 3 cha ac e ized by applying he b anch and bound algo i hm accompanied by p oposing and imp o ing lowe bounds and dominance p ope ies (Kim 1993; Pan and Fan 1997; Pan e al. 2002; Schalle 2005). Howe e , only ew esea ches conside ed he ime lags. Yu e al. (2004) show he NP ha dness o he p oblem e en i all p ocessing imes a e equal o one. La e , Hamdi e al. (2015) de eloped a b anch and bound algo i hm o each an op imal solu ion by using some de eloped lowe bounds and dominance c i e ia. These la e a e de eloped o es ablish p ecedence cons ain s be ween jobs in an op imal sched- ule. Some o hem will be used la e in his esea ch. Also, hey p oposed some compu a ionally e icien heu is ics. Nea ly a he same ime, Hamdi and Loukil (2015b) ex end he esea ch abou he pe mu a ion lowshop p oblem wi h minimal ime lags by conside ing he case o m-machine and op imizing he o al numbe o a dy jobs c i e ion. They p oposed some heu is ic p ocedu es based on known and new ules. Then in e es ingly, hey de eloped lowe bounds based on Moo e’s algo i hm and logic-based Bend- e s decomposi ion as a hyb id app oach ha mix he MILP and he cons ain p og amming. I is known ha he MILP models can be used o ob ain op imal schedules o small size p oblems. They a e o en classi ied based on he choice o he decision a iables. O e he li e a u e, a wide a ie y o pe mu a ion lowshop schedul- ing p oblems we e add essed while using he due da e-based c i e ia. Kha beche and Haoua i (2013) p oposed compac mixed-in ege p og amming models and alid inequali ies o he wo-machine scheduling p oblem. They de eloped a lowe bound ha consis en ly ou pe o ms he bes bound om he li e a u e. Then, hei compu a ional s udy e eals ha mos o he 30-job ha d ins ances a e op imally sol ed using hei p oposed MILP models. Also, Ronconi and Bi gin (2012) p o- posed mixed-in ege linea p og amming o mula ions o he m-machine scheduling p oblem in he lowshop en i onmen wi h unlimi ed and ze o bu e , o he minimiza ion o o al ea liness and a diness. E en wi h he exis ence o o he ypes o he ime lags like he maximal ime lags (deno ed 𝜃max i,k in he case o m-machine o indica e he maximal ime lag o he job i be ween he wo machines k and k+1 ) and he exac ime lags (deno ed 𝜃i,k ), he linea p og amming me hod was he scope o nume ous pape s. Hamdi and Loukil (2015a) p oposed a ma hema ical o mula ion o he p oblem F 𝜋 � 𝜃 min i,k,𝜃 max i,k �∑ i T i which was use- ul o dis inguish he e ec o he ime lags on he esul s. Mo eo e , i was used o e alua e he pe o mance o some p oposed heu is ic me hods by de e mining he pe cen age de ia ion om he op imal solu ion p o ided by unning he p oposed MILP wi h he CPLEX sol e . In he same con ex , Dhouib e al. (2013) p oposed a mixed-in ege ma hema ical p og amming o mula ion o he pe mu a ion lowshop p oblem wi h minimal and maximal ime lags while he objec- i e is o hie a chically minimize wo c i e ia, he p ima y c i e ion is he minimiza ion o he numbe o a dy jobs and he seconda y one minimizes he makespan. I is hen used o sol e op imally p oblems un il he size 20-jobs and 5-machine and o compa ison eason wi h a p oposed simula ed anneal- ing algo i hm. La e , Hamdi and Loukil (2017) p oposed h ee di e en MILP models o sol e he p oblem F 𝜋 � 𝜃i,k �∑ i (Ei+Ti ) which show ha he e is a li le di e ence be ween hem when e e ing o he CPU ime in spi e ha he numbe o decision a iables is almos he same o all he o mula ions. The ea - e , he ob ained op imal solu ion is used o e alua e he pe - o mance o some p oposed uppe and lowe bounds un il he size 20-job and 5-machine. I is wo h men ioning ha he MILP models a e used equen ly by he ecen esea ches ha conce ned by sol - ing scheduling p oblems wi h due da e-based c i e ia (i.e., Mo eno-Camacho e al. 2018; Huang e al. 2013; Kesha a z e al. 2019). The con ibu ion o his pape is wo old: Fi s , we p opose wo ma hema ical o mula ions dis inguished by he used decision a iables which a e: he comple ion ime a iables and he idle ime a iables. Second, we p esen wo se s o alid inequali ies ha can be used o imp o e he p oposed MILP esolu ion as he CPU ime equi ed o sol e he p ob- lem can be signi ican ly educed. To his aim, we exploi some dominance ules om he li e a u e o he i s se , and we p opose a lowe bound on he comple ion ime o he second se . Then, hese se s a e in oduced sepa a ely and oge he o he comple ion ime-based o mula ion o dis inguish hei e ec on he esolu ion pe o mance. Thus, a o al o i e MILP o mula ions a e compu a ionally compa ed by using he CPLEX sol e . To he bes o ou knowledge, his is he i s a emp o in es iga e MILP models o F 2 � 𝜃 min i �∑ i T i . The emainde o his pape is o ganized as ollows: ma hema ical o mula ions o he conside ed p oblem a e p esen ed in “MILP models2” sec ion. In “Valid inequali- ies3” sec ion, we p esen he wo ypes o alid inequali- ies: alid inequali ies based on dominance ules om he li e a u e, and posi ion-based alid inequali ies. Then, com- pu a ional esul s a e epo ed in “Compu a ional esul s4” sec ion. Finally, we discuss concluding ema ks in “Conclu- sion5” sec ion. MILP models This sec ion lis s wo MILP o mula ions: he comple ion ime-based o mula ion and he idle ime-based o mula ion, espec i ely. The conside ed p oblem is cha ac e ized by n jobs being p ocessed on 2 machines always in he same o de while a minimal ime lag 𝜃min i is de ined be ween each couple S225Jou nal o Indus ial Enginee ing In e na ional (2019) 15 (Suppl 1):S223–S229 1 3 o ope a ions o each job i. Each machine ca ies only one job a a ime, we assume ha all jobs a e independen and a ailable o p ocessing a ime 0, and p eemp ions a e no allowed . A common ea u e o bo h o mula ions is ha hey a e based on he posi ional decision a iables. Tha is, he esolu- ion o he p oblem consis s in assigning each job o only one posi ion in he schedule ha leads o he op imal alue o he o al a diness. Comple ion ime‑based o mula ion This o mula ion is based on he ollowing decision a iables: • Xi , j∶ bina y a iable ha akes alue 1 i job i is scheduled in posi ion j, 0 o he wise ∀i,j∈{1, 2, …,n} • Cj , k : comple ion ime o job in posi ion j on machine k, ∀j∈{1, 2, …,n},∀k∈{1, 2} • Tj : a diness o he job in posi ion j∀j∈{1, 2, …,n} The used da a a e gi en as ollows: • ai : p ocessing ime o job i on machine 1, ∀i∈{1, 2, …,n} • bi : p ocessing ime o job i on machine 2, ∀i∈{1, 2, …,n} • 𝜃min i : minimal ime lag be ween he wo machines o each job i∀i∈{1, 2, …,n} Then he MILP o mula ion is p esen ed as ollows (1) Minimize ∑ j T j (2) n ∑ i=1 Xi,j=1∀j=1, …, n (3) n ∑ j= 1 Xi,j=1∀i=1, …, n (4) C 1,1 = n ∑ i=1 Xi,1a i (5) C j,1 + n ∑ i=1 (Xi,j+1ai)≤Cj+1,1 ∀j=1, …,n− 1 (6) C j,2 ≥Cj,1 + n ∑ i=1 Xi,j(bi+𝜃min i)∀j=1, …, n (7) C j,2 + n ∑ i=1 (Xi,j+1bi)≤Cj+1,2 ∀j=1, …,n− 1 The objec i e (1) is o minimize he o al a diness. Con- s ain s (2) ensu e ha each posi ion can be occupied by only one job; howe e cons ain s (3) ensu e ha each job can only be assigned o a sequence posi ion. Cons ain s (4) de e mine he compe i ion ime o he job in he i s posi ion on he i s machine. Cons ain s (5) ind he comple ion ime o he o he jobs on he i s machine. Cons ain s (6) ind he comple ion ime o each job wi h espec o he minimal ime lags be ween ope a ions and he p ecedence cons ain s. Cons ain s (7) de ine he p ecedence cons ain o each wo successi e posi ions in he second machine. Cons ain s (8) ind he a diness alue o each job. Cons ain s (9) impose he a diness and he comple ion ime o be posi i e alues. Then, cons ain s (10) de ine Xi , j as a bina y a iable which is equal o 1 i he job i is assigned o posi ion j and 0 else. In his o mula ion, he numbe o bina y a iables is n2 , he numbe o in ege a iables is 3n, and he numbe o cons ain s is 9n−1 . Idle ime‑based o mula ion This o mula ion is based on he same da a and a iables de ined in he p e ious o mula ion, jus we use he a iable Ij ins ead o Cj , k ; i ep esen s he idle ime on machine 2 be ween he comple ion ime o he job in posi ion j and he s a ing ime o he job in posi ion j+1 . Then, he o mula- ion is p esen ed as ollows. (8) T j−Cj,2 + n ∑ i=1 (diXi,j)≥0∀j=1, …, n (9) Cj , k,Tj ≥ 0∀j=1, …,n,∀k=1, 2 (10) Xi,j ∈{ 0, 1 }∀ i,j = 1, … ., n (11) Minimize ∑ j T j (12) n ∑ i=1 Xi,j=1∀j=1, …, n (13) n ∑ j= 1 Xi,j=1∀i=1, …, n (14) j−1 ∑ k =1 n ∑ i=1 (bi+𝜃min i)Xi,k− j ∑ k=2 n ∑ i=1 (ai+𝜃min i)Xi, k + j ∑ k=2 Ik≥0∀j=2, …,n S226 Jou nal o Indus ial Enginee ing In e na ional (2019) 15 (Suppl 1):S223–S229 1 3 The objec i e (11) and he i s wo cons ain s (12) and (13) a e de ined as same in he p e ious MILP model. Cons ain s (14) s a e ha he idle ime o he job in posi ion j is g ea e han o equal o he comple ion ime o he job in posi ion j on he i s machine minus he comple ion ime o he job in posi ion ( j−1 ) on he second machine. Cons ain s (15) and (16) de e mine he a diness alue o job in posi ion 1 and he o he jobs om posi ion 2 un il posi ion n, espec- i ely. Cons ain s (17) a e used o exp ess he ela ionship among se e al imes such as he p ocessing imes, he idle imes and he ime lags among jobs and he wo machines. In his o mula ion, he numbe o bina y a iables is n2 , he numbe o in ege a iables is 2n−1 , and he numbe o cons ain s is 6n−1 . Valid inequali ies The wo p oposed MILP models include almos he same numbe o decision a iables, which can’ sol e la ge sized p oblems. Then by adding cu s, hei pe o mance can be enhanced by educing he numbe o decision a iables and hen he sea ch space. Two ypes o alid inequali ies a e p esen ed in his sec ion. Valid inequali ies based ondominance ules Fo his i s ype o he alid inequali ies, a p ep ocess- ing s ep is needed o de ine a se o p ecedence con- s ain s by using some dominance ules. Le his se deno e (15) n ∑ i=1 (ai+bi+𝜃min i)Xi,1 − n ∑ i=1 diXi,1 ≤T 1 (16) n ∑ i =1 (ai+𝜃min i)Xi,1 + j ∑ k=1 n ∑ i=1 biXi,k+ j ∑ k=2 I k − n ∑ i=1 diXi,j≤Tj∀j=2, …,n (17) n ∑ j =1 n ∑ i=1 aiXi,j+𝜃min n≤ n ∑ i=1 (ai+𝜃min i)Xi ,1 + n ∑ j= 1 n ∑ i= 1 biXi,j+ n−1 ∑ j= 1 Ij (18) Ij ≥ 0∀j=1, …,n−1 (19) Tj ≥ 0∀j=1, …,n (20) Xi , j∈{0, 1}∀i,j=1, …,n 𝜉= {(i,s)∈J2∶ he e exis s an op imal schedule such ha a job s is p ocessed a e a job i , hen he alid inequali ies o be added o he p oposed MILP model is: whe e ∑n j=1 jXi, j indica es he posi ion index o he job i as he bina y a iable Xi , j akes alue 1 i and only i job i is assigned o posi ion j. Then, hese inequali ies a e de i ed by using some speci ied ules. These ules a e p oposed by Hamdi e al. (2015) o he same s udied p oblem which aim o sequence a job i in an op imal sequence i some p ope ies holds. They a e p o ided as ollows: Rule 1: Fo any wo adjacen jobs (i, s)∈J2 , i (a) min {a s +𝜃 min s ,b i +𝜃 min i }≥a i +𝜃 min i (b) bi +𝜃 min i ≤b s +𝜃 min s (c) di ≤ ds Then he e exis s an op imal schedule such ha i is p o- cessed be o e s. Rule 2: Fo job i, i he e is a job s sa is ying (a) ai +𝜃 min i +b i ≥a s +𝜃 min s +b s (b) 𝜃min i ≤𝜃 min s (c) bi−di ≤ bs−ds Then, he e exis s an op imal schedule such ha i is no he i s job o he sequence. So ha , he a iable Xi,1 will be elimina ed om he o mula ion. Posi ion‑based alid inequali ies These inequali ies a e based on he ac ha he comple ion ime o a job in posi ion j is g ea e han a lowe bound ( 𝜆j) . Then, we ha e: The lowe bound alue ( 𝜆j ) can be calcula ed easily by using he ollowing p oposed o mula: He e, ∑ i bi n is he mean alue o hep ocessing imes on he second machine; hen by elaxing he minimal ime lags cons ain s (as we conside only he minimal alue) and adding he minimal alue o p ocessing ime on he i s machine ( ai) , we ob ain a lowe bound on he comple ion (21) n ∑ j= 1 jXi,j+1≤ n ∑ j= 1 jXi,s,(i,s)∈ 𝜉 (22) C j,2 ≥ n ∑ i=1 𝜆jXi,j∀j=1, …, n 𝜆 j=min i {ai}+min i {𝜃min i}+j×{ ∑ i bi n }∀j=1, …, n S227Jou nal o Indus ial Enginee ing In e na ional (2019) 15 (Suppl 1):S223–S229 1 3 ime o he job in posi ion 1. The e o e, o de e mine he lowe bound on he comple ion ime o each job in posi- ion j(𝜆j) , we should mul iply ∑ i bi n by j∀j=1, …,n o sa - is y he condi ion 𝜆1<𝜆 2< ⋯ <𝜆 n in acco dance wi h C1,2 <C2,2 < ⋯ <Cn,2 . Compu a ional esul s Compu a ional expe imen s a e done o assess he e ec i e- ness o he p oposed models, mainly he enhancemen p o- ided by adding he cu s and he e ec o a ying he mini- mal ime lagsin e als. These models a e es ed by unning heCPLEX 11sol e on a DELL PC/2.20 GHz wi h 4.00 Go RAM. The es s a e conduc ed on a se o gene a ed ins ances ollowing he scheme desc ibed in Hamdi and Loukil (2015b). The p ocessing imes and he minimal ime lags a e gene a ed om a uni o m dis ibu ion be ween 20 and 50 and [0, 𝜃min ], espec i ely whe e 𝜃min ∈{ 0, 7, 14 } . The due da es a e gene a ed as di=P×D ange , whe e P is a lowe bound o he makespan which is gi en as ollows: P =min i {ai+𝜃 min i}+ ∑n i=1b i and D ange =[0.8, 1.2] . The numbe o jobs n is aken o be equal o 10, 15, 20, 25, 40, and 60 jobs. Fo each combina ion o n and 𝜃min , i e ins ances a e gene a ed and he a e age alue o he o al a diness is de e mined. The uppe limi o he CPU ime o sol ing a p oblem is se o 3600 s. We es he ollowing di e en o mula ions: F1 : Comple ion ime-based o mula ion F2 : Idle ime-based o mula ion F3 : F1 + alid inequali y based on dominance ules F4 : F1 + posi ion-based alid inequali y F5 : F1 + he wo se s o inequali ies The esul s a e displayed in Table1. Fo each es ed p ob- lem, we p o ide he CPU ime and he numbe o nodes equi ed o sol e i . The numbe be ween pa en hesis indi- ca es he numbe o unsol ed ins ances. F om he abo e able, we obse e he ollowing poin s: • In spi e ha bo h MILP models include O(n2) bina y a iables and O(n) in ege a iables, he idle-based o - mula ion equi es a bi mo e numbe o nodes o almos all he sizes, hus, i consumes mo e CPU ime o sol e p oblems. • I is ob ious ha he i e models a e able o sol e op i- mally p oblems wi h up o n= 40 in less han one hou , and e en some ins ances wi h up o 60 jobs. • Inc easing he minimal ime lags in e als has a dis in- guishable impac on inc easing he numbe o nodes and he CPU ime. • We could p o e he e e o adding cons ain s on igh - ening he sea ch space as he numbe o nodes and he CPU o he h ee las models end o be dec eased while Table 1 Impac o he alid inequali ies and he minimal ime lags on he esul s n 𝜃min F1 F2 F3 F4 F5 Nodes CPU Nodes CPU Nodes CPU Nodes CPU Nodes CPU 10 0 1.152 0.04 2.540 0.04 2.290 0.04 1.210 0.02 872 0.02 7 920 0.03 2.180 0.08 1.652 0.04 1.089 0.02 914 0.02 14 2.230 0.14 4.271 1.82 3.121 0.04 1.826 0.04 890 0.03 15 0 4.029 1.18 5.320 1.20 3.540 1.17 2.720 0.04 1.581 0.03 7 3.244 2.11 7.211 2.16 3.768 1.15 2.542 1.10 2.044 0.07 14 5.720 2.25 9.017 3.67 6.543 2.50 3.204 1.17 3.000 1.10 20 0 29.276 2.80 41.432 2.97 14.546 2.18 19.768 2.70 15.536 1.89 7 30.671 3.78 40.713 4.21 20.622 2.66 27.756 2.85 20.429 2.50 14 35.810 4.31 55.715 5.32 27.783 2.32 29.077 2.86 29.008 2.75 25 0 97.879 8.87 180.661 10.49 95.670 6.81 85.880 5.43 80.545 5.11 7 109.220 9.10 217.319 10.67 110.989 9.21 93.940 7.21 87.443 6.72 14 178.702 10.76 275.552 12.63 118.901 9.80 112.850 9.40 100.420 9.06 40 0 1255.61 29.14 1060.34 20.64 1409.44 33.29 816.25 17.28 410.88 11.47 7 2190.17 45.46 3019.78 49.29 1780.28 47.12 1970.27 50.32 1849.22 38.91 14 5478.27 67.82 7267.22 70.40 4817.32 58.88 5192.68 60.75 3455.18 41.69 60 0 17,562.278 192.18 27,361.913 210.75 (2) 10,462.667 87.41 11,378.410 160.29 8658.919 128.19 7 24,445.612 331.39 (3) 68,431.224 410.65 (3) 24,556.901 208.54 (1) 22,798.016 200.48 (2) 18,678.138 158.10 14 65,122.679 427.10 (3) 91,245.119 481.45 (3) 39,901.778 228.50 (2) 42,560.186 269.10 (2) 28,924.715 170.26 (1) S228 Jou nal o Indus ial Enginee ing In e na ional (2019) 15 (Suppl 1):S223–S229 1 3 adding he alid inequali ies. The model F5 , cha ac e - ized by adding he wo se s o he inequali ies, is he mos e icien as i is less ime-consuming han he models F3 and F4 . To con i m his las poin and o assess he imp o emen induced by he included ype o inequali ies o he basic MILP model, we de e mine o each o he las h ee o mu- la ions ( F3 , F4 , and F5 ), he a io o he CPU ime equi ed by each p oblem o he CPU ime equi ed by his p oblem in he o iginal o mula ion (F1) . Then, he esul s a e shown in Table2. The las column in Table2 indica es he a e age alue o he calcula ed a io alues o each o mula ion (F3,F4, and F5) by conside ing all n and 𝜃min . Then, adding he wo alid inequali ies can induce a g ea imp o emen o he o iginal o mula ion by educing signi ican ly he CPU ime un il 5.5 imes. Conclusion In his pape , we p oposed wo ma hema ical o mula ions o he wo-machine pe mu a ion lowshop p oblem wi h minimal ime lags scheduling p oblem. Two se s o alid inequali ies a e p oposed, whe e he i s one is based on some dominance ules om he li e a u e and he second one is based on a lowe bound o he job comple ion ime. Di e en ways a e used o in eg a e hese inequali ies o he comple ion ime-based model which leads o compa e i e ma hema ical models. As o ou knowledge, i is he i s pape ha p oposes and compa es he compu a ional pe o - mance o some ma hema ical o mula ions while conside - ing he minimal ime lags cons ain s. The e was no iceable imp o emen in e ms o educing he sea ch space and he ime-consuming equi ed o sol e he p oblem mainly he model F5 cha ac e ized by adding he wo ypes o he alid inequali ies. Open Access This a icle is dis ibu ed unde he e ms o he C ea- i e Commons A ibu ion 4.0 In e na ional License (h p://c ea i eco mmons .o g/licen ses/by/4.0/), which pe mi s un es ic ed use, dis ibu- ion, and ep oduc ion in any medium, p o ided you gi e app op ia e c edi o he o iginal au ho (s) and he sou ce, p o ide a link o he C ea i e Commons license, and indica e i changes we e made. Re e ences Chu C, P o h JM (1996) Single machine scheduling wi h chain s uc u ed p ecedence cons ain s and sepa a ion ime windows. IEEE T ans Robo Au om 12(6):835–844 Dell’Amico M (1996) Shop p oblems wi h wo machines and ime lags. J Ope Res 44(5):777–787 Deppne F (2004) O donnancemen d’a elie a ec con ain es em- po elles en e ope a ions. Ph.D. Thesis, Ins i u Na ional Poly- echnique de Lo aine Dhouib E, Teghem J, Moalla Loukil T (2013) Lexicog aphic op imi- za ion o a pe mu a ion low shop scheduling p oblem wi h ime lag cons ain s. In T ans Ope Res 20(2):213–232 Fond e elle J, Oulama a A, Po mann MC (2006) Pe mu a ion lowshop scheduling p oblems wi h maximal and minimal ime lags. Compu Ope Res 33(6):1540–1556 Foulds LR, Wilson JM (2005) Scheduling ope a ions o he ha es - ing o enewable esou ces. J Food Eng 70(3):281–292 G aham R, Lawle E, Lens a JK, Rinnooy Kan AHG (1979) Op i- miza ion and app oxima ion in de e minis ic sequencing and scheduling: a su ey. Ann Disc e e Ma h 5:287–326 Hamdi I, Loukil T (2017) The pe mu a ion lowshop scheduling p oblem wi h exac ime lags o minimize he o al ea liness and a diness. In J Ope Res 28(1):70–86 Hamdi I, Loukil T (2015a) Minimizing o al a diness in he pe mu- a ion lowshop scheduling p oblem wi h minimal and maximal ime lags. Ope Res In J 15(1):95–114 Hamdi I, Loukil T (2015b) Uppe and lowe bounds o he pe mu- a ion lowshop scheduling p oblem wi h minimal ime lags. Op im Le 9(3):465–482 Hamdi I, Oulama a A, Loukil T (2015) A b anch and bound algo- i hm o minimize o al a diness in he wo machine lowshop p oblem wi h minimal ime lags. In J Ope Res 23(4):387–405 Hamdi I, Loukil T (2011) Minimizing he makespan in he pe mu a- ion lowshop p oblem wi h minimal and maximal ime lags. In: P oceeding o he 2011 IEEE in e na ional con e ence o com- munica ions, compu ing and con ol applica ions (CCCA’11) 03-05 Ma s 2011 a Hammame , Tunisie Table 2 Ra io alues o CPU ime F 𝜃min nA e age alue 10 15 20 25 40 60 F3 0 1.00 1.00 1.28 1.30 0.87 2.19 1.41 7 0.75 1.84 1.42 0.98 0.96 1.58 14 3.50 0.90 1.85 1.09 1.15 1.86 F4 0 2.00 29.5 1.04 1.63 1.68 1.19 3.13 7 1.50 2.00 1.40 1.26 0.90 1.65 14 3.50 1.92 1.50 1.14 1.11 1.58 F5 0 2.00 39.3 1.48 1.73 2.48 1.49 5.54 7 1.50 30.14 1.51 1.35 1.16 2.09 14 4.60 2.04 1.56 1.18 1.62 2.50 S229Jou nal o Indus ial Enginee ing In e na ional (2019) 15 (Suppl 1):S223–S229 1 3 Huang JD, Liu1 JJ, Chen QX and Mao N (2013) Mixed in ege omu- la ion o a diness objec i es in a low shop wi h wo ba ches- p ocessing machines and elease da e. In: CIE43 p oceedings, 16–18 Oc obe 2013, The Uni e si y o Hong Kong Kesha a z T, Salmasi N, Va mazya M (2019) Flowshop sequence- dependen g oup scheduling wi h minimisa ion o weigh ed ea liness and a diness. Eu J Ind Eng 13(1):54–80 Kha beche M, Haoua i M (2013) MIP models o minimizing o al a diness in a wo-machine low shop. J Ope Res Soc 64(5):690–707 Kim YD (1993) A new b anch-and-bound algo i hm o minimizing mean a diness in wo-machine lowshops. Compu Ope Res 20(4):391–401 Mo eno-Camacho CA, Mon oya-To es JR, Vélez-Gallego MC (2018) A compa ison o mixed-in ege linea p og amming models o wo k o ce scheduling wi h posi ion-dependen p ocessing imes. Eng Op im 50(6):917–932 Pan JC-H, Fan ET (1997) Two-machine lowshop scheduling o mini- mize o al a diness. In J Sys Sci 28(4):405–414 Pan JC-H, Chen J-S and Chao C-M (2002) Minimizing a diness in a wo-machine lowshop. Compu Ope Res 29(7):869–885 Ronconi DP, Bi gin EG (2012) Mixed-in ege p og amming models o lowshop scheduling p oblems minimizing he o al ea liness and a diness. Jus -in-Time Sys 23:91–105 Schalle J (2005) No e on minimizing o al a diness in a womachine lowshop. Compu Ope Res 32(12):3273–3281 Yu W, Hooge een H, Lens a JK (2004) Minimising makespan in a wo machine lowshop wi h delays and uni ime ope a ions is NP-ha d. J Sched 7(5):333–348