An Imperialist Competitive Algorithm for the Job Shop Scheduling Problems

Scheduling is assigning a set of tasks on resources in a time period, taking into account the time, capability and capacity constraints. The job shop scheduling problems are the most important problems in management science and combinatorial optimization. These problems belong to the family of NP-hard, in which they cannot be solved in polynomial time (unless P=NP). In this paper, a meta-heuristic algorithm is proposed for solving the job shop scheduling problems with the objective of minimizing makespan. A meta-heuristic approach called imperialist competitive algorithm which imitates the behavior of imperialistic competition is presented. This algorithm is constructed with countries, colonies and imperialists in which colonies and imperialists make the empires. The algorithm starts with initializing the countries and empires. In addition, the algorithm continues the search process by applying assimilation and revolution operators. To further improve the solution quality obtained by the imperialist competitive algorithm, simulated annealing is applied. A set of well-studied benchmarking instances obtained from the OR-Library is used to evaluate the performance of the proposed algorithm, and the computational results indicate its efficiency.