A dynamic programming algorithm for a robotic cell problem with batch transfer

Nacira Chikhi (1) , Moncef Abbas (1) , Abdelghani Bekrar (2) , Rachid Benmansour (2) , Said Hanafi (2)

1 USTHB - Université des Sciences et de la Technologie Houari Boumediene = University of Sciences and Technology Houari Boumediene [Alger]
2 LAMIH - Laboratoire d'Automatique, de Mécanique et d'Informatique industrielles et Humaines - UMR 8201

In this paper, we study a robotic cell problem and precisely a robotic ?ow shop problem with two dedicated machines at the ?rst stage and a common machine at the second stage. We have two types of jobs where each job has to be processed on one dedicated machine at the ?rst stage and then on the common machine. The jobs are transported from the ?rst stage to the second one and the robot can carry up at most c jobs in one shipment. There are several applications of this problem in ?exible manufacturing systems. The main contribution of this study, is to propose exact and approximate methods for the robotic cell problem. The objective is to ?nd a joint schedule of production and transportation such that the makespan is minimized. We prove the NP-hardness of a special case of the general problem. We also provide polynomial time algorithms for some particular problems where the processing times are identical on the ?rst stage. Then, we develop a dynamic programming algorithm to solve optimally this general case. The experiments show the e?ciency of our algorithms

Domaines: Automatique / Robotique

Nacira Chikhi, Moncef Abbas, Abdelghani Bekrar, Rachid Benmansour, Said Hanafi. A dynamic programming algorithm for a robotic cell problem with batch transfer. 28th annual conference of the Belgian Operational Research Society (ORBEL28), Jan 2014, Mons, Belgium. ⟨hal-03470247⟩