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

摘要： 针对柔性作业车间调度问题,以优化最大完工时间为目标,提出一种融合改进邻域结构的混合算法。柔性作业车间调度问题机器选择是工序排序优化的前提和基础,因此,将邻域结构分两级进行：第一级跨机器移动工序,第二级同机器移动工序。对同机器移动工序方面进行了改进,结合关键工序的类型定义了相应的移动操作,对已有邻域结构进行了无效移动的精简和有效移动的扩展,提高了邻域结构的精准有效性。给出了邻域结构相应的近似移动评价方法,综合考虑算法的全局搜索能力和局部搜索能力,设计了柔性作业车间调度问题求解算法。通过采用基准算例进行测试,验证了所提方法的有效性。

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