1. Machine Environment

1.1. Single Stage Problems

Each job comes with a given processing time.

1

there is a single machine

P

there are ${\displaystyle m}$ parallel identical machines

Q

there are ${\displaystyle m}$ parallel machines with different given speeds, length of job ${\displaystyle j}$ on machine ${\displaystyle i}$ is the processing time ${\displaystyle p_j}$ divided by speed ${\displaystyle s_i}$.

R

there are ${\displaystyle m}$ parallel unrelated machines, there are given processing times ${\displaystyle p_{ij}}$ for job ${\displaystyle j}$ on machine ${\displaystyle i}$

These letters might be followed by the number of machines which is then fixed, here ${\displaystyle m}$ stands then for a fixed number. For example, ${\displaystyle P2||C_{max}}$ is the problem of assigning each of the ${\displaystyle n}$ given jobs to one of the 2 given machines so to minimize the maximum total processing time over the machines.

1.2. Multi-Stage Problem

O

Open shop problem. Every job ${\displaystyle j}$ consists of ${\displaystyle m}$ operations ${\displaystyle O_{ij}}$ for ${\displaystyle i=1,\dots ,m}$. The operations can be scheduled in any order. Operation ${\displaystyle O_{ij}}$ must be processed for ${\displaystyle p_{ij}}$ units on machine ${\displaystyle i}$.

F

Flow shop problem. Every job ${\displaystyle j}$ consists of ${\displaystyle n_j}$ operations ${\displaystyle O_{ij}}$ for ${\displaystyle k=1,\dots ,n_j}$, to be scheduled in that order. Operation ${\displaystyle O_{ij}}$ must be processed for ${\displaystyle p_{ij}}$ units on machine ${\displaystyle i}$.

J

Job shop problem. Every job ${\displaystyle j}$ consists of ${\displaystyle n_j}$ operations ${\displaystyle O_{kj}}$ for ${\displaystyle k=1,\dots ,n_j}$, to be scheduled in that order. Operation ${\displaystyle O_{kj}}$ must be processed for ${\displaystyle p_{kj}}$ units on a dedicated machine ${\displaystyle {\mu }_{kj}}$ with ${\displaystyle {\mu }_{kj}\ne {\mu }_{k^{\prime }j}}$ for ${\displaystyle k\ne k^{\prime }}$.

2. Job Characteristics

The processing time may be equal for all jobs (${\displaystyle p_i=p}$, or ${\displaystyle p_{ij}=p}$) or even of unit length (${\displaystyle p_i=1}$, or ${\displaystyle p_{ij}=1}$). All processing times are assumed to be integers. In some older research papers however they are assumed to be rationals.

${\displaystyle r_j}$

for each job a release time is given before which it cannot be scheduled, default is 0.

${\displaystyle online-r_j}$

This is an online problem. Jobs are revealed at their release times. In this context the performance of an algorithm is measured by its competitive ratio.

${\displaystyle d_j}$

for each job a due date is given. The idea is that every job should complete before its due date and there is some penalty for jobs that complete late. This penalty is denoted in the objective value. The presence of the job characteristic ${\displaystyle d_j}$ is implicitly assumed and not denoted in the problem name, unless there are some restrictions as for example ${\displaystyle d_j=d}$, assuming that all due dates are equal to some given date.

${\displaystyle {\overline{d}}_j}$

for each job a strict deadline is given. Every job must complete before its deadline.

pmtn

Jobs can be preempted and resumed possibly on another machine. Sometimes also denoted by 'prmp'.

${\displaystyle siz{e}_j}$

Each job comes with a number of machines on which it must be scheduled at the same time, default is 1.

2.1. Precedence Relations

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

Given general precedence relation. If ${\displaystyle i\prec j}$ then starting time of ${\displaystyle j}$ should be not earlier than completion time of ${\displaystyle i}$.

chains

Given precedence relation in form of chains (indegrees and outdegrees are at most 1).

tree

Given general precedence relation in form of a tree, either intree or outtree.

intree

Given general precedence relation in form of an intree (outdegrees are at most 1).

outtree

Given general precedence relation in form of an outtree (indegrees are at most 1).

opposing forest

Given general precedence relation in form of a collection of intrees and outtrees.

