Online Scheduling On Parallel-batch Machines With Job Compatibilities

The essence of the scheduling problem is how to better arrange and complete the corresponding tasks under certain resource constraints so that the desired benefits or goals can achieve the optimal or ideal value. Scheduling theory is widely used in many fields such as industrial manufacturing, computer science, logistics and transportation management, so it has important theoretical research value and wide application prospect.We consider the online scheduling problem on m unbounded parallel-batch machines with job compatibilities. Online means that jobs arrive over time and the scheduler does not know the information of a job until it arrives. On the arrival of the jobs, the decision maker can immediately schedule it or delay the processing of it. A parallel batch machine can process several jobs as a batch simultaneously. The batch capacity can be limited or infinite. Jobs in a common batch have the same starting times and the same completion times. The processing time of a batch is given by the longest job in this batch. We study two scheduling models on batch machines with job compatibilities. In the first model, the job compatibility is characterized by an interval compatibility graph. Each job has an interval, and two jobs are compatible if and only if the interval of them intersects. Any two jobs can be processed in the same batch as long as they are pairwise compatible. In the second model, all jobs from several incompatible families and jobs belonging to distinct families cannot be processed in the same batch. In both models, the objective is to minimize the makespan.The main results of this paper are as follows:(1) For problem pm|on- line, rj,G = INT, p - batch,b =?|Cmax , we firstly show that there is no online algorithm with a competitive ratio less than 2. Then we provide an online algorithm with a competitive ratio 2+(m-1)/(m+1) which is optimal for the case m = 1. When all jobs have the same processing times, we provide an optimal online algorithm with a competitive ratio 2.(2) For problem pm|on- line, rj, family, p - batch, b = ?|Cmax, we show that there is no online algorithm with a competitive ratio less than 2. Then we provide an online algorithm with a competitive ratio 7/3-1/(3m), and prove that this bound is tight. When all jobs have the same processing times, we present an optimal online algorithm with a competitive ratio 2.