Title: Parallel branch-and-bound and parallel PSO algorithms for job shop scheduling problem with blocking

Authors: Abdelhakim AitZai; 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

Abstract: In this paper, we deal with the resolution of the scheduling problem with blocking which is known to be non-polynomial-hard. The nature of the workshop defines the type of issue to treat: flow shop problem and job shop problem (JSP). A lot of researches are dedicated in the literature to the resolution of the flow shop problem, whereas not enough works are found concerning JSP. We have oriented our efforts in this paper to the resolution of JSP with blocking. For that, we propose three methods: a parallel version of a branch-and-bound method based on an implicit enumeration, a sequential particle swarm optimisation (PSO) and a parallel PSO. The first one is an exact method but the complexity of the problem makes it useless for more than 10 jobs × 10 machines. For that, we investigate in meta-heuristics which procure good scheduling in real time. A comparison of these methods is presented at the end of this paper.

Keywords: job shop scheduling; blocking constraints; alternative graphs; parallel branch-and-bound; parallel PSO; particle swarm optimisation; operational research.

DOI: 10.1504/IJOR.2013.050538

International Journal of Operational Research, 2013 Vol.16 No.1, pp.14 - 37

Published online: 29 Jul 2014 *

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