Interval scheduling: Difference between revisions

Revision as of 00:03, 3 October 2023

Latest revision as of 14:15, 24 June 2025

(11 intermediate revisions by 6 users not shown)

Line 1:

{{short description|Class of problems in  computer science}}

'''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 processed by some machine (or, equivalently, scheduled on some resource). 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 on the machine/resource. 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.

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.

Line 24:

=== 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|publisher=Pearson/Addison-Wesley |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.

Line 39:

=== Weighted ===

WhenProblems theinvolving intervals have weights, theweighted interval scheduling problem isare equivalent to finding a maximum-weight [[Independent set (graph theory)|independent set]] in an [[interval graph]]. These weighted interval schedulingSuch problems can be solved in polynomial time.<ref name=":0">{{Cite journal |last1=Bar-Noy |first1=Amotz |last2=Bar-Yehuda |first2=Reuven |last3=Freund |first3=Ari |last4=(Seffi) Naor |first4=Joseph |last5=Schieber |first5=Baruch |author5-link=Baruch Schieber |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|s2cid=12329294 |issn=0004-5411 |s2cid=12329294|url-access=subscription }}</ref>

ToAssuming findthe vectors are sorted from earliest to latest finish time, the following pseudocode determines the maximum weight of a single-interval schedule in Θ(n) time,:<syntaxhighlight perform theline="1" following pseudocode:lang="c">

<syntaxhighlight line="1" lang="c">

// The vectors are already sorted from earliest to latest finish time.

int v[numOfVectors + 1]; // list of interval vectors

int w[numOfVectors + 1]; // w[j] is the weight for v[j].

int p[numOfVectors + 1]; // p[j] is the # of vectors that end before v[j] begins.

int M[numOfVectors + 1];

int finalSchedule[];

// v[0] does not exist., Theand the first interval vector is setassigned to v[1].

w[0] = 0; p[0] = 0; M[0] = 0;

// The following code determines the value of M for each vector.

// The maximum weight of the schedule is equal to M[numOfVectors].

for (int i = 1; i < numOfVectornumOfVectors + 1; i++) {

M[i] = max(w[i] + M[p[i]], M[i - 1]);

}

// TheFunction maximumto weight ofconstruct the optimal schedule is equal to M[numOfVectors].

schedule (j) {

if (j == 0) { return; }

Line 71 ⟶ 70:

==== Example ====

If we have the following 9 vectors sorted by finish time, with the weights above each corresponding interval, we can determine which of these vectors are included in our maximum weight schedule which only contains a subset of the following vectors.

[[File:Weighted Interval Scheduling Example.png|none|thumb|701x701px872x872px]]

Here, we start withinput our final vector (where j=9 in this example), and input it into our schedule function infrom the code block above. We perform thesethe actions in the table below until j is set to 0, at which point, we only include into our final schedule the encountered intervals which met the <math display="inline">w[j]+M[p[j]] >=\ge M[j-1]</math> requirement. This final schedule is the schedule with the maximum weight.

{| class="wikitable mw-collapsible"

|+

!j

!Calculation

!<math display="inline">w[j]+M[p[j]] >=\ge M[j-1]</math>

(i.e. This vector is included in the final schedule)

!Set j to

Line 166 ⟶ 164:

=== 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 = 730730–738
| year = 2006
| last1 = Chuzhoy | first1 = J.Julia | author1-link = Julia Chuzhoy
| last2 = Ostrovsky | first2 = R.Rafail | author2-link = Rafail Ostrovsky| last3 = Rabani | first3 = Y. | citeseerx = 10.1.1.105.2578}}</ref>

| last3=Rabani | first3=Yuval

| citeseerx=10.1.1.105.2578}}</ref>

==Related problems==

Line 188 ⟶ 197:

{{Scheduling problems}}

[[Category:Optimal scheduling]]

[[Category:NP-complete problems]]