Skip to Main content Skip to Navigation
Journal articles

Two-machine job shop problem under availability constraints on one machine: Makespan minimization

Abstract : This paper considers a two-machine job shop scheduling problem with availability constraints on one machine in order to minimize makespan. We consider the problem when unavailability periods are known in advance and operations are non-preemptive. First, two mixed integer linear programming models MILP1, MILP2 are presented. Secondly, we introduce some properties concerning the optimality of Jackson’s algorithm under availability constraints. Consequently, new lower bounds are provided and an upper bound is obtained using heuristics based on Jackson’s rule. Then, a branch and bound algorithm (B&B) incorporating these bounds is proposed to solve the problem. The performances of the proposed approaches are evaluated by comparing their solutions through well known benchmarks. Computational results prove the efficiency of the proposed B&B.
Document type :
Journal articles
Complete list of metadatas

https://hal-utt.archives-ouvertes.fr/hal-02525216
Contributor : Daniel Gavrysiak <>
Submitted on : Monday, March 30, 2020 - 6:22:55 PM
Last modification on : Tuesday, March 31, 2020 - 2:01:51 AM

Identifiers

Collections

ROSAS | UTT | CNRS

Citation

Mourad Benttaleb, Faicel Hnaien, Farouk Yalaoui. Two-machine job shop problem under availability constraints on one machine: Makespan minimization. Computers & Industrial Engineering, 2018, 117, pp.138-151. ⟨10.1016/j.cie.2018.01.028⟩. ⟨hal-02525216⟩

Share

Metrics

Record views

19