一类带批安装时间的平行机在线分批排序问题  

An On-line Parallel-machine Batching and Scheduling Problem with Batching Setups

作　　者：王迅娣[1] 朱洪利[1] 

机构地区：[1]曲阜师范大学运筹与管理学院,山东日照276826

出　　处：《洛阳理工学院学报（自然科学版）》2009年第3期51-55,共5页Journal of Luoyang Institute of Science and Technology：Natural Science Edition

基　　金：国家自然科学基金(10671108);山东省自然科学基金(Y2005A04);曲阜师范大学科研基金资助项目(XJZ200849)

摘　　要：研究一类带批安装时间的平行机排序问题。工件按时间到达,在任何时刻,只知道当前已经就绪工件的信息。工件成批加工,同一批中工件的完工时间为批中最后一个工件的完工时间,每批开工前有一个固定的批安装时间。目标函数为极小化所有工件的总完工时间。主要考虑两个到达时间且工件加工时间都相等的特殊情形,给出竞争比为3/2的在线算法,并且有实例说明此界为紧致的。This paper studies the parallel-machine scheduling model. All jobs are released on time, that is, at any time, with the only information about the ready jobs. Available jobs are grouped into batches, and all the jobs in the same batch have a common completion time which is equal to the completion time of the last job in the batch, and a constant setup time is prior to each batch. The objective function is to minimize the total completion time of all jobs. Mainly considering the special case where the jobs have two release times and the identical processing time, we provide an efficient on-line algorithm with competitive ratio of 3/2 and show that this bound is tight.

关 键 词：排序 在线 串行分批 批安装时间 

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