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

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

作　　者：杜玉祥[1,2] 杜东雷[1,2] 张国川 

机构地区：[1]泰安师范专科学校 [2]中国科学院应用数学所

出　　处：《高校应用数学学报（A辑）》1997年第2期191-196,共6页Applied Mathematics A Journal of Chinese Universities(Ser.A)

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

关 键 词：自由作业排序 贪婪算法 最坏性能比 排序 

分 类 号：O223[理学—运筹学与控制论]