柔性作业车间调度问题的集成启发式算法

Integrated Heuristic Algorithm for Flexible Job-shop Scheduling Problems

柔性作业车间调度问题,包括路径分配和加工排序2大子问题,是组合优化理论和实际生产管理的重要研究方向。作为传统作业车间调度的扩展,柔性作业车间调度问题的内在复杂性(强NP-Hard)使得传统的最优化方法难以有效求解。文章针对以多目标权重和最优为目标的柔性作业车间调度问题,提出基于过滤定向搜索的集成启发式算法,设计改进了节点分枝策略和局部/全局评价函数,能同时解决2大子问题。通过实例仿真,对算法性能进行比较分析和评价,结果表明了算法的可行性和有效性。

Flexible job-shop scheduling problem, containing routing sub-problem and sequencing sub-problem, is an important issue in both fields of combinatorial optimization and production operations. Being an extension of the classical job-shop scheduling problem, it presents additional complexity（NP-hard in strong sense）, which makes traditional optimization approaches difficult to achieve an optimal solution in reasonable computational time. In this paper, a filtered-beam-search based heuristic algorithm is proposed to solve the flexible job-shop scheduling problem with the objective of optimal weighted sum of multiple measure performances. The proposed algorithm makes improvement in the generation procedures of branches and the local/global evaluation functions, which makes it possible to solve two sub-problems, the performance of the proposed algorithm is evaluated and compared with those of other representative approaches through simulations, and the results demonstrate the feasibility and efficiency of the proposed algorithm.