带准备时间的自由作业排序问题——最坏性能比分析

OPEN SHOP SCHEDULING PROBLEM WITH RELEASE TIMES——THE WORST CASE ANALYSIS

本文研究了一类自然的排序问题，带准备时间的自由作业（ＯｐｅｎＳｈｏｐ）排序．在机器台数任意的情况下，证明了一个简单的贪婪算法的最坏性能比不超过２，并猜想该算法的紧界为２－１ｍ，其中ｍ为机器台数．特别当ｍ＝２时。

An open shop scheduling problem with release times is considered in this paper. For arbitrary number of machines, a simple greedy algorithm can produce a schedule whose makespan is at most 2 times that of the optimal one in the worst case in general. However, we conjecture that the tight bound is 2-1m (m is the number of machines). The worst case ratio is proved to be 3/2 for m=2.