文献类型：期刊文献

中文题名：总延误问题顺时安排法的性能比

英文题名：The Performance Ratio of the Time Forward Algorithm for the Total Tardiness Problem

作者：刘朝晖[1]

机构：[1]华东理工大学应用数学研究所

年份：1997

卷号：1

期号：1X

起止页码：89

中文期刊名：运筹学学报

外文期刊名：OR TRANSACTIONS

收录：CSCD:【CSCD2011_2012】；

基金：国家自然科学基金

语种：中文

中文关键词：时间表;总延误问题;近似算法;顺时安排法

外文关键词：scheduling, total tardiness problem, approximation algorithm, time forward algorithm, performance ratio

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