Unweighted 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.

Related Problems

Related: Weighted Interval Schedule Maximization Problem (ISMP)

Parameters

n: number of tasks (intervals)

k: number of machines (resources)

Table of Algorithms

Currently no algorithms in our database for the given problem.