This paper considers a reentrant flow shop with two machines and exact time lag $L$, in which each task may be processed in this order ${M}_{1},{M}_{2},{M}_{1}$ and there is an identical time lag between the completion time of the first operation and the start time of the second operation on the first machine. The objective is to minimize the total completion time. We prove the NP-hardness of a special case and we give some special subproblems that can be solved in polynomial time.

Keywords: Flow shop, reentrance, time lag, makespan, complexity

^{1, 2}; Boudhar, Mourad

^{2}

@article{RO_2016__50_2_223_0, author = {Amrouche, Karim and Boudhar, Mourad}, title = {Two machines flow shop with reentrance and exact time lag}, journal = {RAIRO - Operations Research - Recherche Op\'erationnelle}, pages = {223--232}, publisher = {EDP-Sciences}, volume = {50}, number = {2}, year = {2016}, doi = {10.1051/ro/2015015}, mrnumber = {3479865}, zbl = {1338.90157}, language = {en}, url = {http://archive.numdam.org/articles/10.1051/ro/2015015/} }

TY - JOUR AU - Amrouche, Karim AU - Boudhar, Mourad TI - Two machines flow shop with reentrance and exact time lag JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2016 SP - 223 EP - 232 VL - 50 IS - 2 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ro/2015015/ DO - 10.1051/ro/2015015 LA - en ID - RO_2016__50_2_223_0 ER -

%0 Journal Article %A Amrouche, Karim %A Boudhar, Mourad %T Two machines flow shop with reentrance and exact time lag %J RAIRO - Operations Research - Recherche Opérationnelle %D 2016 %P 223-232 %V 50 %N 2 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ro/2015015/ %R 10.1051/ro/2015015 %G en %F RO_2016__50_2_223_0

Amrouche, Karim; Boudhar, Mourad. Two machines flow shop with reentrance and exact time lag. RAIRO - Operations Research - Recherche Opérationnelle, Volume 50 (2016) no. 2, pp. 223-232. doi : 10.1051/ro/2015015. http://archive.numdam.org/articles/10.1051/ro/2015015/

Approximation algorithms for UET scheduling problems with exact delays. Oper. Res. Lett. 35 (2007) 533–540. | DOI | MR | Zbl

and ,A.A. Ageev and A.V. Kononov, Approximation Algorithms for Scheduling Problems with Exact Delays. In WAOA, vol. 4368 of Lect. Notes Comput. Sci. (2006) 1–14. | MR | Zbl

An exact algorithm for scheduling identical coupled tasks. Math. Methods Oper. Res. 59 (2004) 193–203. | DOI | MR | Zbl

, , , and ,Scheduling of coupled tasks with unit processing times. J. Sched. 13 (2010) 453–461. | DOI | MR | Zbl

, , , , and ,Two-stage hybrid flow shop with recirculation. Int. Trans. Oper. Res. 17 (2010) 239–255. | DOI | MR | Zbl

and ,Scheduling of coupled tasks and one-machine no-wait robotic cells. Comput. Oper. Res. 36 (2009) 301–307. | DOI | MR | Zbl

, , , and ,Shop problems with two machines and time lags. Oper. Res. 44 (1996) 777–787. | DOI | Zbl

,Minimizing the Number of Tardy Jobs in a Permutation Flowshop Scheduling Problem with Setup Times and Time Lags Constraints. J. Math. Model. Algorithms 12 (2013) 85–99. | MR | Zbl

, and ,Permutation flowshop scheduling problems with time lags to minimize the weighted sum of machine completion times. Int. J. Prod. Econ. 33 (2007) 168–176.

, , ,M.R. Garey and D.S. Johnson, Computers and Intractability. W.H. Freeman and Company, New York (1979). | MR | Zbl

Optimal two and three-stage production schedules with setup times included. Nav. Res. Logist. Quarterly 1 (1954) 61–68. | DOI | Zbl

,E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D.B. Shmoys, Sequencing and scheduling theory: algorithms and complexity. In Handb. Oper. Res. Manag. Sci. Edited by S.C. Graves, P.H. Zipkin and A.H.G. Rinnooy Kan. North Holland, Amesterdam (1993).

V-shop scheduling. Eur. J. Oper. Res. 18 (1984) 51–56. | DOI | MR | Zbl

and ,Sequencing n jobs on two machines with arbitrary time lags. Manage. Sci. 5 (1959) 293–298. | DOI | MR | Zbl

,On the Complexity of Coupled-task Scheduling. Discrete Appl. Math. 72 (1997) 141–54. | DOI | MR | Zbl

and ,Scheduling coupled tasks. Nav. Res. Logist. Quarterly 27 (1980) 489–497. | DOI | MR | Zbl

,A model predictive control approach for real-time optimization of reentrant manufacturing lines. Comput. Ind. 45 (2001) 45–57. | DOI

and ,Minimizing makespan in a class of reentrant shops. Oper. Res. 45 (1997) 702–712. | DOI | Zbl

, and ,W. Yu, The two-machine flowshop problem with delays and the one-machine total tardiness problem. Ph. D. thesis, Technische Universiteit Eindhoven (1996). | MR | Zbl

Minimizing makespan in a two-machine flow shop with delays and unit-time operations is np-hard. J. Sched. 7 (2004) const3–348. | MR | Zbl

, and ,On-line two-machine open shop scheduling with time lags. Eur. J. Oper. Res. 204 (2010) 14–19. | DOI | MR | Zbl

and ,*Cited by Sources: *