Notation for theoretic scheduling problems

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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[edit]

Single stage problems[edit]

Each job comes with a given processing time.

there is a single machine
there are m parallel identical machines
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
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[edit]

open shop problem
flow shop problem
job shop problem

Job characteristics[edit]

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.

for each job a release time is given before which it cannot be scheduled, default is 0.
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.
the jobs may be preempted and execution resumed later, possibly on a different machine
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.

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

Objective functions[edit]

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.


Adapted from [1]

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.
3-machines job shop with unit processing times, minimizing maximum completion time.


  1. ^ a b 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.