Parallel branch-and-bound and parallel PSO algorithms for job shop scheduling problem with blocking
by Abdelhakim AitZai; Mourad Boudhar
International Journal of Operational Research (IJOR), Vol. 16, No. 1, 2013

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.

Online publication date: Tue, 29-Jul-2014

The full text of this article is only available to individual subscribers or to users at subscribing institutions.

 
Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.

Pay per view:
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.

Complimentary Subscribers, Editors or Members of the Editorial Board of the International Journal of Operational Research (IJOR):
Login with your Inderscience username and password:

    Username:        Password:         

Forgotten your password?


Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.

If you still need assistance, please email subs@inderscience.com