Solving the job shop scheduling problem using the imperialist competitive algorithm

摘要

This paper deals with the Job Shop Scheduling Problem with the minimization of makespan as the objective.A novel meta-heuristic named imperialist competitive algorithm (ICA) is adopted to solve the problem.Since appropriate design of the parameters has a significant impact on the performance of the algorithm,the parameters were chosen based on orthogonal test.A local search strategy based on critical path and critical block was used to improve the performance of the algorithm.At last the algorithm was tested on a set of standard benchmark instances,and the computational results showed that the algorithm proposed performed well in both convergence rate and better global optima achievement.