关键词: 作业车间调度, 块结构邻域搜索, 遗传算法, 子代选择

Abstract: Aiming at the Job Shop Scheduling Problem (JSP) with the optimization objective of minimizing the maximum completion time,a neighborhood search algorithm based on critical operations,block structure neighborhood search algorithm was proposed.The structure generation process was carried on the operation sequence,which was operated based on the operation-based encoding.Utilizing the first operation or the end operation as the center of the block,the neighborhood individuals were generated by exchanging and moving the operations in the critical block.Then redundancy criterion was generated by analyzing the position relations between the central operations with intra-block operations in the operation sequence,which could reduce redundant neighborhood individuals.To improve the effectiveness of the entire population gene and the premature maturity of the delay algorithm,an improved selection mechanism named offspring selection mechanism was adopted.Simulation experiments on typical examples verified the effectiveness of the proposed algorithm.

Key words: job-shop scheduling problems, block structure neighborhood search algorithm, genetic algorithms, offspring selection