Two machines flow shop with reentrance and exact time lag

Amrouche, Karim; Boudhar, Mourad

doi:10.1051/ro/2015015

Amrouche, Karim ^1,² ; Boudhar, Mourad ²

¹ University of Algiers 3, Faculty of Economics and Management sciences, 2 street Ahmed Waked, Dely Brahim, Algiers, Algeria.
² RECITS laboratory, Faculty of Mathematics, USTHB University, BP 32 Bab-Ezzouar, 16111 El-Alia, Algiers, Algeria.

RAIRO - Operations Research - Recherche Opérationnelle, Special issue: Research on Optimization and Graph Theory dedicated to COSI 2013 / Special issue: Recent Advances in Operations Research in Computational Biology, Bioinformatics and Medicine, Tome 50 (2016) no. 2, pp. 223-232.

Résumé

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.

MR Zbl

DOI : 10.1051/ro/2015015

Classification : 90B35
Mots-clés : Flow shop, reentrance, time lag, makespan, complexity

Affiliations des auteurs :

Amrouche, Karim ^{1, 2} ; Boudhar, Mourad ²

@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://www.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://www.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://www.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, Special issue: Research on Optimization and Graph Theory dedicated to COSI 2013 / Special issue: Recent Advances in Operations Research in Computational Biology, Bioinformatics and Medicine, Tome 50 (2016) no. 2, pp. 223-232. doi : 10.1051/ro/2015015. http://www.numdam.org/articles/10.1051/ro/2015015/

Bibliographie
Cité par

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

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

D. Ahr, J. Békési, G. Galambos, M. Oswald and G. Reinelt, An exact algorithm for scheduling identical coupled tasks. Math. Methods Oper. Res. 59 (2004) 193–203. | DOI | MR | Zbl

J. Blazewicz, K. Ecker, T. Kis, Cn. Potts, M. Tanas and J. Whitehead, Scheduling of coupled tasks with unit processing times. J. Sched. 13 (2010) 453–461. | DOI | MR | Zbl

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

N. Brauner, G. Finke, V. Lehoux-Lebacque, C. Potts and J. Whithead, Scheduling of coupled tasks and one-machine no-wait robotic cells. Comput. Oper. Res. 36 (2009) 301–307. | DOI | MR | Zbl

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

E. Dhouib, J. Teghem and T. Loukir, 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

J. Fondrevelle, A. Oulamara, M.C. Portmann, 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

S.M. Johnson, 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. Lev and I. Adiri, V-shop scheduling. Eur. J. Oper. Res. 18 (1984) 51–56. | DOI | MR | Zbl

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

A.J. Orman and C.N. Potts, On the Complexity of Coupled-task Scheduling. Discrete Appl. Math. 72 (1997) 141–54. | DOI | MR | Zbl

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

F.D. Vargas-Villamil and D.E. Rivera, A model predictive control approach for real-time optimization of reentrant manufacturing lines. Comput. Ind. 45 (2001) 45–57. | DOI

M.Y. Wang, S.P. Sethi and S.L. Van De Velde, Minimizing makespan in a class of reentrant shops. Oper. Res. 45 (1997) 702–712. | DOI | Zbl

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

W. Yu, H. Hoogeveen and J.K. Lenstra, 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

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

Cité par Sources :