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

Open-Shop Problem with Delays──The Worst Performance Analysis

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

An open shop scheduling problem with delays is considered in this paper. For arbitrary number of machines, a simple greedy algorithm can produce a schedule whose makespan is at most twice that of the optimal one in the worst case in general. The worst case ratio is proved to be for m=2 (m is the number of machines).