Content deleted Content added
→Example: fixed the display of a latex image to use \ge instead of >= |
m Open access bot: doi updated in citation with #oabot. |
||
Line 5:
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| doi = 10.1002/nav.20231| s2cid = 15288326| doi-access = free}}</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.
| |||