Unweighted Interval Scheduling, Online (Interval Scheduling)

From Algorithm Wiki
Jump to navigation Jump to search


Given are $n$ intervals of the form $(s_j , f_j)$ with $s_j < f_j$, for $j = 1, \ldots , n$. These intervals are the jobs that require uninterrupted processing during that interval. We will assume (without loss of generality) that the $s_j$’s and the $f_j$’s are nonnegative integers. We say that two intervals (or jobs) overlap if their intersection is nonempty, otherwise they are called disjoint. Further, there are machines. In the basic interval scheduling problem each machine can process at most one job at a time and is always available, i.e. each machine is continuously available in $(0,\infty)$. We assume that, when processed, each job is assigned to a single machine, thus, we do not allow interrupting a job and resuming it on another machine, unless explicitly stated otherwise. The basic interval scheduling problem is now to process all jobs using a minimum number of machines. In other words, find an assignment of jobs to machines such that no two jobs assigned to the same machine overlap while using a minimum number of machines. We call an assignment of (a subset of) the jobs to the machines a schedule.

This is the online version of the problem.

Related Problems

Related: Unweighted Interval Scheduling, Weighted Interval Schedule Maximization Problem (ISMP)


$n$: number of tasks (intervals)

$k$: number of machines (resources)

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Fixed priority shortest job first 1940 $O(n \log n)$ $O(n+k)$? Exact Deterministic
Priority scheduling 1940 $O(n)$ $O(n+k)$? Exact Deterministic
Shortest remaining time first 1940 $O(n)$ $O(n+k)$? Exact Deterministic
First come, first served 1940 $O(n)$ $O(n+k)$? Exact Deterministic
Round-robin scheduling 1940 $O(n)$ $O(n+k)$? Exact Deterministic
Multilevel queue scheduling 1940 $O(n)$ $O(n+k)$? Exact Deterministic
Work-conserving schedulers 1940 $O(n)$ Exact Deterministic

Time Complexity Graph

Interval Scheduling - Unweighted Interval Scheduling, Online - Time.png