单位工件的平行机并行分批在线排序问题的算法  

Algorithms for an Online Parallel-batching Scheduling Problem with Unit Jobs

作　　者：胡丹[1] 农庆琴[1] 方奇志[1] 

机构地区：[1]中国海洋大学数学科学学院,山东青岛266100

出　　处：《运筹与管理》2015年第1期137-141,共5页Operations Research and Management Science

基　　金：国家自然科学基金资助项目(11201439);国家自然科学基金资助项目(11271341);教育部博士点专项基金新教师基金(20120132120001);山东省自然科学基金(ZR2012AQ12)

摘　　要：本文研究一类批容量有界的并行分批、平行机在线排序问题。模型中有n个相互独立的工件J={J1,…,Jn}要在m台批处理机上加工。批处理机每次可同时加工至多B(B<n)个工件。同一批中的工件同时开工,同时完工,工件加工过程不允许中断。工件Jj(1≤j≤n)的到达时间为rj,加工时间为1,工件是否会到达事先未知,而只有等到工件的到达时间才能获知它的到达。目标为最小化工件的最大完工时间。针对该排序问题,本文设计了两个竞争比均达到最好可能的在线算法。In this paper, we consider the problem of on-line scheduling a set of independent jobs J={J1,…,Jn}on parallel-batching processing machines{M1 ,…,Mm}.Each machine can handle up to B jobs as a batch simul-taneously , and all the jobs in a batch start and complete at the same time .Once a batch is started , it cannot be stopped until its completion .We deal with the bounded case where the capacity of the machines is finite , i.e., B＆lt;n.Each job Jj（1≤i≤n）becomes available at its release date rj, which is unknown in advance , and its pro-cessing time pj is a unit time.The problem involves assigning all the jobs to batches and machines and determi-ning the sequence of batches so as to minimize the makespan （ the maximum completion of the jobs ） .In this paper, two different best possible on -line algorithms, Unified Algorithm and Greedy Algorithm are designed .

关 键 词：排序 并行批 最大完工时间 在线算法 竞争比 

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