Scheduling Notation

computation scheduling

Definition

Scheduling Notation

Scheduling notation is the three-field notation

$$\alpha \mid \beta \mid \gamma$$

for classifying a scheduling problem. The field $\alpha$ describes the machine environment, $\beta$ describes job characteristics and constraints, and $\gamma$ describes the objective function.

Machine environment

The field $\alpha$ describes the machines and the operational structure of each job.

For single-stage jobs, each job has one operation.

Except for the special case $\alpha =1$, a single-stage machine environment has the form

$$T_m,$$

where $T$ is the machine type and $m$ is the number of machines.

Notation	Meaning
$1$	one machine
$P_m$	$m$ identical parallel machines
$Q_m$	$m$ uniform parallel machines with different speeds
$R_m$	$m$ unrelated parallel machines

If $m$ is omitted, the number of machines is part of the input. For example, $P$ denotes an arbitrary number of identical parallel machines.

Thus $T$ is not an additional fourth field. It is the first part of $\alpha$ in environments such as $P_m$, $Q_m$, and $R_m$.

For identical machines, job $j$ has the same processing time $p_j$ on every machine. For uniform machines, machine $i$ has speed $s_i$, so job $j$ takes time

$$\frac{p_j}{s_i}$$

on machine $i$. For unrelated machines, the processing time depends directly on the pair $(i,j)$ and is written $p_{ij}$.

Shop environments

For multi-stage jobs, each job consists of several operations. Usually, only one operation of the same job may be processed at a time.

Shop environments use the same pattern $T_m$, but now $T$ describes the order structure of operations rather than only the speed relation between machines.

Notation	Name	Structure
$O_m$	open shop	operations may be scheduled in any order
$F_m$	flow shop	operations follow the same fixed machine order for every job
$J_m$	job shop	each job has its own fixed operation order

As before, $m$ may be omitted when the number of machines is variable or clear from context.

In an open-shop or flow-shop instance, job $j$ has operations $O_{ij}$ for $i=1,\dots ,q$. Operation $O_{ij}$ must be processed on machine $i$ and takes time $p_{ij}$.

In a job-shop instance, job $j$ has operations $O_{kj}$ for $k=1,\dots ,q_j$. Operation $O_{kj}$ must be processed on machine ${\mu }_{kj}$ and takes time $p_{kj}$. The machines for different operations of the same job are usually distinct:

$${\mu }_{kj}\ne {\mu }_{k^{\prime }j}\text{for }k\ne k^{\prime }.$$

Job constraints

The field $\beta$ lists additional job characteristics and constraints.

Notation	Meaning
$r_j$	release time; job $j$ cannot be processed before time $r_j$
$d_j$	due date; lateness may be allowed but penalised
${\bar{d}}_j$	strict deadline; job $j$ must complete by ${\bar{d}}_j$
$\mathrm{pmtn}$	preemption is allowed
$\mathrm{prec}$	precedence constraints are present

Preemption means that a job may be stopped and resumed later, possibly on another machine. A precedence constraint is a partial order on jobs. If $i\prec j$, then job $j$ may start only after job $i$ has completed.

Objectives

The field $\gamma$ states the quantity to optimise. Unless stated otherwise, the objective is minimisation.

For a schedule, define for each job $j$:

$$L_j=C_j-d_j,U_j=\{\begin{array}{ll}1& \text{if }{C}_j>d_j,\\ 0& \text{otherwise.}\end{array}$$

Here $C_j$ is the completion time, $L_j$ is the lateness, and $U_j$ is the unit penalty for missing the due date.

Objective	Meaning
absent	find any feasible schedule
${\sum }_j{U}_j$	minimise the number of late jobs, equivalently maximise on-time throughput
$L_{\max }$	minimise maximum lateness
$C_{\max }$	minimise makespan
${\sum }_j{C}_j$	minimise total completion time, equivalently average completion time

Conventions

Variants

Scheduling notation is not completely uniform in the literature. Some authors omit $d_j$ from $\beta$ when the objective already contains $L_j$ or $U_j$, since those objectives require due dates. Some authors also write $d_j$ instead of ${\bar{d}}_j$ when strict deadlines are clear from context.

Most scheduling models use integer input parameters unless another domain is stated explicitly.

Scheduling Zoo

Definition

Scheduling Zoo

The scheduling zoo

Link to original

Examples

Writing notation

One machine with no additional constraints and objective of minimising makespan is written as

$$1\mid \varnothing \mid C_{\max }.$$

Three identical machines with precedence constraints and deadlines, where the task is to check whether every job can meet its deadline, can be written as

$$P_3\mid \mathrm{prec},{\bar{d}}_j\mid \sum _j{U}_j=0.$$

Two uniform machines with release times and objective of minimising average completion time can be written as

$$Q_2\mid r_j\mid \frac{1}{n}\sum _j{C}_j.$$

Since $n$ is fixed for an instance, this is equivalent to minimising ${\sum }_j{C}_j$.

Reading notation

The notation

$$1\mid r_j,{\bar{d}}_j\mid \sum _j{U}_j$$

means a single-machine problem where each job has a release time and a strict deadline. The objective is to minimise the number of jobs completed after their deadlines, or equivalently to maximise the number completed on time.

The notation

$$1\mid r_j\mid \sum _j{C}_j$$

means a single-machine problem where each job has a release time. The objective is to minimise the total completion time, equivalently the average completion time.

The notation

$$R\mid \mathrm{pmtn},r_j\mid L_{\max }$$

means an unrelated-parallel-machine problem with a variable number of machines. Jobs have release times and may be preempted. The objective is to minimise the maximum lateness.

Room booking

A room can host at most one event at a time. Each event has a fixed interval $[r_j,{\bar{d}}_j)$ and processing time

$$p_j={\bar{d}}_j-r_j.$$

The problem of booking the maximum number of compatible events can be written as

$$1\mid r_j,{\bar{d}}_j,p_j={\bar{d}}_j-r_j\mid \sum _j{U}_j.$$

This is the interval scheduling problem when each selected job must occupy its given interval.
If $p_j$ is not forced to equal ${\bar{d}}_j-r_j$, then even feasibility on one machine becomes hard; see a deadline gap can hide subset sum.

Two-machine factory scheduling

Suppose there are two identical machines and each job $j$ has release time $r_j$, due date $d_j$, and processing time $p_j$. The decision version asks whether all jobs can be completed by their due dates. One notation is

$$P_2\mid r_j,d_j\mid \sum _j{U}_j=0.$$

The equality expresses the decision requirement that no job is late.