Multiple route job shop scheduling using particle swarm optimisation approach

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.