Program > By author > Chikhi Nacira

Thursday 27
Heuristics and meta-heuristics
THIERRY BENOIST
› 14:00 - 14:20 (20min)
› Bât. C - Sigalas
On the complexity of robotic flow shop with transportation constraints
Nacira Chikhi  2, 1, *@  , Moncef Abbas  1@  , Abdelghani Bekrar  3@  , Rachid Benmansour  2@  , Said Hanafi  2@  
2 : Laboratoire d'Automatique, de Mécanique et d'Informatique Industrielles et Humaines  (LAMIH)
Université de Valenciennes et du Hainaut-Cambrésis
1 : Laboratoroire AMCD&RO , Université des sciences et de la technologie USTHB
3 : Laboratoire de Thermique, Ecoulements Mécaniques matériaux mise en forme PrOduction  (TEMPO)
Université de Valenciennes et du Hainaut Cambrésis
* : Corresponding author

Most of machine scheduling models in the literature assume that either transportation capacity of transporters for delivering jobs is unlimited or transportation times from one location to another are negligible. In this paper, we study a two stages robotic flow shop problem which is a scheduling problem in a robotic cell with dedicated machines at the first stage and a common machine at the second stage. There are several applications of this problem in automated manufacturing systems especially in flexible manufacturing cells. We have two types of jobs. Each one has to be executed on a dedicated machine at the first stage and the jobs are transported in batches between the two stages by a conveyor with a limited capacity cThe objective is to find a joint schedule of production and transportation such that the makespan is minimized. First, we provide new complexity results, more precisely we prove that a special case of the problem with conveyor capacity c=2 is NP-Hard by a reduction from 3-Partition problem and we establish new lower bounds on the makespan. Next, we propose an exact method to solve a particular problem. Finally, computational experiments are designed on randomly generated problem instances to compare our exact method with other approaches in the litterature. The numerical experiments show the efficiency of our method.


Online user: 1