带机器准备时间的已知工件总加工时间半在线问题  

Semi-online Scheduling Problem with Non-simultaneous Machnie Avaliable Line and Known the Total Size

作　　者：罗润梓[1] 孙世杰[2] 何龙敏[2] 

机构地区：[1]南昌大学数学系,江西南昌330031 [2]上海大学数学系,上海200444

出　　处：《南昌大学学报（理科版）》2010年第1期24-32,共9页Journal of Nanchang University(Natural Science)

基　　金：江西省自然科学基金资助项目(2007GZS2126)

摘　　要：考虑带机器准备时间的已知工件总加工时间半在线问题。首先考虑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.

关 键 词：竞争比 半在线 排序 

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