Minimising the makespan in the two-machine job shop problem under availability constraints

Abstract : Classical scheduling problem assumes that machines are available during the scheduling horizon. This assumption may be justified in some situations but it does not apply if maintenance requirements, machine breakdowns or other availability constraints have to be considered. In this paper, we treat a two-machine job shop scheduling problem with one availability constraint on each machine to minimise the maximum completion time (makespan). The unavailability periods are known in advance and the processing of an operation cannot be interrupted by an unavailability period (non-preemptive case). We present in our approach properties dealing with permutation dominance and the optimality of Jackson's rule under availability constraints. In order to evaluate the effectiveness of the proposed approach, we develop two mixed integer linear programming models and two schemes for a branch and bound method to solve the tackled problem. Computational results validate the proposed approach and prove the efficiency of the developed methods.
Document type :
Journal articles
Complete list of metadatas

https://hal-utt.archives-ouvertes.fr/hal-02311035
Contributor : Jean-Baptiste Vu Van <>
Submitted on : Thursday, October 10, 2019 - 4:11:20 PM
Last modification on : Friday, October 11, 2019 - 1:31:03 AM

Identifiers

Collections

Citation

Mourad Benttaleb, Faicel Hnaien, Farouk Yalaoui. Minimising the makespan in the two-machine job shop problem under availability constraints. International Journal of Production Research, Taylor & Francis, 2018, 57 (5), pp.1427-1457. ⟨10.1080/00207543.2018.1489160⟩. ⟨hal-02311035⟩

Share

Metrics

Record views

3