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.