Online scheduling of equal-length jobs with incompatible families on multiple batch machines to maximize the weighted number of early jobs

This paper studies the online scheduling of equal-length jobs with incompatible families on multiple batch machines which can process the jobs from a common family in batches, where each batch has a capacity b   with b=∞b=∞ in the unbounded batching and b<∞b<∞ in the bounded batching. Each job J   has an equal-length integral processing time p>0p>0, an integral release time r(J)⩾0r(J)⩾0, an integral deadline d(J)⩾0d(J)⩾0 and a real weight w(J)⩾0w(J)⩾0. The goal is to determine a preemptive schedule with restart which maximizes the weighted number of early jobs. When p=1p=1, we show that a simple greedy online algorithm has a competitive ratio 2, and establish the lower bound 2−1/b2−1/b. This means that the greedy algorithm is of the best possible for b=∞b=∞. When p   is any positive integer, we provide an online algorithm of competitive ratio 3+22 for both b=∞b=∞ and b<∞b<∞. This is the first online algorithm for the problem with a constant competitive ratio.

► Our algorithm is able to adapt to the unbounded batching and bounded batching.
► We design a simple and effective method (CPV Method) to select machines and jobs.
► Our algorithm is the first online algorithm for this problem with the competitive ratio being bounded by a constant.