| Parallel-batch scheduling is an important model of modern scheduling. An advantage of this model is that multiple jobs can be put into a common batch so that these jobs are processed simultaneously. Here, the processing time of a job batch is defined to be the longest processing time of the jobs in the batch.In this paper, we study two problems on parallel-batch scheduling. First, we study the scheduling on m unbounded parallel batch matchines with release dates and rejections of jobs. In this problem, a job is either rejected with a certain penalty having to be paid, or accepted and processed in batches on one of the m machines. The objective is to minimize the sum of the makespan of the accepted jobs and the total rejection penalty of the rejected jobs. When m is a fixed number, we provide a pseudo-polynomial-time algorithm and a fully polynomial-time approximation scheme for the problem.Then we consider the online uniform batch scheduling problem with (m=2) uniform ma-chines in which one machine has a processing speed of 1, and the other machine has a processing speed of v with 0<υ≤1. The objective is to minimize the makespan. All jobs arrive over time, and we know no information of the comming jobs in advance. Suppose thatα≈0.618 is the pos-itive solution ofα2+α-1= 0, andβis the positive solution ofβ3+3β2+(3-1/υ)β-1/υ=0. We first establish the lower bound of the problem:when 0<υ≤1/2, our lower bound is 1+α; when 1/2≤υ≤1, our lower bound is 1+β. The above lower bound is still valid for the special version pj= 1. Then we present two online algorithms, called Delay-Q2 and Refined-Delay-Q2. The competitive ratio of Delay-Q2 is max{1+α, min{1+υ, 1/υ+α}}. When 0<υ≤1/2, Delay-Q2 is the best possible, and still best possible for the special version pj= 1, with com-petitive ratio being 1+α≈1.618. When 1/2≤υ≤1 and pj= 1, The online algorithm Refined-Delay-Q2 is best possible with competitive ratio 1+β.
|
PDF Full Text Request