The hybrid heuristic genetic algorithm for job shop scheduling

The hybrid heuristic genetic algorithm for job shop scheduling

0.00 Avg rating0 Votes
Article ID: iaor2002207
Country: Netherlands
Volume: 40
Issue: 3
Start Page Number: 191
End Page Number: 200
Publication Date: Jul 2001
Journal: Computers & Industrial Engineering
Authors: , ,
Keywords: genetic algorithms, job shop
Abstract:

Scheduling for the job shop is very important in both fields of production management and combinatorial optimization. However, it is quite difficult to achieve an optimal solution to this problem with traditional optimization methods owing to the high computational complexity (NP-hard). Genetic algorithms (GA) have been proved to be effective for a variety of situations, including scheduling and sequencing. Unfortunately, its efficiency is not satisfactory. In order to make GA more efficient and practical, the knowledge relevant to the problem to be solved is helpful. In this paper, a kind of hybrid heuristic GA is proposed for problem n/m/G/Cmax, where the scheduling rules, such as shortest processing time (SPT) and MWKR, are integrated into the process of genetic evolution. In addition, the neighborhood search technique (NST) is adopted as an auxiliary procedure to improve the solution performance. The new algorithm is proved to be effective and efficient by comparing it with some popular methods, i.e. the heuristic of neighborhood search, simulated annealing (SA), and traditional GA.

Reviews

Required fields are marked *. Your email address will not be published.