The hybrid heuristic genetic algorithm for job shop scheduling

Scheduling for the job shop is very important in both fields of production management and combinatorial optimization. However, it is quite difficult t o achieve an optimal solution to this problem with traditional optimization methods owing to the high computational complexity (NP-hard). Genetic algo rithms (GA) have been proved to be effective for a variety of situations, i ncluding scheduling and sequencing. Unfortunately, its efficiency is not sa tisfactory. 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 CA is proposed for problem n/m/G/C-max, where the scheduli ng rules, such as shortest processing time (SPT) and MWKR, are integrated i nto the process of genetic evolution. In addition, the neighborhood search technique (NST) is adopted as an auxiliary procedure to improve the solutio n 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. (C) 2001 Elsevier Sc ience Ltd. All rights reserved.