运筹学学报
運籌學學報
운주학학보
OR TRANSACTIONS
2006年
1期
31-37
,共7页
运筹学%近似算法%分批加工%排序%释放时间%最大完工时间
運籌學%近似算法%分批加工%排序%釋放時間%最大完工時間
운주학%근사산법%분비가공%배서%석방시간%최대완공시간
Operation research%Approximation algorithms%batch processing%scheduling%release times%makespan
本文考虑极小化最大完工时间的单机分批加工问题.设有n个工件和一台批加工机器.每个工件有一个释放时间和一个加工时间.批加工机器可以同时加工b(b＜n)个工件.一个批次的加工时间是该批次所包含所有工件的加工时间的最大者.在同一批次中加工的工件有相同的完工时间,即它们的共同开始时间加上该批次的加工时间.对于极小化最大完工时间问题,本文给出了一个多项式时间近似方案(PTAS).该算法的总运行时间为O(nlog nC·n),C仅与精度ε有关.这一结果改进了已有的两个多项式时间近似方案.
本文攷慮極小化最大完工時間的單機分批加工問題.設有n箇工件和一檯批加工機器.每箇工件有一箇釋放時間和一箇加工時間.批加工機器可以同時加工b(b＜n)箇工件.一箇批次的加工時間是該批次所包含所有工件的加工時間的最大者.在同一批次中加工的工件有相同的完工時間,即它們的共同開始時間加上該批次的加工時間.對于極小化最大完工時間問題,本文給齣瞭一箇多項式時間近似方案(PTAS).該算法的總運行時間為O(nlog nC·n),C僅與精度ε有關.這一結果改進瞭已有的兩箇多項式時間近似方案.
본문고필겁소화최대완공시간적단궤분비가공문제.설유n개공건화일태비가공궤기.매개공건유일개석방시간화일개가공시간.비가공궤기가이동시가공b(b＜n)개공건.일개비차적가공시간시해비차소포함소유공건적가공시간적최대자.재동일비차중가공적공건유상동적완공시간,즉타문적공동개시시간가상해비차적가공시간.대우겁소화최대완공시간문제,본문급출료일개다항식시간근사방안(PTAS).해산법적총운행시간위O(nlog nC·n),C부여정도ε유관.저일결과개진료이유적량개다항식시간근사방안.
We consider the problem of minimizing the maximum completion time (makespan)on a batch machine. In this problem, we are given n jobs and a bat ch machine. Each job is characterized by a release time and a processing time. The batch machine can process up to b (b ＜ n) jobs as a batch simultaneously. The processing time of a batch is equal to the longest processing time among all jobs in the batch. Jobs processed in the same batch have the same completion time, i.e., their common starting time plus the processmg time of the batch. We present a polynomial time approximation scheme (PTAS) for this only on the accuracy ε. The result improves the previous two PTASs for the problem.
