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

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