摘要
本文研究一类批容量有界的并行分批、平行机在线排序问题。模型中有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 .
出处
《运筹与管理》
CSSCI
CSCD
北大核心
2015年第1期137-141,共5页
Operations Research and Management Science
基金
国家自然科学基金资助项目(11201439)
国家自然科学基金资助项目(11271341)
教育部博士点专项基金新教师基金(20120132120001)
山东省自然科学基金(ZR2012AQ12)
关键词
排序
并行批
最大完工时间
在线算法
竞争比
scheduling
parallel-batching
makespan
on-line algorithm
competitive ratio
