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

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