Skip to Main content Skip to Navigation
Journal articles

Makespan minimization on a two-machine flowshop with an availability constraint on the first machine

Abstract : This paper deals with the scheduling of a two-machineflowshop with an availability constraint on thefirst machine with the aim of minimizing the makespan. We investigate two mixed-integer program-ming (MIP) models for this problem. Then we propose a branch and bound (B&B) algorithm based on aset of new lower bounds and heuristics. We further provide the results of extensive computationalexperiments performed on randomly generated instances to show the efficiency of the proposedapproaches. Our computational study reveals that most of the instances of size up to 100 jobs areoptimally solved with the (B&B) method. However, thefirst MIP (MIP1) model is able to solve optimallyinstances of size up to 10 jobs and the second MIP (MIP2) model can solve instances of size up to 20 jobs.It has been shown that there is an impact of the unavailability start time period and instances withunavailability period at the middle of the time window are the hardest to solve. The impact of the lengthof the unavailability period on the performance of the (B&B) is also considered
Document type :
Journal articles
Complete list of metadatas

https://hal-utt.archives-ouvertes.fr/hal-02497215
Contributor : Daniel Gavrysiak <>
Submitted on : Tuesday, March 3, 2020 - 3:09:31 PM
Last modification on : Wednesday, March 4, 2020 - 1:34:26 AM

Identifiers

Collections

ROSAS | UTT | CNRS

Citation

Faicel Hnaien, Farouk Yalaoui, Ahmed Mhadhbi. Makespan minimization on a two-machine flowshop with an availability constraint on the first machine. International Journal of Production Economics, Elsevier, 2015, 164, pp.95-104. ⟨10.1016/j.ijpe.2015.02.025⟩. ⟨hal-02497215⟩

Share

Metrics

Record views

38