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

Mourad Benttaleb 1 Faicel Hnaien 1 Farouk Yalaoui 1
1 LOSI - Laboratoire d'Optimisation des Systèmes Industriels
ICD - Institut Charles Delaunay
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.
Keywords : job shop scheduling availability constraints mixed integer linear programming branch and bound makespan
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

ROSAS | UTT

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⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

3

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD