# A branch and bound algorithm for the two-machine flowshop problem with unit-time operations and time delays

Aziz Moukrim; Djamal Rebaine; Mehdi Serairi

RAIRO - Operations Research - Recherche Opérationnelle (2014)

- Volume: 48, Issue: 2, page 235-254
- ISSN: 0399-0559

## Access Full Article

top## Abstract

top## How to cite

topMoukrim, Aziz, Rebaine, Djamal, and 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 48.2 (2014): 235-254. <http://eudml.org/doc/275093>.

@article{Moukrim2014,

abstract = {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 $\{\mathcal \{N\}P\}$ x1d4a9;x1d4ab; -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.},

author = {Moukrim, Aziz, Rebaine, Djamal, Serairi, Mehdi},

journal = {RAIRO - Operations Research - Recherche Opérationnelle},

keywords = {branch and bound; dominance rule; flowshop; lower and upper bounds; time delays},

language = {eng},

number = {2},

pages = {235-254},

publisher = {EDP-Sciences},

title = {A branch and bound algorithm for the two-machine flowshop problem with unit-time operations and time delays},

url = {http://eudml.org/doc/275093},

volume = {48},

year = {2014},

}

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

PB - EDP-Sciences

VL - 48

IS - 2

SP - 235

EP - 254

AB - 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 ${\mathcal {N}P}$ x1d4a9;x1d4ab; -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.

LA - eng

KW - branch and bound; dominance rule; flowshop; lower and upper bounds; time delays

UR - http://eudml.org/doc/275093

ER -

## References

top- [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). Zbl0568.90068MR811477
- [2] T.H. Cormen, C.E. Leiserson and R.L. Rivest, Introduction to Algorithms. McGraw-Hill (1990). Zbl1158.68538MR1066870
- [3] S. French, Sequencing and scheduling: an introduction to the mathematics of the job-shop. Series: Math. and its Appl. Ellis Horwood Ltd. (1982). Zbl0479.90037MR642978
- [4] T. Gonzalez and S. Sahni, Flow shop and job shop schedules: complexity and approximations. Oper. Res.26 (1978) 36–52. Zbl0371.90061MR465149
- [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. Zbl1141.90020MR2318886
- [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. Zbl1135.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. Zbl1154.90506MR2101693
- [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). Zbl0863.90096MR1393202

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.