工件带链约束和尺寸的并行批排序  

A single batch processing machine with nonidentical job sizes and chain precedence constraints

作　　者：马冉[1] 姚景景[1] 郑玉歌[1] 

机构地区：[1]河南理工大学数学与信息科学学院,河南焦作454000

出　　处：《河南理工大学学报（自然科学版）》2011年第4期502-504,共3页Journal of Henan Polytechnic University（Natural Science）

基　　金：国家自然科学基金资助项目(10971201);河南理工大学重点学科研究项目

摘　　要：主要对带链优先约束和尺寸的工件并行批排序问题进行了研究,当工件的加工时间一致时对目标函数是极小化所有工件加工时间之和的情形,借助于拆分的技巧,给出了一个最差性能比为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.

关 键 词：分批排序 近似算法 最差性能比 优先约束 

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