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

Abstract

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

How to cite

top

Moukrim, 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. [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. [2] T.H. Cormen, C.E. Leiserson and R.L. Rivest, Introduction to Algorithms. McGraw-Hill (1990). Zbl1158.68538MR1066870
  3. [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. [4] T. Gonzalez and S. Sahni, Flow shop and job shop schedules: complexity and approximations. Oper. Res.26 (1978) 36–52. Zbl0371.90061MR465149
  5. [5] S. Johnson, Optimal two- and three-stage production with set-up times included. Nav. Res. Log. Quart.1 (1954) 61–68. 
  6. [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. [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. [8] D. Rebaine, Permutation shop vs. non permutation flow shop with delays. J. Comput. Industrial Engrg.48 (2005) 357–362. 
  9. [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. [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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.