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{} 𝒩𝒫 -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.
Mots clés : branch and bound, dominance rule, flowshop, lower and upper bounds, time delays
@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},
pages = {235--254},
publisher = {EDP-Sciences},
volume = {48},
number = {2},
year = {2014},
doi = {10.1051/ro/2014004},
mrnumber = {3264377},
zbl = {1292.90321},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ro/2014004/}
}
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 SP - 235 EP - 254 VL - 48 IS - 2 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro/2014004/ DO - 10.1051/ro/2014004 LA - en ID - RO_2014__48_2_235_0 ER -
%0 Journal Article %A Moukrim, Aziz %A Rebaine, Djamal %A Serairi, Mehdi %T A branch and bound algorithm for the two-machine flowshop problem with unit-time operations and time delays %J RAIRO - Operations Research - Recherche Opérationnelle %D 2014 %P 235-254 %V 48 %N 2 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ro/2014004/ %R 10.1051/ro/2014004 %G en %F 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. http://www.numdam.org/articles/10.1051/ro/2014004/
[1] and , 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 | Zbl
[2] , and , Introduction to Algorithms. McGraw-Hill (1990). | MR | Zbl
[3] , Sequencing and scheduling: an introduction to the mathematics of the job-shop. Series: Math. and its Appl. Ellis Horwood Ltd. (1982). | MR | Zbl
[4] and , Flow shop and job shop schedules: complexity and approximations. Oper. Res. 26 (1978) 36-52. | MR | Zbl
[5] , Optimal two- and three-stage production with set-up times included. Nav. Res. Log. Quart. 1 (1954) 61-68.
[6] and , Polynomial time algorithms for the UET permutation flowshop problem with time delays. Comput. Oper. Res. 35 (2008) 525-537. | MR | Zbl
[7] and , Analysis of heuristics for the UET two-machine flow shop. Comput. Oper. Res. 35 (2008) 3298-3310. | Zbl
[8] , Permutation shop vs. non permutation flow shop with delays. J. Comput. Industrial Engrg. 48 (2005) 357-362.
[9] , and , Minimizing makespan in a two-machine flow with delays and unit-time operations is NP-hard. J. Schedul. 7 (2004) 333-348. | MR | Zbl
[10] , The two-machine flow shop problem and the one-machine total tardiness problem. Ph.D. thesis, Eindhoven University of Technology, The Netherlands (1996). | MR | Zbl
Cité par Sources :
