# Notation for theoretic scheduling problems

A convenient notation for theoretic scheduling problems was introduced by Ronald Graham, Eugene Lawler, Jan Karel Lenstra and Alexander Rinnooy Kan in.[1] It consists of three fields: α, β and γ.

Each field may be a comma separated list of words. The α field describes the machine environment, β the job characteristics, and γ the objective function.

## Machine environment

### Single stage problems

Each job comes with a given processing time.

1
there is a single machine
P
there are $m$ parallel identical machines
Q
there are $m$ parallel machines with different given speeds, length of job $i$ on machine $j$ is the processing time $p_{i}$ divided by speed $s_j$
R
there are $m$ parallel unrelated machines, there are given processing times $p_{ij}$ for job $i$ on machine $j$

The last three letters might be followed by the number of machines which is then fixed, here $m$ stands then for a fixed number.

### Multi-stage problem

open shop problem
flow shop problem
job shop problem

## Job characteristics

The processing time may be equal for all jobs ($p_i=p$, or $p_{ij}=p$) or even of unit length ($p_i=1$, or $p_{ij}=1$). This makes a difference because all release times, deadlines are assumed to be integer.

$r_i$
for each job a release time is given before which it cannot be scheduled, default is 0.
$d_i$
for each job a deadline is given after which it cannot be scheduled. If the objective is $\sum U_i$ for example, then this field is implicitly assumed.
pmtn
the jobs may be preempted and execution resumed later, possibly on a different machine
$size_i$
Each job comes with a number of machines on which it must be scheduled at the same time, default is 1.

Precedence relations might be given for the jobs, in form of a partial order, meaning that if i is a predecessor of i' in that order, i' can start only when i is completed.

prec
an arbitrary precedence relation is given
sp-tree, tree, intree, outtree, chain
specific partial orders

## Objective functions

Most objective functions depend on the deadline $d_i$ and the completion time $C_i$ of job $i$. We define lateness $L_i=C_i-d_i$, earliness $E_i = \max\{0, d_i-C_i\}$, tardiness $T_i = \max\{0, C_i-d_i\}$, unit penalty $U_i = 0$ if $C_i\le d_i$ and $U_i=1$ otherwise. The common objective functions are $C_\max, L_\max, E_\max, T_\max, \sum C_i, \sum L_i, \sum E_i, \sum T_i$ or weighted version of these sums, where every job comes with a priority $w_i$.

## Examples

1|prec|$L_\max$
R|pmtn|$\sum C_i$
J3|$p_{ij}$|$C_\max$