This paper explores the coordinated scheduling problem between production and transportation in a two stage flow shop with dedicated machines. There are two dedicated machines at the first stage and one common machine at the second stage. Each job has to be processed on a specified machine at the stage 1 depending on job type. A transporter with limited capacity is available to transport the semi-finished jobs from stage 1 to stage 2 for further processing. The objective is to minimize the makespan, i.e. the maximum completion time of all the jobs. The main focus is on the case where the transporter capacity is equal to two. New complexity results related to this case are established. Due to the NP-hardness of the general problem, we develop approximative approach to tackle the problem. Computational results indicate that the obtained solutions within moderate CPU time are of high quality.
Accepted:
DOI: 10.1051/ro/2016053
Keywords: Flowshop, complexity, makespan, dynamic algorithm, tranportation
@article{RO_2017__51_3_749_0, author = {Chikhi, Nacira and Abbas, Moncef and Benmansour, Rachid and Hanafi, Sa{\"\i}d}, title = {New complexity results on scheduling problem in a robotic cell}, journal = {RAIRO - Operations Research - Recherche Op\'erationnelle}, pages = {749--762}, publisher = {EDP-Sciences}, volume = {51}, number = {3}, year = {2017}, doi = {10.1051/ro/2016053}, mrnumber = {3880523}, zbl = {1384.90042}, language = {en}, url = {http://archive.numdam.org/articles/10.1051/ro/2016053/} }
TY - JOUR AU - Chikhi, Nacira AU - Abbas, Moncef AU - Benmansour, Rachid AU - Hanafi, Saïd TI - New complexity results on scheduling problem in a robotic cell JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2017 SP - 749 EP - 762 VL - 51 IS - 3 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ro/2016053/ DO - 10.1051/ro/2016053 LA - en ID - RO_2017__51_3_749_0 ER -
%0 Journal Article %A Chikhi, Nacira %A Abbas, Moncef %A Benmansour, Rachid %A Hanafi, Saïd %T New complexity results on scheduling problem in a robotic cell %J RAIRO - Operations Research - Recherche Opérationnelle %D 2017 %P 749-762 %V 51 %N 3 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ro/2016053/ %R 10.1051/ro/2016053 %G en %F RO_2017__51_3_749_0
Chikhi, Nacira; Abbas, Moncef; Benmansour, Rachid; Hanafi, Saïd. New complexity results on scheduling problem in a robotic cell. RAIRO - Operations Research - Recherche Opérationnelle, Volume 51 (2017) no. 3, pp. 749-762. doi : 10.1051/ro/2016053. http://archive.numdam.org/articles/10.1051/ro/2016053/
Group shop scheduling with sequence-dependent setup and transportation times. Appl. Math. Model. 38 (2014) 5080–5091. | DOI | MR | Zbl
and ,N. Chikhi, M. Abbas, A. Bekrar, R. Benmansour and S. Hanafi, On the complexity of robotic flow shop with transportation constraints. In ROADEF – 15ème congrès annuel de la Société française de recherche opérationnelle et d’aide à la décision, Bordeaux, France (2014).
N. Chikhi, R. Benmansour, A. Bekrar, S. Hanafi and M. Abbas, A case study of a two-stage flow shop with dedicated machines and a single robot. In Control, Decision and Information Technologies (CoDIT) (2014).
A scheduling problem in blocking hybrid flow shop robotic cells with multiple robots. Comput. Oper. Res. 40 (2013) 2543–2555. | DOI | MR | Zbl
and ,Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discrete Math. 5 (1979) 287–326. | DOI | MR | Zbl
, , and ,Makespan minimization for flow-shop problems with transportation times and a single robot. Discrete Appl. Math. 112 (2001) 199–216. | DOI | MR | Zbl
and ,On an automated two-machine flowshop scheduling problem with infinite buffer. J. Oper. Res. Soc. Jpn. 34 (1991) 354–361. | MR | Zbl
,Machine scheduling with transportation considerations. J. Sched. 4 (2001) 24. | MR | Zbl
and ,Scheduling a two-machine robotic cell: A solvable case. Ann. Oper. Res. 57 (1995) 217–232. | DOI | Zbl
, and ,The strong np-hardness of two-stage flowshop scheduling with a common second-stage machine. Comput. Oper. Res. 26 (1999) 695–698. | DOI | MR | Zbl
,S. Panwalkar, Scheduling of a two-machine flowshop with travel time between machines. J. Oper. Res. Soc. (1991) 609–613. | Zbl
Two-machine flowshop scheduling problems involving a batching machine with transportation or deterioration consideration. Appl. Math. Modelling 33 (2009) 1187–1199. | DOI | MR | Zbl
and ,Two-stage hybrid flow shop scheduling with dynamic job arrivals. Comput. Oper. Res. 39 (2012) 1701–1712 . | DOI | MR | Zbl
, and ,Hybrid flowshop scheduling with interstage job transportation. J. Oper. Res. Soc. China 2 (2014) 109–121. | DOI | MR | Zbl
and ,Cited by Sources: