Notation for Scheduling Problems
Here we collect notation related to scheduling problems we cover in class.
Interval Scheduling
The Problem
Notation | Meaning |
n | Number of intervals |
s(i) | Start time of ith interval. The convention that the interval has to start at time step s(i) |
f(i) | Finish time of ith interval. The convention that the interval has to finish at time step f(i)−1 |
[ℓ,r) | The interval {ℓ,…,r−1} |
O | An optimal schedule |
Greedy Algorithm for Interval Scheduling
Notation | Meaning |
S | At any point of the run of the algorithm the set of intervals that have been chosen/scheduled. |
R | At any point of the run of the algorithm the set of intervals that do not have conflict with intervals in S. |
S∗ | The final schedule output by the algorithm. |
Scheduling to minimize maximum lateness
The Problem
Notation | Meaning |
n | Number of jobs. |
di | Deadline for ith job: job needs to finish by time di−1. |
ti | Duration for ith job: job takes ti time units. |
s(i) | Scheduled start time for job i. |
f(i) | Scheduled finish time for job i: f(i)=s(i)+ti. |
ℓi | Latness of job i, ℓi=max. |
L(S) | Maximum latness of scheule S. Defined as L(S)=\max_{i\in S} \ell_i. |
\text{idle}(S) | Idle time of schedule S. Recall that the idle time of S is \max_{i < n} (s(i+1)-f(i)). |
\#\text{inv}(S) | Number of inversions in S. Recall that (i,j) is an inversion in S if i is scheduled before j but d_i > d_j. |
Greedy Algorithm for Scheduling to Minimize Maximum Lateness
Notation | Meaning |
S | Schedule output by Greedy algorithm. Schedule is set of pairs (s(i),f(i)). |
\mathcal{O} | An optimal schedule. |
Weighted Interval Scheduling
The Problem
Notation | Meaning |
n | Number of intervals |
s_i | Start time of ith interval. The convention that the interval has to start at time step s_i |
f_i | Finish time of ith interval. The convention that the interval has to finish at time step f_i-1 |
v_i | Value of the ith interval. If i is added to the schedule, we get a value of v_i. |
S | S\subseteq [n] is a schedule if no two intervals in S conflict with each other. |
v(S) | Value of schedule S. Defined as \sum_{i\in S} v_i. |
\mathcal{O} | An optimal schedule |
Dynamic Programming Algorithm for Wighted Interval Scheduling
Notation | Meaning |
\mathcal{O}_j | An optimal solution for the first j jobs. |
\text{OPT}(j) | Value of any optimal solution for first j jobs. I.e. \text{OPT}(j)=v(\mathcal{O}_j). |
p(j) | Largest index i< j such that i and j do not conflict (under the assumption that f_1\le f_2\le \cdots \le f_n). |