摘要
主要对带链优先约束和尺寸的工件并行批排序问题进行了研究,当工件的加工时间一致时对目标函数是极小化所有工件加工时间之和的情形,借助于拆分的技巧,给出了一个最差性能比为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.
出处
《河南理工大学学报（自然科学版）》
CAS
2011年第4期502-504,共3页
Journal of Henan Polytechnic University（Natural Science）
基金
国家自然科学基金资助项目(10971201)
河南理工大学重点学科研究项目
关键词
分批排序
近似算法
最差性能比
优先约束
batching scheduling
approximation algorithm
worst-case performance ratio
precedence constraints
