带机器准备时间的机器覆盖问题的在线、半在线算法  

Online,semi-online algorithms for machine covering with non-simultaneous machine available time

作　　者：蔡圣义[1] 

机构地区：[1]温州大学数学与信息科学学院,浙江温州325035

出　　处：《高校应用数学学报（A辑）》2007年第3期285-292,共8页Applied Mathematics A Journal of Chinese Universities(Ser.A)

基　　金：国家自然科学基金(10271110;60674071);温州师范学院课题经费(2001Z06)

摘　　要：研究以极大化最小机器负载为目标的机器带准备时间的同型机排序问题.证明了LS算法是求解该问题的最好的在线算法,它的最坏情况界为1/m.同时给出了求解两台机的预先知道工件最大加工时间,预先知道工件集的总加工时间以及预先知道工件从大到小到达这三种情形下最好的半在线算法,这三个算法的最坏情况界分别为2/3,2/3以及3/4.The paper considers the parallel machine scheduling problem with non-simultaneous machine available time and the object is to maximize the earliest machine completion time. In online version, the worst-case ratio of LS being 1/m is proved, so LS is the optimal algorithm for this problem. Three different semi-online conditions -- the largest processing time known in advance, the total processing time known in advance and the jobs ordered in non-increasing processing time are investigated. For each problem the optimal algorithm （worst-case ratio 2/3, 2/3, 3/4） for two machine case is presented.

关 键 词：排序问题 在线 半在线 最坏情况界 

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