单机总误工问题的分解启发式算法

为了解决单机总误工问题,提出了一种分解启发式算法。该算法是将解决这一问题最好的优化方法(Lawler分解算法)和非常有效的启发式算法(MDD)有机结合,在每一次迭代过程中均利用MDD算法估计Lawler分解算法中不同分解位置对应的误工,确定具有最大加工时间的工件在获得最小总误工的分解位置处加工。从理论上证明了该算法得到的排序结果优于MDD排序,仿真实验也表明该算法得到的结果99%以上为最优排序,而且可以求解多达1000个工件的问题。该算法以较短的时间获得了接近最优排序的结果,算法性能优良。

Decomposition heuristic algorithm for the total tardiness problem

A decomposition heuristic algorithm was developed to solve the single machine total tardiness problem. The algorithm combines the decomposition algorithm proposed by Lawler, the most successful optimizing algorithm to date for this problem, with the very efficient modified due date (MDD) algorithm. At each iteration of the procedure, MDD algorithm is used to estimate the total tardiness corresponding to each decomposition position of the Lawler decomposition algorithm with the job with the longest processing time fixed to the position yielding the minimum total tardiness. The algorithm theoretically proves to be superior to MDD algorithm. Simulation results show that the algorithm generates solutions with an optimal sequence ratio larger than 99%. The algorithm can solve a problem with up to (1 000) jobs with an approximate solution close to the optimal sequence in short time.