Content deleted Content added
Erel Segal (talk | contribs) add template |
Erel Segal (talk | contribs) No edit summary |
||
Line 1:
'''Interval scheduling''' is a class of problems in [[computer science]], particularly in the area of [[algorithm]] design. The problems consider a set of tasks. Each task is represented by an ''interval'' describing the time in which it needs to be executed. For instance, task A might run from 2:00 to 5:00, task B might run from 4:00 to 10:00 and task C might run from 9:00 to 11:00. A subset of intervals is ''compatible'' if no two intervals overlap. For example, the subset {A,C} is compatible, as is the subset {B}; but neither {A,B} nor {B,C} are compatible subsets, because the corresponding intervals within each subset overlap.
The ''interval scheduling maximization problem'' (ISMP) is to find a largest compatible set - a set of non-overlapping intervals of maximum size. The goal here is to execute as many tasks as possible, that is, maximize the [[throughput]].
In an upgraded version of the problem, the intervals are partitioned into groups. A subset of intervals is ''compatible'' if no two intervals overlap, and moreover, no two intervals belong to the same group (i.e. the subset contains at most a single representative interval of each group).
Line 11:
GISMP is the most general problem; the other two problems can be seen as special cases of it:
* ISMP is the special case in which each task belongs to its own group (i.e. it is equal to GISMP1).
* GISDP is the problem of deciding whether the maximum
==Interval Scheduling Maximization==
| |||