总延误问题顺时安排法的性能比

The Performance Ratio of the Time Forward Algorithm for the Total Tardiness Problem

给定一组工件的加工时间与工期，要求确定这些工件在一台机器上的加工排列，使相应的总延误达到最小，这就是总延误问题，该问题在近年已被证明是ＮＰ困难的。由Ｗｉｌｋｅｒｓｏｎ和Ｉｒｗｉｎ（１９７１），林诒勋（１９８３）等所研究的顺归安排法能得到相邻交换意义下的局部解。在本文中，我们进一步证明该算法能得到前移邻域意义下的局部解，并确定了该算法的性能比。

Given a set of jobs, together with the processing time and the due date for each job, thetotal tardiness problem asks to find a processing sequence on one machine, which minimizesthe sum of the tardinesses of all jobs. This problem has been shown to be NP-hard. Asa heuristic for the total tardiness problem, the time forward algorithm was presented byWilkerson & Irwin (1971), Lin (1983), etc. In this paper, we show that the job sequenceproduced by the time forward algorithm is locally optimal with respect to the forward shiftneighbourhood, and we also obtain the performance ratio of the algorithm.