Abstract: In this paper, we consider the problem of on-line scheduling a set of independent jobs J={J₁,…,J_n}on parallel-batching processing machines{M₁,…,M_m}. Each machine can handle up to B jobs as a batch simultaneously, 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 J_j(1≤i≤n)becomes available at its release date r_j, which is unknown in advance, and its processing time p_j is a unit time. The problem involves assigning all the jobs to batches and machines and determining 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

摘要： 本文研究一类批容量有界的并行分批、平行机在线排序问题。模型中有n个相互独立的工件J={J₁,…,J_n}要在m台批处理机上加工。批处理机每次可同时加工至多B(B<n)个工件。同一批中的工件同时开工,同时完工,工件加工过程不允许中断。工件J_j(1≤j≤n)的到达时间为r_j,加工时间为1,工件是否会到达事先未知,而只有等到工件的到达时间才能获知它的到达。目标为最小化工件的最大完工时间。针对该排序问题,本文设计了两个竞争比均达到最好可能的在线算法。

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