Interval scheduling
Encyclopedia
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. Compatible set of maximum size are 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 other many shorter requests. Also, selecting the shortest intervals is not optimal either or selecting intervals with fewest conflicts. 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.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, particularly in the area of algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
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. Compatible set of maximum size are 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 other many shorter requests. Also, selecting the shortest intervals is not optimal either or selecting intervals with fewest conflicts. 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
Charging Argument
In computer science, a Charging Argument is used to compare an algorithm output to an optimal solution.-Example:Proving optimality for earliest finishing time greedy algorithm:...
.
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
Earliest deadline first scheduling
Earliest deadline first or least time to go is a dynamic scheduling algorithm used in real-time operating systems. It places processes in a priority queue. Whenever a scheduling event occurs the queue will be searched for the process closest to its deadline...
.
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.