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

O 

open shop problem

F 

flow shop problem

J 

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

Adapted from ^[1]

1|prec|$L_\max$

a single machine, general precedence constraint, minimizing maximum lateness.

R|pmtn|$\sum C_i$

variable number of unrelated parallel machines, allowing preemption, minimizing total completion time.

J3|$p_{ij}$|$C_\max$

3-machines job shop with unit processing times, minimizing maximum completion time.

References

• B. Chen, C.N. Potts and G.J. Woeginger. "A review of machine scheduling: Complexity, algorithms and approximability". Handbook of Combinatorial Optimization (Volume 3) (Editors: D.-Z. Du and P. Pardalos), 1998, Kluwer Academic Publishers. 21-169. ISBN 0-7923-5285-8 (HB) 0-7923-5019-7 (Set)
• Peter Brucker, Sigrid Knust. Complexity results for scheduling problems

1. Graham, R. L.; Lawler, E. L.; Lenstra, J.K.; Rinnooy Kan, A.H.G. (1979). "Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey". Proceedings of the Advanced Research Institute on Discrete Optimization and Systems Applications of the Systems Science Panel of NATO and of the Discrete Optimization Symposium. Elsevier. pp. (5) 287–326.