A Hybrid Simulated Annealing for Job Shop Scheduling Problem

Abstract

The Job Shop Scheduling Problem (JSSP) arises in the context of high-performance computing and belongs to the NP-hard combinatorial optimization problems. The purpose of JSSP is to find the order of execution of a set of jobs on a group of machines, subject to certain precedence and resource availability constraints. The objective in this problem is minimizing the makespan that is the time elapsed from the starting time of the first job until the completion time of the last job. In this paper, a novel hybrid algorithm named AntGenSA for solving JSSP is proposed. AntGenSA uses Ant Colony System (ACS), Simulated Annealing (SA), and Genetic Algorithm (GA). To assess the performance of this algorithm, it is executed in a parallel computer, using a set of instances proposed by Fisher-Thompson, Yamada-Nakano, Taillard, Lawrence, and Applegate-Cook. The evaluation of this algorithm was performed mainly by the quality of the solution but the execution time was measuring as well. The experimental results show that the performance of the parallel execution of AntGenSA is highly competitive with the state-of-the-art algorithms.