IFF算法求解顺序依赖的单机总权重拖期调度问题

转换(启动)时间是工业中带有清洗、更换物料工序的生产过程所需要的, 该时间一般很大程度上依赖于紧接工序. 这种环境下的调度问题都是工件顺序依赖的. 本文研究顺序依赖的单机总权重拖期调度问题, 为NP难的组合优化问题. 针对该问题, 提出了一种迭代的过滤-扇出算法(IFF), 算法以分支树的结构形式在解空间中搜索. 在算法中, 当分支移动不能改进根节点时, 重新产生有继承性的根节点, 使得算法继续进行. 根据问题特性, 提出了带序列片段重组和参考局部搜索的分支移动策略, 获得分支节点. 对文献中的120组数据的算法测试结果表明: 对大多数实例, IFF算法的计算结果优于或不劣于DE算法和DPSO算法的计算结果, 同时改进了42个实例的最好解.

IFF algorithm for the single machine total weighted tardiness scheduling problem with sequence dependent setup times

Setup (changeover) time is needed by the processes with cleaning or changing fixtures operations, which is strongly dependent on the immediately succeeding operation. The scheduling problems in this environment are sequence-dependent. This paper focuses on the single machine scheduling problem with sequence dependent setup times to minimize the total weighted tardiness, which is NP-hard. An iterated filter-and-fan algorithm (IFF) is proposed to solve it, which searches the solution space as a manner of a branch tree. In this algorithm, when the branching moves cannot improve the root solution, a new root solution with inherited features is generated, from which the search continues to work. According to the solution characteristic of the problem, a branching move strategy with sequence segment recomposing and referenced local search is proposed to generate branch nodes. The algorithm is tested by 120 instances from literature. The results show the solutions obtained by the IFF algorithm are better or not worse than those obtained by DE and DPSO algorithm for most instances. Besides, the best solutions for 42 instances are improved by the IFF algorithm.