Content deleted Content added
→Weighted: format code |
Citation bot (talk | contribs) Alter: pages. Add: s2cid, doi, authors 1-1. Removed parameters. Formatted dashes. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Whoop whoop pull up | #UCB_webform 1608/3352 |
||
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 =
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.
Line 38:
=== Weighted ===
When the intervals have weights, the problem is equivalent to finding a maximum-weight [[Independent set (graph theory)|independent set]] in an [[interval graph]]. It can be solved in polynomial time.<ref name=":0">{{Cite journal|
To find the maximum weight of a single interval schedule in Θ(n) time, perform the following pseudocode:
Line 65:
} else { schedule(j - 1); }
}
</syntaxhighlight><ref>{{Cite book |
==Group Interval Scheduling Decision==
| |||