View source for Unweighted Interval Scheduling, Online

{{DISPLAYTITLE:Unweighted Interval Scheduling, Online (Interval Scheduling)}}
== 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 == 

{| class="wikitable sortable"  style="text-align:center;" width="100%"

! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference

|-

| [[Fixed priority shortest job first (Unweighted Interval Scheduling, Online Interval Scheduling)|Fixed priority shortest job first]] || 1940 || $O(n \log n)$ || $O(n+k)$? || Exact || Deterministic ||  
|-
| [[Priority scheduling (Unweighted Interval Scheduling, Online Interval Scheduling)|Priority scheduling]] || 1940 || $O(n)$ || $O(n+k)$? || Exact || Deterministic ||  
|-
| [[Shortest remaining time first (Unweighted Interval Scheduling, Online Interval Scheduling)|Shortest remaining time first]] || 1940 || $O(n)$ || $O(n+k)$? || Exact || Deterministic ||  
|-
| [[First come, first served (Unweighted Interval Scheduling, Online Interval Scheduling)|First come, first served]] || 1940 || $O(n)$ || $O(n+k)$? || Exact || Deterministic ||  
|-
| [[Round-robin scheduling (Unweighted Interval Scheduling, Online Interval Scheduling)|Round-robin scheduling]] || 1940 || $O(n)$ || $O(n+k)$? || Exact || Deterministic ||  
|-
| [[Multilevel queue scheduling (Unweighted Interval Scheduling, Online Interval Scheduling)|Multilevel queue scheduling]] || 1940 || $O(n)$ || $O(n+k)$? || Exact || Deterministic ||  
|-
| [[Work-conserving schedulers (Unweighted Interval Scheduling, Online Interval Scheduling)|Work-conserving schedulers]] || 1940 || $O(n)$ ||  || Exact || Deterministic ||  
|-
|}

== Time Complexity Graph == 

[[File:Interval Scheduling - Unweighted Interval Scheduling, Online - Time.png|1000px]]