In this paper we consider the single-machine parallel-batching scheduling problem with family jobs under on-line setting in the sense that we construct our schedule irrevocably as time proceeds and do not know of the ...
详细信息
ISBN:
(纸本)9783642253485;9783642253492
In this paper we consider the single-machine parallel-batching scheduling problem with family jobs under on-line setting in the sense that we construct our schedule irrevocably as time proceeds and do not know of the existence of any job until its arrival. Our objective is to minimize the maximum completion time of the jobs (makespan). A batch processing machine can handle up to B jobs simultaneously. The jobs that are processed together form a batch, and all jobs in a batch start and complete at the same time. The processing time of a batch is given by the longest processing time of any job in the batch. The jobs from different families are incompatible and thus cannot be put in the same batch. We deal with the special variant of the general problem: the unbounded model in which the machine can handle infinite number of jobs simultaneously, the jobs only have two distinct arrival times and come from 2 families. We provide an on-line algorithm with a worst case ratio 1 + alpha where alpha = root 5-1/2.
暂无评论