Interval scheduling: Difference between revisions

Revision as of 15:28, 6 October 2021

Revision as of 15:31, 6 October 2021

Line 3:

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]].

A generalization of the problem considers ''<math>k>1''</math> machines/resources.<ref name=Survey>{{Cite journal | title = Interval scheduling: A survey| year = 2007| last1 = Kolen| first1 = A. | journal = Naval Research Logistics| volume = 54| issue = 5| pages = 530-543}}</ref> Here the goal is to find ''<math>k''</math> compatible subsets whose union is the largest.

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