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
doi : 10.1051/ro/2014004
URL stable : http://www.numdam.org/item?id=RO_2014__48_2_235_0

Classification:  9008
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.

### Bibliographie

[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