On-line Batch Scheduling With Special Family-jobs

Scheduling is to assign some tasks to time resources under some constraints such that one- or multi-criteria attain to the optimum. In the parallel-batching scheduling model, a machine can process seveal jobs simultaneously as a batch. The processing time of each batch is equal to the longest processing time of the jobs assigned to it. When jobs are processed, jobs from different families cannot be processed in the same batch. In the online scheduling problem, jobs arrive over time and each job's characteristic, including its processing time p_j and release date r_j, is unknown until it is released, and once a job is scheduled, it cannot be changed. The quality of an on-line algorithm is usually measured by its competitive ratio.In this paper, we consider a special kind of on-line batch scheduling to minimize makespan of three families of jobs. In this model, the batch size of the two families can be processed in batch is infinite, that is the two families are general batch-families; the batch size of the other family is one, that is only one job can be processed in a batch. The lower bound of this model is equal to the upper bound of the model of two general families. Because of the particularity of one of the families, we give an on-line algorithm which prioritize jobs of this family. As long as jobs of this family arrive, we first schedule these jobs. In the proof of the upper bound of the algorithm, we consider mainly the last four batches. Then either there exist idle times among them or they are executed contiguously. At last we have that this algorith is best possible on-line algorithm with competitive ratio of (17^1/2+3)/4.