Skip to Main content Skip to Navigation
Journal articles

A two-stage flow shop scheduling problem with transportation considerations

Abstract : This paper considers a two-stage robotic flow shop scheduling problem of which the objective is to minimize the maximum completion time of all the jobs. The problem consists of two dedicated machines at the first stage and a single machine at the second stage. Each job is defined by two operations processed in series on two stages. Depending on the job type, each job is processed on a dedicated machine at the first stage, and is then transported, by a robot or a conveyor, to be processed on a single machine at the second stage. To tackle the problem, a mixed integer programming model is proposed, which is solved by CPLEX. This model is improved using valid inequalities based on three lower bounds. In addition, we establish the complexity of several variations of the problem and we identify special cases that can be solved in polynomial time. Furthermore due to the NP-hardness of the problem, two heuristics are proposed to solve approximately large-sized problems. The results indicate that the solutions obtained are of high quality and the corresponding CPU time is acceptable.
Document type :
Journal articles
Complete list of metadata

https://hal-uphf.archives-ouvertes.fr/hal-03402138
Contributor : Mylène Delrue Connect in order to contact the contributor
Submitted on : Monday, October 25, 2021 - 3:25:02 PM
Last modification on : Wednesday, November 17, 2021 - 3:08:33 AM

Identifiers

Collections

Citation

Nacira Chikhi, Moncef Abbas, Rachid Benmansour, Abdelghani Bekrar, Said Hanafi. A two-stage flow shop scheduling problem with transportation considerations. 4OR: A Quarterly Journal of Operations Research, Springer Verlag, 2015, 13 (4), pp.381-402. ⟨10.1007/s10288-015-0297-4⟩. ⟨hal-03402138⟩

Share

Metrics

Record views

9