Online Scheduling Problem With Incompatible Families

Scheduling is to assign some tasks to time resources under some constraints, such that one-or multi-criteria to the optimum. Recently, online scheduling and parallel batch scheduling are two flourishing scheduling models. On-line scheduling means that all job informations are unknown before their release times, and once a job is scheduled, it cannot be changed. Parallel batch scheduling means that a machine can process several jobs simultaneously as a batch, when the sum of their sizes is not greater than the capacity of machine. The processing time of the batch is equal to the longest processing time of the jobs assigned to it. Once a batch is started, it cannot be stopped until its completion. Incompatible families means that jobs belong to different families are incompatible, cannot be assigned together.In our paper, we consider several online parallel batch scheduling models:scheduling with incompatible families. Here, we have one or more batch machines and some jobs, whose informations such as release time, process time, size and families are unknown before their release times. Our goal is to minimize the makespan. Using the 3-field notation of Graham et al.[2], the main results of this paper are as follows:(1) For the scheduling model 1|online, p-patch, b<n, two families, p=1| Cmax, we give a best possible online algorithm.(2) For the scheduling model Pm |online, p-patch, b<n, m families, p=1| Cmax, we give an online algorithm with competitive ratio 2, and a best possible online algorithm in the case that release times are known.(3) For the scheduling model 1|online, p-patch, b=1, si, two families, p=1| Cmax, we give an online algorithm with competitive ratio 2, and a best possible online algorithm in the case that small jobs can be spilt.