sp-graph

Given precedence relation in form of a series parallel graph.

bounded height

Given precedence relation where the longest directed path is bounded by a constant.

level order

Given precedence relation where each vertex of a given level l (i.e. the length of the longest directed path starting from this vertex is l) is a predecessor of all the vertices of level l-1.

interval order

Given precedence relation for which one can associate to each vertex an interval in the real line, and there is a precedence between x and y if and only if the half open intervals x=[s_x,e_x) and y=[s_y,e_y) are such that e_x is smaller than or equal to s_y.

quasi-interval order

Quasi-interval orders are a superclass of interval orders defined in Moukrim: Optimal scheduling on parallel machines for a new order class, Operations Research Letters, 24(1):91-95, 1999.

over-interval order

Over-interval orders are a superclass of quasi-interval orders defined in Chardon and Moukrim: The Coffman-Graham algorithm optimally solves UET task systems with overinterval orders, SIAM Journal on Discrete Mathematics, 19(1):109-121, 2005.

Am-order

Am orders are a superclass of over-interval orders defined in Moukrim and Quilliot: A relation between multiprocessor scheduling and linear programming. Order, 14(3):269-278, 1997.

DC-graph

A divide-and-conquer graph is a subclass of series-parallel graphs defined in Kubiak et al.: Optimality of HLF for scheduling divide-and-conquer UET task graphs on identical parallel processors. Discrete Optimization, 6:79-91, 2009.

2-dim partial order

A 2-dimensional partial order is a k-dimensional partial order for k=2.

k-dim partial order

A poset is a k-dimensional partial order iff it can be embedded into the k-dimensional Euclidean space in such a way that each node is represented by a k-dimensional point and there is a precedence between two nodes i and j iff for any dimension the coordinate of i is smaller than or equal to the one of j.

In the presence of a precedence relation one might in addition assume time lags. Let ${\displaystyle S_j}$ denote the start time of a job and ${\displaystyle C_j}$ its completion time. Then the precedence relation ${\displaystyle i\prec j}$ implies the constraint ${\displaystyle C_i+l_{ij}\le S_j}$. If no time lag ${\displaystyle l_{ij}}$ is specified then it is assumed to be zero. Time lags can be positive or negative numbers.

l

job independent time lags. In other words ${\displaystyle l_{ij}=l}$ for all job pairs i, j and a given number l.

${\displaystyle l_{ij}}$

job pair dependent arbitrary time lags.

2.2. Transportation Delays

${\displaystyle t_{jk}}$

Between the completion of operation ${\displaystyle O_{kj}}$ of job ${\displaystyle j}$ on machine ${\displaystyle k}$ and the start of operation ${\displaystyle O_{k+1,j}}$ of job ${\displaystyle j}$ on machine ${\displaystyle k+1}$, there is a transportation delay of at least ${\displaystyle t_{jk}}$units.

${\displaystyle t_{jkl}}$

Between the completion of operation ${\displaystyle O_{kj}}$ of job ${\displaystyle j}$ on machine ${\displaystyle k}$ and the start of operation ${\displaystyle O_{l,j}}$ of job ${\displaystyle j}$ on machine ${\displaystyle l}$, there is a transportation delay of at least ${\displaystyle t_{jkl}}$ units.

${\displaystyle t_k}$

Machine dependent transportation delay. Between the completion of operation ${\displaystyle O_{kj}}$ of job ${\displaystyle j}$ on machine ${\displaystyle k}$ and the start of operation ${\displaystyle O_{k+1,j}}$ of job ${\displaystyle j}$ on machine ${\displaystyle k+1}$, there is a transportation delay of at least ${\displaystyle t_k}$ units.

${\displaystyle t_{kl}}$

Machine pair dependent transportation delay. Between the completion of operation ${\displaystyle O_{kj}}$ of job ${\displaystyle j}$ on machine ${\displaystyle k}$ and the start of operation ${\displaystyle O_{l,j}}$ of job ${\displaystyle j}$ on machine ${\displaystyle l}$, there is a transportation delay of at least ${\displaystyle t_{kl}}$ units.

${\displaystyle t_j}$

