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, p. 235-254
Le texte intégral des articles récents est réservé aux abonnés de la revue. Consulter l'article sur le site de la revue
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{$𝒩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.
DOI : https://doi.org/10.1051/ro/2014004
Classification:  9008
@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},
publisher = {EDP-Sciences},
volume = {48},
number = {2},
year = {2014},
pages = {235-254},
doi = {10.1051/ro/2014004},
zbl = {1292.90321},
mrnumber = {3264377},
language = {en},
url = {http://www.numdam.org/item/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. https://www.numdam.org/item/RO_2014__48_2_235_0/

[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 811477 | Zbl 0568.90068

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

[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 642978 | Zbl 0479.90037

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

[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 2318886 | Zbl 1141.90020

[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 1135.90016

[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 2101693 | Zbl 1154.90506

[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 1393202 | Zbl 0863.90096