Skip to Main content Skip to Navigation
Conference papers

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

Abstract : 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
Document type :
Conference papers
Complete list of metadata

https://hal-uphf.archives-ouvertes.fr/hal-03470247
Contributor : Mylène Delrue Connect in order to contact the contributor
Submitted on : Wednesday, December 8, 2021 - 10:35:59 AM
Last modification on : Thursday, December 9, 2021 - 3:47:49 AM

Identifiers

  • HAL Id : hal-03470247, version 1

Collections

Citation

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⟩

Share

Metrics

Les métriques sont temporairement indisponibles