摘要
考虑带机器准备时间的已知工件总加工时间半在线问题。首先考虑P2,ri|sum|Cmin问题,给出Prsum算法并证明此算法的竞争比为23,且是最优算法;然后考虑Q2,ri|sum|Cmax问题,给出Qrsum算法并证明此算法的竞争比为2,同时给出此问题的一个下界1+3～(1/2)/2。显然Qrsum算法的竞争比与最优算法的竞争比之差小于0.048 2。
In this paper, it investigate a semi -online version on two machines with non -simultaneous machine available time where the total processing time of jobs is known in advance. It first consider P2, ri｜ sum｜ Cmin problem, 3 we give a Prsum algorithm and prove its competitive ratio is 3/2- which is optimal. Then it consider Q2, ri ｜ sum ｜ Cmax problem, it propose a Qrsum algorithm and prove its competitive ratio is √2 It also claim that the lower bound of this 1 ＋√3/2- It is obvious that the gap between the competitive ratio of Qrsum algorithm and the optimal value problem isis not greater than 0.048 2.
出处
《南昌大学学报（理科版）》
CAS
北大核心
2010年第1期24-32,共9页
Journal of Nanchang University(Natural Science)
基金
江西省自然科学基金资助项目(2007GZS2126)
关键词
竞争比
半在线
排序
competitive ratio
semi - online
scheduling
