带服务等级约束的单位长度工件排序问题  

Schedule Unit-length Jobs on Parallel Machines with GOS Levels

作　　者：胡觉亮[1] 刘晨[1] 

机构地区：[1]浙江理工大学理学院,杭州310018

出　　处：《浙江理工大学学报（自然科学版）》2008年第1期99-102,共4页Journal of Zhejiang Sci-Tech University(Natural Sciences)

基　　金：国家自然科学基金(10671177);浙江省自然科学基金(Y605316)

摘　　要：研究带服务等级约束的等工件长度排序问题。对该问题的离线情形,给出了求解最优解的线性时间算法。对带有两个服务等级的在线情形,证明了该问题的下界为3/2,并给出了两台机上的最优在线算法。The parallel machine scheduling problem for unit-length jobs with a grade of service （GOS） levels is discussed in this paper. For the offline version, an optimal linear algorithm is presented. For the online version with two GOS levels, it is shown that the lower bound is 3/2. An optimal online algorithm for two-machine case is also proposed.

关 键 词：排序问题 离线 在线 近似算法 竞争比 

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