A branch and bound algorithm for the two-machine flowshop problem with unit-time operations and time delays
RAIRO - Operations Research - Recherche Opérationnelle, Tome 48 (2014) no. 2, pp. 235-254.

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 𝒩𝒫-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.

DOI : 10.1051/ro/2014004
Classification : 9008
Mots-clés : 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, Tome 48 (2014) no. 2, pp. 235-254. doi : 10.1051/ro/2014004. http://archive.numdam.org/articles/10.1051/ro/2014004/

[1] E. Balas and P. Toth, 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

[2] T.H. Cormen, C.E. Leiserson and R.L. Rivest, Introduction to Algorithms. McGraw-Hill (1990). | MR | Zbl

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

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

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

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

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

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

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

[10] W. Yu, 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

Cité par Sources :