一类有尺寸大小的在线分批排序问题  

A Kind of Problem of On-line Batch Scheduling with Non-identical Job Sizes

作　　者：徐健腾[1] 柏庆国[1] 魏伟[2] 

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

出　　处：《临沂师范学院学报》2006年第6期17-19,共3页Journal of Linyi Teachers' College

基　　金：山东省自然科学基金项目资助(Y2005A04)

摘　　要：研究了工件有尺寸大小的一致性在线分批排序．就所有工件有两个到达时间ri,i=1,2(不妨设r1=0,r2=r)对于0时刻到达的工件中加工时间最大的批满足一定的约束条件下的一致性在线分批排序给出一个在线算法,并证明了算法的竞争比不超过2．357．In this paper, we consider the proportional problem of on-line batch scheduling with non-identical job sizes. We also provide an on-line algorithm with the competitive ratio not more than 2.357 for the special case that the longest job with arrival 0 satisfies certain restraints.

关 键 词：运筹学 分批排序 在线算法 竞争比 

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