Two-machine job shop problem under availability constraints on one machine: Makespan minimization. (March 2018)

• Record Type: Journal Article
• Authors: Benttaleb, Mourad; Hnaien, Faicel; Yalaoui, Farouk
• Is Part Of: Computers & industrial engineering. Volume 117(2018)
• Page Start: 138
• Page End: 151
• Publication Date: 2018-03
• Subjects: Scheduling problem -- Job shop -- Availability constraint -- Makespan -- Mixed integer linear programming -- Branch-and-bound; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2018.01.028
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: We consider a two machine job shop scheduling problem with availability constraints. New properties concerning the optimality of Jackson's rule and considering availability constraints are provided. Two mathematical models and branch and bound method are proposed. Results indicate that the proposed branch and bound is efficient for the considered problem. 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.