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

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

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

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

贪婪算法与最坏性能比分析

研究了具有准备时间和延迟时间的自由作业问题，通过引入虚拟工作，证明该问题是强NP－困难的，提出了解决这个问题的一种方法－－贪婪算法，并证明了在只有2台机器的情况下，具有准备时间和延迟时间的自由作业问题使用贪婪算法，其最坏性能比是3／2。     

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

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