Unweighted Interval Scheduling, Online

Description

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)

Parameters

$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