Interval scheduling
Interval scheduling is a class of problems in computer science, particularly in the area of algorithm design. A list of tasks is given as a set of time intervals; for instance, one task might run from 2:00 to 5:00 and another task might run from 6:00 to 8:00. Posed as an optimization problem, the goal is to maximize the number of executed tasks without overlapping the tasks. A request corresponds to an interval of time. We say that a subset of requests is compatible if no two of them overlap in time and our goal is to accept as large a compatible subset as possible. A compatible set of maximum size is called optimal.
There are several solutions for this problem that are not optimal. For example, selecting the intervals that start earliest is not an optimal solution because if the earliest interval happens to be really long by accepting it we would have to reject many other shorter requests. Selecting the shortest intervals or selecting intervals with the fewest conflicts is also not optimal. The optimal solution is choosing the earliest finishing time, as in the request that finishes first. One way of proving the optimality of this algorithm is by using the Charging Argument .
An important class of scheduling algorithms is the class of dynamic priority algorithms. When none of the intervals overlap the optimum solution is trivial. The optimum for the non-weighted version can found with the earliest deadline first scheduling.
Weighted interval scheduling is a generalization where a value is assigned to each executed task and the goal is to maximize the total value. The solution need not be unique.
[edit] See also
[edit] Sources
- Kleinberg, Jon; Tardos, Eva (2006). Algorithm Design. ISBN 0-321-29535-8.
