带重入的单台机排序问题(英文)  

Single Machine Scheduling with Re-entrance

作　　者：井彩霞[1] 钱省三[1] 唐国春[2] 

机构地区：[1]上海理工大学管理学院,上海200093 [2]上海第二工业大学经济管理学院,上海201209

出　　处：《运筹学学报》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).

摘　　要：本文考虑带重入的单台机排序问题。重入是指每个工件在机器上加工不止一次.通过把重入模型转化为带平行链约束的排序问题,我们成功地获得了单机重入问题的两个目标函数的多项式时间最优算法,一个是总带权完工时间∑ω_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.

关 键 词：运筹学 排序 多项式时间算法 转化 重入 总带权完工时间 最大费用 

分 类 号：O223[理学—运筹学与控制论] TP316[理学—数学]