 A branch and bound and parallel genetic algorithm for the job shop scheduling problem with blockingAbdelhakim AitZai, Brahim Benmedjdoub and Mourad Boudhar International Journal of Operational Research, 2012, vol. 14, issue 3, 343-365 Abstract: In this paper, we study the job shop scheduling problem with blocking where the objective is to minimise the maximum completion time (i.e. makespan). To solve this non-polynomial-hard problem, we propose three algorithms. First, we propose a combination of a branch and bound algorithm with alternative graphs. We investigate the performance of this proposal to get an optimal solution in a reasonable time. Next, we develop two methods based on genetic algorithms (GAs): sequential and parallel GAs. In the former, we propose two different ways to encode the individuals: binary code using alternative arcs and priority rules code. In the latter, we propose a parallelisation of the GA, where the master computer is dedicated to the steps of selection, crossover and mutation, and the other computers (slaves) are concerned with the computation of the individuals fitness. At the end of this paper, we discuss the different results. Keywords: job shop scheduling; blocking constraints; alternative graphs; B%B; branch and bound; parallel genetic algorithms; operational research. (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:ids:ijores:v:14:y:2012:i:3:p:343-365 Access Statistics for this article More articles in International Journal of Operational Research from Inderscience Enterprises Ltd |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.