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