Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) |
||
Line 16:
All these problems are special cases of [[single-machine scheduling]], since they assume that all tasks must run on a single processor. Single-machine scheduling is a special case of [[optimal job scheduling]].
==Single-Interval Scheduling Maximization==
[[File:IntervalSelection.svg|20px|right]]
=== Unweighted ===
Several algorithms, that may look promising at first sight, actually do not find the optimal solution:<ref name="KleinbergTardos">{{cite book|last=Kleinberg|first=Jon|url=https://archive.org/details/algorithmdesign0000klei|title=Algorithm Design|author2=Tardos, Éva|year=2006|isbn=978-0-321-29535-4|url-access=registration}}</ref>
* Selecting the intervals that start earliest is not an optimal solution, because if the earliest interval happens to be very long, accepting it would make us reject many other shorter requests.
* Selecting the shortest intervals or selecting intervals with the fewest conflicts is also not optimal.
The following [[greedy algorithm]], called [[Earliest deadline first scheduling]], does find the optimal solution for unweighted single-inteval scheduling:
# Select the interval, ''x'', with the earliest '''finishing time'''.
Line 35:
The greedy algorithm can be executed in time O(''n'' log ''n''), where ''n'' is the number of tasks, using a preprocessing step in which the tasks are sorted by their finishing times.
=== 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>{{Cite journal|last=Bar-Noy|first=Amotz|last2=Bar-Yehuda|first2=Reuven|last3=Freund|first3=Ari|last4=(Seffi) Naor|first4=Joseph|last5=Schieber|first5=Baruch|date=2001-09-01|title=A unified approach to approximating resource allocation and scheduling|url=https://doi.org/10.1145/502102.502107|journal=Journal of the ACM|volume=48|issue=5|pages=1069–1090|doi=10.1145/502102.502107|issn=0004-5411}}</ref>
| |||