Job dependent transportation delay. Between the completion of operation ${\displaystyle O_{kj}}$ of job ${\displaystyle j}$ on machine ${\displaystyle k}$ and the start of operation ${\displaystyle O_{l,j}}$ of job ${\displaystyle j}$ on machine ${\displaystyle l}$, there is a transportation delay of at least ${\displaystyle t_j}$ units.

2.3. Various Constraints

rcrc

Recirculation, also called Flexible job shop. The promise on ${\displaystyle \mu }$ is lifted and for some pairs ${\displaystyle k\ne k^{\prime }}$ we might have ${\displaystyle {\mu }_{kj}={\mu }_{k^{\prime }j}}$.

no-wait

The operation ${\displaystyle O_{k+1,i}}$must start exactly when operation ${\displaystyle O_{k,i}}$ completes. Sometimes also denoted as 'nwt'.

no-idle

No machine is ever idle between two executions.

${\displaystyle siz{e}_j}$

Multiprocessor tasks on identical parallel machines. The execution of job ${\displaystyle j}$ is done simultaneously on ${\displaystyle siz{e}_j}$parallel machines.

${\displaystyle fi{x}_j}$

Multiprocessor tasks. Every job ${\displaystyle j}$is given with a set of machines ${\displaystyle fi{x}_j\subseteq \{1,\dots ,m\}}$, and needs simultaneously all these machines for execution. Sometimes also denoted by 'MPT'.

${\displaystyle M_j}$

Multipurpose machines. Every job ${\displaystyle j}$needs to be scheduled on one machine out of a given set ${\displaystyle M_j\subseteq \{1,\dots ,m\}}$. Sometimes also denoted by 'M_j'.

3. Objective Functions

Usually the goal is to minimize some objective value. One difference is the notation ${\displaystyle \sum U_j}$ where the goal is to maximize the number of jobs that complete before their deadline. This is also called the throughput. The objective value can be sum, possibly weighted by some given priority weights ${\displaystyle w_j}$ per job.

-

The absence of an objective value is denoted by a single dash. This means that the problem consists simply in producing a feasible scheduling, satisfying all given constraints.

${\displaystyle C_j}$

This denotes the completion time of job ${\displaystyle j}$.

${\displaystyle F_j}$

The flow time of a job is difference between its completion time and its release time, i.e. ${\displaystyle F_j=C_j-r_j}$.

${\displaystyle L_j}$

Lateness. Every job ${\displaystyle j}$ is given a due date ${\displaystyle d_j}$. The lateness of job ${\displaystyle j}$ is defined as ${\displaystyle C_j-d_j}$. Sometimes ${\displaystyle L_{max}}$ is used to denote feasibility for a problem with deadlines. Indeed using binary search, the complexity of the feasibility version is equivalent to the minimization of ${\displaystyle L_{max}}$.

${\displaystyle U_j}$

Throughput. Every job is given a due date ${\displaystyle d_j}$. There is a unit profit for jobs that complete one time, i.e. ${\displaystyle U_j=1}$ if ${\displaystyle C_j\le d_j}$ and ${\displaystyle U_j=0}$ otherwise. Sometimes the meaning of ${\displaystyle U_j}$ is inverted in the literature, which is equivalent when considering the decision version of the problem, but which makes a huge difference for approximations.

${\displaystyle T_j}$

Tardiness. Every job ${\displaystyle j}$ is given a due date ${\displaystyle d_j}$. The tardiness of job ${\displaystyle j}$ is defined as ${\displaystyle T_j=max\{0,C_j-d_j\}}$.

${\displaystyle E_j}$

Earliness. Every job ${\displaystyle j}$ is given a due date ${\displaystyle d_j}$. The earliness of job ${\displaystyle j}$ is defined as ${\displaystyle E_j=max\{0,d_j-C_j\}}$. This objective is important for just-in-time' scheduling.

4. Examples

Adapted from ^[1]

1|prec|${\displaystyle L_{max}}$

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

R|pmtn|${\displaystyle \sum C_i}$

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

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

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

P|${\displaystyle siz{e}_j}$|${\displaystyle C_{max}}$

${\displaystyle m}$ parallel identical machines, each job comes with a number of machines on which it must be scheduled at the same time, minimizing maximum completion time (see also parallel task scheduling problem).