混合多目标算法用于柔性作业车间调度问题

Hybrid Multi-objective Algorithm for Solving Flexible Job Shop Scheduling Problem

在生产调度领域,柔性作业车间调度问题是一个非常重要的优化问题。大多数研究通常优化的目标只是最大完工时间,而在实际中,往往要考虑多个目标。因此,提出了一种新的混合多目标算法用于解决柔性作业车间调度问题,其中考虑了3个目标,分别是:最大完工时间、机器总负载和瓶颈机器负荷。算法设计了有效的编码方式和遗传算子,并采用非支配近邻免疫算法求解非支配最优解。为了提高算法性能,提出了3种不同的局部搜索策略,并将其结合在多目标算法中。在多个数据集上的实验对比结果表明,所提算法优于其它代表性的算法。此外,实验结果还验证了局部搜索技术的有效性。

The flexible job shop scheduling problem is one of the most important optimization problems in the field of production scheduling, due to its complexity and practical applications in real life. Most studies focus on only one objec- tives-the makespan that is the total time required to complete all jobs. However, a single objective may be insufficient for real applications. Therefore,a new hybrid multi-objective algorithm was proposed for solving the flexible job shop scheduling problem（FJSP） with three objectives,including the makespan, total workload, and critical workload. Effec- tive chromosome representation and genetic operators are introduced. The nondominated neighbor immune algorithm is used to search for Pareto optimal solutions. To improve the search performance, three different local search strategies were designed and combined in the multi-objective algorithm. The computational results on several data sets show that the proposed algorithm outperforms other representative effectiveness of local search strategies. algorithms in general. In addition, the experiments validate the