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

A Heuristic Algorithm for Open-Shop Problem with Release Times and its Worst-Case Analysis

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

We consider the open-shop problem with release times .Given a simple heuristic algorithon,we discuss the worst -case performance, and prove that the worst-case performance is 2-1/m,so we have proved the conjecture for this problem. Especially, when m is equal to 2,the worst-case performance is 3/2,too. The tight is bound for both cases.