Two-machine job shop problem under availability constraints on one machine: Makespan minimization - Archive ouverte HAL Access content directly
Journal Articles Computers & Industrial Engineering Year : 2018

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

(1) , (1) , (1)
1

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.
Not file

Dates and versions

hal-02525216 , version 1 (30-03-2020)

Identifiers

Cite

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⟩

Collections

CNRS UTT LOSI
14 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More