Abstract: A hybrid method based on DBR(Drum-Buffer-Rope)and improved genetic algorithm is proposed for flexible job shop scheduling problems with the objective to minimize the makespan. In the initialization, a bottleneck machine recognition mechanism is proposed to improve initialization methods and to enhance the quality of the initial solution. In the process of computing based on the critical path, a bottleneck machines identification mechanisms and scheduling strategy are esfablished. In order to keep the excellent solutions in each generation, the external libraries is adopted. Benchmark problems are solved by the proposed algorithm, and computational results show that the proposed method is feasibility and effective.

Key words: flexible job shop scheduling, DBR theory, genetic algorithm, critical path

摘要： 针对柔性作业车间调度完工时间最小问题,提出一种结合DBR(鼓-缓冲器-绳子)理论和改进遗传算法的方法。在问题初始化时,建立瓶颈机器识别机制改善初始化方法,提高初始解的质量;在运算过程中依据关键路径建立瓶颈机器的识别机制和调度策略。为了更好保留每代中的优良解,采用外部精英库对优良解进行解保留。运用提出的算法求解基准测试问题,实验结果验证了算法的可行性和有效性。

关键词: 柔性作业车间调度, DBR理论, 遗传算法, 关键路径