关键词: 柔性作业车间调度问题, 遗传算法, 邻域结构, 最大完工时间, 近似评价

Abstract:

Aiming at the Flexible Job Shop Scheduling Problem (FJSP) with the objective of optimizing the maximum completion time,a hybrid algorithm that incorporating improved neighborhood structure was proposed.Machine selection was the premise and basis of operation sequencing optimization in the FJSP.Therefore,the neighborhood structure was divided into two levels: the first-level neighborhood search was performed to move the operation across the machine,and the second-level neighborhood search was achieved by moving the operation on the current machine.Some improvements were made to the second-level neighborhood search.The movement was decided by the types of critical operations to achieve invalid move streamlining and effective move expansion.The accuracy and effectiveness of the existing neighborhood structures were improved.The approximate move evaluation method of the neighborhood structure was given.A hybrid FJSP solving algorithm was designed considering the global search ability and local search ability.The benchmark examples were used to test and verify the effectiveness of the proposed method.

Key words: flexible job shop scheduling problem, genetic algorithms, neighborhood structure, maximum completion time, approximate evaluation