Title: A branch and bound and parallel genetic algorithm for the job shop scheduling problem with blocking

Authors: Abdelhakim AitZai; Brahim Benmedjdoub; Mourad Boudhar

Addresses: Faculty of Electronics and Computer Science (FEI), Department of Computer Science, USTHB University, BP 32 El Alia, Algiers, Algeria ' Faculty of Mathematics, USTHB University, BP 32 El Alia, Algiers, Algeria ' Faculty of Mathematics, USTHB University, BP 32 El Alia, Algiers, Algeria

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.

DOI: 10.1504/IJOR.2012.047094

International Journal of Operational Research, 2012 Vol.14 No.3, pp.343 - 365

Published online: 11 Jan 2015 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article