摘要
研究了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.
出处
《北京师范大学学报（自然科学版）》
CAS
CSCD
北大核心
2008年第4期343-347,共5页
Journal of Beijing Normal University(Natural Science)
基金
国家"九七三"计划资助项目(2002CB312200)
国家自然科学基金资助项目(60474023)
关键词
调度
同型机
时间表长
总完工时间
机器维护
scheduling
identical machine
make-span
total completion time
machine maintenance
