摘要
本文考虑带重入的单台机排序问题。重入是指每个工件在机器上加工不止一次.通过把重入模型转化为带平行链约束的排序问题,我们成功地获得了单机重入问题的两个目标函数的多项式时间最优算法,一个是总带权完工时间∑ω_jC_j,另一个是最大费用函数h_(max).
We consider single machine scheduling problems with re-entrance, in which every job visits the machine more than once. By transforming the re-entrant models into models subject to parallel chain precedence constraints, we successfully get the optimal polynomial time algorithms for two objective functions of the problem, one is the total weighted completion time ∑ωjCj, and the other is the maximum cost hmax.
出处
《运筹学学报》
CSCD
北大核心
2008年第2期84-87,共4页
Operations Research Transactions
基金
the National Natural Science Foundation of China(No.10371071,70731160015)
Shanghai Leading Academic Discipline Project(No.T0502)
The National Research Foundation for Program of Higher Education of China(No.20050252008).
关键词
运筹学
排序
多项式时间算法
转化
重入
总带权完工时间
最大费用
Operations research, scheduling, polynomial algorithm, transformation, re-entrant, total weighted completion time, maximum cost
