Interval scheduling: Difference between revisions

Revision as of 09:51, 3 September 2021

Revision as of 15:24, 6 October 2021

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 executedprocessed by some machine (or, equivalently, scheduled on some resource). 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 on the machine/resource. 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, -i.e., a set of non-overlapping intervals of maximum size. The goal here is to execute as many tasks as possible, that is, to maximize the [[throughput]]. It is equivalent to finding a [[Independent set (graph theory)|maximum independent set]] in an [[interval graph]].

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). Each group of intervals corresponds to a single task, and represents several alternative intervals in which it can be executed.

The ''group interval scheduling decision problem'' (GISDP) is to decide whether there exists a compatible set in which all groups are represented. The goal here is to execute a single representative task from each group. GISDPk is a restricted version of GISDP in which the number of intervals in each group is at most ''k''.