河南理工大学学报：自然科学版
河南理工大學學報：自然科學版
하남리공대학학보：자연과학판
JOURNAL OF HENAN POLYTECHNIC UNIVERSITY
2011年
4期
502-504
,共3页
分批排序%近似算法%最差性能比%优先约束
分批排序%近似算法%最差性能比%優先約束
분비배서%근사산법%최차성능비%우선약속
batching scheduling%approximation algorithm%worst-case performance ratio%precedence constraints
主要对带链优先约束和尺寸的工件并行批排序问题进行了研究,当工件的加工时间一致时对目标函数是极小化所有工件加工时间之和的情形,借助于拆分的技巧,给出了一个最差性能比为2的近似算法.
主要對帶鏈優先約束和呎吋的工件併行批排序問題進行瞭研究,噹工件的加工時間一緻時對目標函數是極小化所有工件加工時間之和的情形,藉助于拆分的技巧,給齣瞭一箇最差性能比為2的近似算法.
주요대대련우선약속화척촌적공건병행비배서문제진행료연구,당공건적가공시간일치시대목표함수시겁소화소유공건가공시간지화적정형,차조우탁분적기교,급출료일개최차성능비위2적근사산법.
The paper focuses on the problem of batching scheduling with job sizes and chain precedence constraints.A2-approximation algorithm is presented for the case on a single machine where all jobs have identical processing times when minimizing total completion time.
