Online job scheduling is a variant of the optimal job scheduling problem, in which the jobs are not all available at the beginning, but come one after the other. Each job must be scheduled to a machine immediately when it arrives, and cannot be scheduled later. This implies that the final scheduling might not be optimal in hindsight. Online algorithms for job scheduling are evaluated by their competitive ratio – the ratio between their performance and the best possible offline performance. Semi-online scheduling is a class of intermediate variants, between online scheduling and standard (offline) scheduling. In a semi-online problem, some – but not all – information about upcoming jobs is available in advance, e.g. the total size of all jobs or the maximum job size.
Online scheduling algorithms The first known algorithm for online job scheduling was List Scheduling, developed by Ronald Graham at 1966. It is a simple greedy algorithm that assigns the next job to the machine with the least load so far. Its competitive ratio for minimizing the maximum sum is 2-1/n (where n is the number of machines). This ratio is tight for n=2,3. The competitive ratio was improved in a series of later works. In 1999, Susanne Albers presented an algorithm that attains an approximation ratio of 1.923 for any number of machines, and proved a lower bound of 1.852, for minimizing the maximum sum. Elkind, Lam, Latifian, Neoh and Teh study a related problem called temporal fair division. A special case of this problem (where all agents have identical valuations) is equivalent to a variant of job scheduling, in which the goal is maximizing the minimum sum (this variant is sometimes called machine covering). They present an algorithm that guarantees envy-freeness up to one good (EF1). Although their paper assumes that all information on future items is available, this specific algorithm does not need future information (it is based on the Envy-graph procedure), so it is in fact an online algorithm.
Semi-online scheduling algorithms Kellerer, Kotov, Speranza and Tuza study three semi-online variants for minimizing the maximum sum, for n=2 machines (where for the fully-online variant, the optimal approximation ratio is 3/2):
There is a buffer of length k; the algorithm can either assign the job immediately, or store it in a buffer; if the buffer is full, one job from the buffer must be assigned. There is an algorithm with approximation ratio 4/3 for k=1, and it is tight even for larger k. Note that a fixed look-ahead of size k does not help; we must be able to store the jobs. There are two multi-processors that run in parallel; we send each job to each of the two multi-processors, and they can schedule it differently. At the end, the multi-processor with the smallest makespan is chosen. They present a heuristic with approximation ratio 4/3, and prove that it is tight. The sum of all job sizes is known in advance. They present a heuristic with approximation ratio 4/3, and prove that it is tight. Tan and Wu present optimal algorithms for three semi-online problems for maximizing the minimum sum (aka machine covering). They prove that:
If either the total value or the largest value is known in advance, then the approximation ratio of all algorithms is 1/(n-1). If both the total value and the largest value is known in advance, then the approximation ratio of all algorithms is 2/3 when n=3, and 1/(n-2) when n≥4. Dwibedy and Mohanti present a survey on semi-online scheduling algorithms, updated to 2022. Neoh, Peters and Teh present semi-online algorithms for other fairness notions besides max-min and min-max:
With identical valuations and information on the sum of valuations, when n=2 it is possible guarantee a multiplicative approximation of to (sqrt(5)-1)/2 EFx, and it is tight; when n≥3 no positive approximation is possible. Without any future information, it is impossible to guarantee any positive multiplicative approximation of EFx.
See also Online fair division – a more general problem, in which items should be allocated online to agents who may have different valuations.
References
