In this paper we consider the problem of scheduling, on a two-machine flowshop, a set of unit-time operations subject to time delays with respect to the makespan. This problem is known to be \hbox{$\mathcal{N}P$} 𝒩𝒫 -hard in the strong sense. We propose an algorithm based on a branch and bound enumeration scheme. This algorithm includes the implementation of new lower and upper bound procedures, and dominance rules. A computer simulation to measure the performance of the algorithm is provided for a wide range of test problems.

Keywords: branch and bound, dominance rule, flowshop, lower and upper bounds, time delays

@article{RO_2014__48_2_235_0, author = {Moukrim, Aziz and Rebaine, Djamal and Serairi, Mehdi}, title = {A branch and bound algorithm for the two-machine flowshop problem with unit-time operations and time delays}, journal = {RAIRO - Operations Research - Recherche Op\'erationnelle}, pages = {235--254}, publisher = {EDP-Sciences}, volume = {48}, number = {2}, year = {2014}, doi = {10.1051/ro/2014004}, mrnumber = {3264377}, zbl = {1292.90321}, language = {en}, url = {http://archive.numdam.org/articles/10.1051/ro/2014004/} }

TY - JOUR AU - Moukrim, Aziz AU - Rebaine, Djamal AU - Serairi, Mehdi TI - A branch and bound algorithm for the two-machine flowshop problem with unit-time operations and time delays JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2014 SP - 235 EP - 254 VL - 48 IS - 2 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ro/2014004/ DO - 10.1051/ro/2014004 LA - en ID - RO_2014__48_2_235_0 ER -

%0 Journal Article %A Moukrim, Aziz %A Rebaine, Djamal %A Serairi, Mehdi %T A branch and bound algorithm for the two-machine flowshop problem with unit-time operations and time delays %J RAIRO - Operations Research - Recherche Opérationnelle %D 2014 %P 235-254 %V 48 %N 2 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ro/2014004/ %R 10.1051/ro/2014004 %G en %F RO_2014__48_2_235_0

Moukrim, Aziz; Rebaine, Djamal; Serairi, Mehdi. A branch and bound algorithm for the two-machine flowshop problem with unit-time operations and time delays. RAIRO - Operations Research - Recherche Opérationnelle, Volume 48 (2014) no. 2, pp. 235-254. doi : 10.1051/ro/2014004. http://archive.numdam.org/articles/10.1051/ro/2014004/

[1] Branch and bound methods, chapter 10, in The traveling salesman problems: a guided tour of Combinatorial Opt., edited by E.L. Lawler. John Wiley (1985). | MR | Zbl

and ,[2] Introduction to Algorithms. McGraw-Hill (1990). | MR | Zbl

, and ,[3] Sequencing and scheduling: an introduction to the mathematics of the job-shop. Series: Math. and its Appl. Ellis Horwood Ltd. (1982). | MR | Zbl

,[4] Flow shop and job shop schedules: complexity and approximations. Oper. Res. 26 (1978) 36-52. | MR | Zbl

and ,[5] Optimal two- and three-stage production with set-up times included. Nav. Res. Log. Quart. 1 (1954) 61-68.

,[6] Polynomial time algorithms for the UET permutation flowshop problem with time delays. Comput. Oper. Res. 35 (2008) 525-537. | MR | Zbl

and ,[7] Analysis of heuristics for the UET two-machine flow shop. Comput. Oper. Res. 35 (2008) 3298-3310. | Zbl

and ,[8] Permutation shop vs. non permutation flow shop with delays. J. Comput. Industrial Engrg. 48 (2005) 357-362.

,[9] Minimizing makespan in a two-machine flow with delays and unit-time operations is NP-hard. J. Schedul. 7 (2004) 333-348. | MR | Zbl

, and ,[10] The two-machine flow shop problem and the one-machine total tardiness problem. Ph.D. thesis, Eindhoven University of Technology, The Netherlands (1996). | MR | Zbl

,*Cited by Sources: *