Ant colony optimisation with parameterised search space for the job shop scheduling problem

摘要

The job-shop scheduling problem (JSSP) is known to be NP-hard. Due to its complexity, many metaheuristic algorithm approaches have arisen. Ant colony metaheuristic algorithm, lately proposed, has successful application to various combinatorial optimisation problems. In this study, an ant colony optimisation algorithm with parameterised search space is developed for JSSP with an objective of minimising makespan. The problem is modelled as a disjunctive graph where arcs connect only pairs of operations related rather than all operations are connected in pairs to mitigate the increase of the spatial complexity. The proposed algorithm is compared with a multiple colony ant algorithm using 20 benchmark problems. The results show that the proposed algorithm is very accurate by generating 12 optimal solutions out of 20 benchmark problems, and mean relative errors of the proposed and the multiple colony ant algorithms to the optimal solutions are 0.93% and 1.24%, respectively.