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

Abdelhakim AitZai and Mourad Boudhar

International Journal of Operational Research, 2013, vol. 16, issue 1, 14-37

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. (search for similar items in EconPapers)
Date: 2013
References: Add references at CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.inderscience.com/link.php?id=50538 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ids:ijores:v:16:y:2013:i:1:p:14-37

Access Statistics for this article

More articles in International Journal of Operational Research from Inderscience Enterprises Ltd
Bibliographic data for series maintained by Sarah Parker ().