An enhanced genetic algorithm with simulated annealing for job-shop scheduling

Abstract

The Job-Shop Scheduling Problem (JSSP) is one of the most difficult problems, as it is classified as NP-Hard problem. The main objective of the JSSP is to find a schedule of operations that can minimize the maximum completion time (called makespan) that is the completed time of carrying total operations out in the schedule for n jobs and m machines. In many cases, the combination of goals and resources exponentially increases the search space, and thus the generation of consistently good scheduling is particularly difficult, because we have a very large combinatorial search space and precedence constraints between operations. Exact methods such as the branch and bound method and dynamic programming take considerable computing time to obtain the optimum solution. In order to overcome this difficulty, it is more sensible to obtain a good solution near the optimal one. Stochastic search techniques such as evolutionary algorithms can be used to find a good solution. In this paper we proposed a new method for solving job-shop scheduling problem using hybrid Genetic Algorithm (GA) with Simulated Annealing (SA). This method introduces a reasonable combination of local search and global search for solving JSSP.

Keywords: Job-shop scheduling, genetic algorithm, simulated annealing, local search, global search