运筹与管理Issue(1)：137-141,5.
单位工件的平行机并行分批在线排序问题的算法
Algorithms for an Online Parallel-batching Scheduling Problem with Unit Jobs
摘要
Abstract
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<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 .关键词
排序/并行批/最大完工时间/在线算法/竞争比Key words
scheduling/parallel-batching/makespan/on-line algorithm/competitive ratio分类
数理科学引用本文复制引用
胡丹,农庆琴,方奇志..单位工件的平行机并行分批在线排序问题的算法[J].运筹与管理,2015,(1):137-141,5.基金项目
国家自然科学基金资助项目（11201439）；国家自然科学基金资助项目（11271341）；教育部博士点专项基金新教师基金（20120132120001）；山东省自然科学基金 （）
