可移动周期性维护排序问题的算法研究

对于周期性维护的两台同型机排序问题,每台机器在进行时长不超过T的加工后需进行时长为t的维护,可在两台机器中任选一台加工工件,加工过程不可中断,且不能在维护前后加工同一工件,目标为极小化工件最大完工时间,证明了其不存在最坏情况比小于1+t T的多项式时间近似算法,除非P=NP。同时给出了该问题的近似算法,证明了其最坏情况比不超过f(t/T)。