Content deleted Content added
Erel Segal (talk | contribs) No edit summary |
Erel Segal (talk | contribs) |
||
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 executed. 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. 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 - a set of non-overlapping intervals of maximum size. The goal here is to execute as many tasks as possible, that is, 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.
Line 12:
* ISMP is the special case in which each task belongs to its own group (i.e. it is equal to GISMP1).
* GISDP is the problem of deciding whether the maximum exactly equals the number of groups.
All these problems can be generalized by adding a ''weight'' for each interval, representing the profit from executing the task in that interval. Then, the goal is to maximize the total weight.
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]].
==Interval Scheduling Maximization==
[[File:IntervalSelection.svg|20px|right]]
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.
=== Greedy polynomial solution ===
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'''.
# Remove ''x'', and all intervals intersecting ''x'', from the set of candidate intervals.
Line 32 ⟶ 34:
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 single-interval scheduling ===
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>
==Group Interval Scheduling Decision==
Line 96 ⟶ 101:
=== LP based approximation algorithms ===
Using the technique of [[Linear programming relaxation]], it is possible to approximate the optimal scheduling with slightly better approximation factors. The approximation ratio of the first such algorithm is asymptotically 2 when ''k'' is large, but when ''k=2'' the algorithm achieves an approximation ratio of 5/3.<ref name=Spieksma/> The approximation factor for arbitrary ''k'' was later improved to 1.582.<ref name="ChuzoiEtAl">{{Cite journal | doi = 10.1287/moor.1060.0218| title = Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems| journal = Mathematics of Operations Research| volume = 31| issue = 4| pages = 730| year = 2006| last1 = Chuzhoy | first1 = J. | author1-link = Julia Chuzhoy | last2 = Ostrovsky | first2 = R. | author2-link = Rafail Ostrovsky| last3 = Rabani | first3 = Y. | citeseerx = 10.1.1.105.2578}}</ref>
<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>
==Graph representations==
| |||