运筹学学报
運籌學學報
운주학학보
OR TRANSACTIONS
2008年
2期
84-87
,共4页
Jing Caixia%井彩霞%钱省三%唐国春
Jing Caixia%井綵霞%錢省三%唐國春
Jing Caixia%정채하%전성삼%당국춘
运筹学%排序%多项式时间算法%转化%重入%总带权完工时间%最大费用
運籌學%排序%多項式時間算法%轉化%重入%總帶權完工時間%最大費用
운주학%배서%다항식시간산법%전화%중입%총대권완공시간%최대비용
Operations research%scheduling%polynomial algorithm%transformation%re-entrant%total weighted completion time%maximum cost
本文考虑带重入的单台机排序问题,重入是指每个工件在机器上加工不止一次.通过把重入模型转化为带平行链约束的排序问题,我们成功地获得了单机重入问题的两个目标函数的多项式时间最优算法,一个是总带权完工时间∑ωjCj,另一个是最大费用函数hmax.
本文攷慮帶重入的單檯機排序問題,重入是指每箇工件在機器上加工不止一次.通過把重入模型轉化為帶平行鏈約束的排序問題,我們成功地穫得瞭單機重入問題的兩箇目標函數的多項式時間最優算法,一箇是總帶權完工時間∑ωjCj,另一箇是最大費用函數hmax.
본문고필대중입적단태궤배서문제,중입시지매개공건재궤기상가공불지일차.통과파중입모형전화위대평행련약속적배서문제,아문성공지획득료단궤중입문제적량개목표함수적다항식시간최우산법,일개시총대권완공시간∑ωjCj,령일개시최대비용함수hmax.
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.
