A hybrid shifting bottleneck procedure algorithm for the parallel‐machine job‐shop scheduling problem

A hybrid shifting bottleneck procedure algorithm for the parallel‐machine job‐shop scheduling problem

0.00 Avg rating0 Votes
Article ID: iaor2012138
Volume: 63
Issue: 2
Start Page Number: 168
End Page Number: 182
Publication Date: Feb 2012
Journal: Journal of the Operational Research Society
Authors: ,
Keywords: graphs, heuristics: tabu search
Abstract:

In practice, parallel‐machine job‐shop scheduling (PMJSS) is very useful in the development of standard modelling approaches and generic solution techniques for many real‐world scheduling problems. In this paper, based on the analysis of structural properties in an extended disjunctive graph model, a hybrid shifting bottleneck procedure (HSBP) algorithm combined with Tabu Search (TS) metaheuristic algorithm is developed to deal with the PMJSS problem. The original‐version shifting bottleneck procedure (SBP) algorithm for the job‐shop scheduling (JSS) has been significantly improved to solve the PMJSS problem with four novelties: (i) a topological‐sequence algorithm is proposed to decompose the PMJSS problem in a set of single‐machine scheduling (SMS) and/or parallel‐machine scheduling subproblems; (ii) a modified Carlier algorithm based on the proposed lemmas and the proofs is developed to solve the SMS subproblem; (iii) the Jackson rule is extended to solve the PMS subproblem; (iv) a TS metaheuristic algorithm is embedded under the framework of SBP to optimise the JSS and PMJSS cases. The computational experiments show that the proposed HSBP is very efficient in solving the JSS and PMJSS problems.

Reviews

Required fields are marked *. Your email address will not be published.