Volume 51, Number 3, July-September 2017
|Page(s)||749 - 762|
|Published online||10 August 2017|
New complexity results on scheduling problem in a robotic cell
1 Université des Sciences et de la Technologie USTHB, Laboratoire AMCD&RO, BP32, Bab-Ezzouar, 16111, Alger, Algérie.
2 Université de Valenciennes et du Hainaut Cambrésis, LAMIH – UMR CNRS 8201, Le Mont-Houy 59313 Valenciennes cedex 9, France.
Received: 29 December 2015
Accepted: 28 August 2016
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.
Mathematics Subject Classification: 90B35 / 90C59 / 90C11
Key words: Flowshop / complexity / makespan / dynamic algorithm / tranportation
© EDP Sciences, ROADEF, SMAI 2017
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.