摘要
把工件之间不带前后约束的延误排序的后移算法移植到带有前后约束的情况,提出一个多项式时间的近似算法．这个算法可以快速地得到这种延误问题的近似解．
For the total tardiness scheduling with precedence constraints, an approximation algorithm with polynomial complexity was presented by transplanting the backward-shift algorithm of the case without precedence constraints. The new algorithm can get an approximation solution for the scheduling quickly.
出处
《华东师范大学学报（自然科学版）》
CAS
CSCD
北大核心
2007年第1期51-55,共5页
Journal of East China Normal University(Natural Science)
基金
国家自然科学基金(10371071)
关键词
延误问题
Emmons条件
前后约束
近似算法
total tardiness scheduling
Emmons conditions
precedence constraints
approximation algorithm
