单机总误工排序问题的启发式算法的性能扩张方法

Performance-extending approaches for total tardiness scheduling problem on one machine

对于单机总误工问题,分解算法是迄今最有效的最优排序算法,但只能求解100个工件的小规模问题。现有启发式算法均能在数秒内产生数千工件的加工方案。为通过逐渐增加启发式算法的计算时间来换取尽可能好的排序性能,该文将分解算法转换为树搜索问题。节点的性能评价函数由2部分组成:一是用修正工期(M DD)规则预测总误工时间;二是根据实验拟合的经验公式定义惩罚函数对预测进行修正。通过控制被保留的节点数目限制该算法的时间复杂度。实验结果表明,这种处理方法能够根据需要在计算时间和排序性能之间进行有效的权衡,并且对于大规模问题,该算法能够在可接受的时间内得到较好的排序结果。

The total tardiness problem on one machine is one of the important scheduling problems. The decomposition algorithm is, up to now, the best optimization algorithm for the problem, however, it can only solve problems with no more than 100 jobs. Various heuristics have been developed which can solve large-scale problems within several seconds. This paper describes how to obtain better scheduling performance at the expense of longer CPU times using the decomposition algorithm with a search tree. A function based on the MDD algorithm and empirical formulas for specific problems is used to evaluate node values. The time complexity of the algorithm is controlled by properly setting the number of candidate nodes. Extensive experiments show that the method balances the CPU time and the scheduling performance to obtain good results within acceptable times in large-scale problems.