自由作业问题的一种启发式算法及最坏性能比分析

研究具有准备时间的自由作业问题，给出一种简单的启发式算法，证明 在此启发式算法上，最坏性能比是2－1／m（其中m是机器的参数），且上界是紧的。从而证明了对该问题的猜想：即在贪婪算法的情况下其最坏性能比是2－1／m（其中m是机器的台数），且上界是紧的。特别当m＝2时，具有准备时间的自由作业问题，利用该启发式算法得到最坏性能比是3／2，其上界也是紧的。     

具有延迟时间的自由作业排序问题——最坏性能比分析

研究一类具有延迟时间的自由作业问题，证明在机器台数任意的情况下，一个简单的贪婪算法的最坏性能比不超过2。特别当m＝2时，证明了该算法的最坏性能比为3／2，其中m为机器的台数。     

具有优先权的自由作业时间表问题研究

研究了具有优先权的自由作业时间表问题，在工件具有准备时间的条件下，给出一种新的启发式算法，其最坏性能比不超过2，猜想该算法的紧界是2—2／(m 1)，其中m是机器的台数，证明在3台机器的情况下，该算法的最坏性能比为3／2，且上界是紧的。     

m台机器上流水作业时间表问题的复杂性及一种新的启发式算法

研究流水作业时间表问题，在具有延迟时间的条件下证明该问题是强NP-困难的．给出一种新的启发式算法，并证明该算法的最坏性能比是(m 1)/2，且上界是紧的．     

流水作业问题的一个启发式算法

讨论具有延迟时间的流水作业问题,并提出了解决该问题的一种启发算法,证明了其最坏性能比是（m 1）/2,并且上界是紧的,特别当m=2,即两台机器上具有延迟时间的流水作业问题时,其最坏性能比是3/2,最后将所得结论推广到FmID2问题,即加工时间相等且延迟时间只取两上值的流水作业问题,其最坏性能比也是m 1/2。     

带运输时间和单自动机的流水作业排序

本文研究n个工件在2台机器上加工的流水作业排序问题。同一工件在一台机器上完工后在下一台机器加工之前有一个时间间隔即运输时间,所有运输时间都是由单自动机来完成运输,同一时间自动机只能运输一个工件,本文主要研究所有加工时间均匀等于1的情况下该问题的复杂性,并给出新的启发式算法,证明该算法的最坏性能比是3/2,且上界是紧的。     

求解AFS问题的两种启发式算法在最坏情况下性能比上界的可达性研究

对文献[2]中提出的求AFS问题的次优解的两个简单易行的启发式算法及其品性进行了进一步的研究。由于已证明了其在最坏情况下性能比Cmax（H）／Cmax的上界不去超过2,本文用两个典型的例子证明：对这两种算法,这一上界是可达的。     

机器具有不可用时间间隔的两机无等待流水车间调度问题的求解性质

研究工件具有无等待约束,并且只有一台机器具有不可用时间间隔的两机流水车间调度问题.文中给出使用GGA算法得到问题最优解的条件,并证明问题的复杂性,分析将GGA算法作为问题启发式算法的最坏性能比范围.     

排序问题Fm‖Cmax的几种启发式算法在最坏情况下性能比上界的可达性研究

Ｇｏｎｚａｌｅｚ和Ｓａｈｎｉ已证明：当ｍ≥３时，排序问题ＦｍＣｍａｘ是ＮＰ困难问题，没有好算法。因此，很多学者提出了多种简单易行的启发式方法求这类问题的次优解，且对其中的ＧＳ算法和ＲＳ算法证明了在最坏情况下性能比Ｃ＊ｍａｘ（Ａ）／Ｃ＊ｍａｘ的上界不超过｛ｍ／２｝＊。本文用同一例子证明，对这两种算法，这一上界是可达的。     

Flow shop排序问题F2｜prmu｜∑ωjCj的一个启发式算法

给出Flow shop排序问题F2|prmu|∑ωjCj的一个启发式算法，其最坏情况的界为2，且是紧界。此外，还讨论了它的三种多项式可解的条件。