工件按加工长度不增序到达的最小化最大流程在线分批排序  

Online parallel batching scheduling for nonincreasing-processing-time jobs to minimize the maximum flow-time

作　　者：焦成文[1,2] 李文华[1] 

机构地区：[1]郑州大学数学与统计学院,郑州450001 [2]中国科学院大学数学科学学院,北京100049

出　　处：《运筹学学报》2013年第4期96-102,共7页Operations Research Transactions

基　　金：国家自然科学基金(No.11171313)

摘　　要：研究单处理机工件按加工长度不增顺序到达的在线分批排序问题.工件按时在线到达,目标是最小化最大流程.流程时间是指工件的完工时间与到达时间的差值,它体现了工件在系统内的逗留时间.对于批容量有界的情形,给出了一个竞争比为(?)的最好可能的在线算法;对于批容量无界的情形,给出了一个竞争比为2^(1/2)的最好可能的在线算法.We consider on-line scheduling on a parallel batching machine where the jobs come with the noninereasing-processing times. In this paper online means that jobs arrive over time. The objective is to minimize the maximum flow time of these jobs. The flow-time of a job means that its completion time minus its arrival time. It reflects the time of the job staying in the system. For the bounded model, we give a best possible algorithm with competitive ratio 1＋√5/2. For the unbounded model, we also give a best possible algorithm with competitive ratio √2.

关 键 词：在线排序 平行分批 最大流程时间 竞争比 

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