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

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