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

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