关键词: 邻域搜索, 启发式规则, 遗传算法, 种群初始化, 作业车间调度

Abstract: For the job shop scheduling optimization problem, population initialization method and neighborhood search mechanism of its solution genetic algorithm are studied. To improve the quality of the initial population, heuristic initialization method that combining active scheduling, non-delay scheduling with heuristic rules is adopted. Neighborhood structure is constructed based on the critical path. Neighborhood search moving of the key operations is carried out based on operation-based encoding to avoid infeasible solutions and chromosome testing-repair work. Different neighborhood moving for the first, inside and last operations of the operation block is defined respectively. Based on the active decoded gantt chart, to standardize the chromosome by the operation start time, and get the chromosome that the operation’s position order is in accordance with the actual processing order on machines. For the expansion of the range of operation neighborhood search, the right moving is operated on the gantt chart, and to standardize the chromosome reversely by the operation completion time. Neighborhood search is implemented on the two standardized chromosome individuals obtained by forward and reverse standardization. Benchmark problems are applied to test the proposed algorithm, and effectiveress is verified.

Key words: Genetic algorithm, Heuristic rules, Job shop scheduling, Neighborhood search, Population initialization