两台同型机多阶段维护调度问题的若干结果  

SOME RESULTS OF SCHEDULING WITH MULTI-PHASE MAINTENANCES ON TWO IDENTICAL MACHINES

作　　者：孙凯彪[1] 李金权[1] 王加银[1] 

机构地区：[1]北京师范大学数学科学学院,北京100875

出　　处：《北京师范大学学报（自然科学版）》2008年第4期343-347,共5页Journal of Beijing Normal University(Natural Science)

基　　金：国家"九七三"计划资助项目(2002CB312200);国家自然科学基金资助项目(60474023)

摘　　要：研究了2种类型的机器维护:一种为周期性维护,另一种为决策维护.对于周期维护最小化时间表长问题,证明了经典的FFD算法是一个很好的启发式算法,并且得到了该算法的一个上界.对于决策维护最小化总完工时间问题,分析了SPT算法的界.特别地,对于单机并且机器仅需要2次维护的情况,给出SPT算法的界不超过11/9.Two types of machine maintenance were investigated in this paper. One was periodic maintenance, and the other was decision maintenance. For the make-span minimization problem on two machines with periodic maintenance, it was shown that FFD algorithm was an efficient algorithm. For the total completion time minimization problem on two machines with decision maintenance, the worst-case analysis of SPT algorithm was given. For a single machine, if the SPT schedule had three batches, it was pointed out that the worst-case bound was not larger than 11/9.

关 键 词：调度 同型机 时间表长 总完工时间 机器维护 

分 类 号：O224[理学—运筹学与控制论] TP308[理学—数学]