Online job scheduling
From Wikipedia, the free encyclopedia
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.
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.[1]
The competitive ratio was improved in a series of later works. In 1999, Susanne Albers[2] 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[3]: Sec.3.2 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.[4]: Sec.6