Title: Multiple route job shop scheduling using particle swarm optimisation approach

Authors: Hamid Reza Golmakani; Ali Reza Birjandi

Addresses: Industrial Engineering Department, Tafresh University, Tafresh, Iran ' Industrial Engineering Department, Tafresh University, Tafresh, Iran

Abstract: Multiple-route job shop scheduling problem (MRJSP) is a generalisation of job shop scheduling problem in which each job may have more than one route for its production and the numbers of operations associated to the alternative routes of a job are not necessarily equal. MRJSP is recognised to be extremely difficult because of its combinatorial nature of integer optimisation and the large size of the real problem, necessitating the use of meta-heuristic approaches for its solution. In this paper, mathematical formulation of MRJSP is first presented. Then, an approach based on particle swarm optimisation (PSO) is proposed to minimise makespan. The approach tackles the two major sub-problems in MRJSP, namely, the route selection and the sequencing sub-problems. In order to evaluate the effectiveness of the proposed approach, 90 problems (in small, medium, and large size) are designed and solved using the proposed approach. The problems are also solved using some dispatching rules and comparisons are provided. In addition, 43 known benchmarking problems are solved using the proposed approach and their solution are compared with optimal solutions. The computational results show that the proposed approach generates high-quality schedules in a timely fashion.

Keywords: multiple routes; job shop scheduling; makespan; particle swarm optimisation; PSO; route selection; sequencing; dispatching rules.

DOI: 10.1504/IJPM.2014.059551

International Journal of Procurement Management, 2014 Vol.7 No.2, pp.119 - 144

Published online: 30 May 2014 *

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