提前预知信息的在线分批排序问题  

Online batch scheduling with known information in advance

作　　者：王成飞[1] 张玉忠[1] 

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

出　　处：《运筹学学报》2016年第1期84-90,共7页Operations Research Transactions

基　　金：教育部高等学校博士学科点专项科研基金(No.20123705110003);山东省自然科学基金(Nos.ZR2015GZ009;ZR2014AM012);曲阜师范大学博士科研启动基金(No.bsqd046000051)

摘　　要：研究工件可提前预知信息的在线分批排序问题,工件的预知信息时间依时间到达,目标为极小化最大完工时间.已知从工件的信息可预知到该工件可加工需要时间a,所有工件的最大加工时间为p_（max）,多个工件可以作为一批被机器同时加工,批的加工时间为该批工件中最长加工时间.对于批容量无限的单机问题给出一个在线算法γH-∞,并证明其竞争比和问题的下界都为1＋γ,其中γ=（-1＋（1＋（4p（max））/（p（max）＋a）））/2,进而算法是最优的.We study a single online batch scheduling problem with known information in advance.The information arrives over time and the objective is to minimize the maximum completion time.The time between the information arrival of a job and its release time is constant a.The maximum of the processing times of all jobs p_（max） is known in advance too.A batch processing machine can handle up to b jobs simultaneously.The processing time of a batch is given by the longest processing time of all jobs in the batch.When b=∞,we provide an optimal online algorithm γH-∞ with a competitive ratio of 1＋γ,where γ=（-1＋（1＋（4p_（max））/（p_（max）＋a）））/2.

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

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