Notation for theoretic scheduling problems

﻿
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. 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 pi divided by speed sj
R
there are m parallel unrelated machines, there are given processing times pij for job i on machine j

The last two letters might be followed by a 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 (pi = p, or pij = p) or even of unit length (pi = 1, or pij = 1). This makes a difference because all release times, deadlines are assumed to be integer.

ri
for each job a release time is given before which it cannot be scheduled, default is 0.
di
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
sizei
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 di and the completion time Ci of job i. We define lateness Li = Cidi, earliness Ei = max{0,diCi}, tardiness Ti = max{0,Cidi}, unit penalty Ui = 0 if $C_i\le d_i$ and Ui = 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 wi.

References

Wikimedia Foundation. 2010.

Look at other dictionaries:

• Scheduling — is the process of deciding how to commit resources between a variety of possible tasks. Time can be specified (scheduling a flight to leave at 8:00) or floating as part of a sequence of events.Scheduling may refer to: * I/O scheduling, the order… …   Wikipedia

• Mathematical economics — Economics …   Wikipedia

• List of algorithms — The following is a list of the algorithms described in Wikipedia. See also the list of data structures, list of algorithm general topics and list of terms relating to algorithms and data structures.If you intend to describe a new algorithm,… …   Wikipedia

• List of mathematics articles (S) — NOTOC S S duality S matrix S plane S transform S unit S.O.S. Mathematics SA subgroup Saccheri quadrilateral Sacks spiral Sacred geometry Saddle node bifurcation Saddle point Saddle surface Sadleirian Professor of Pure Mathematics Safe prime Safe… …   Wikipedia

• combinatorics — /keuhm buy neuh tawr iks, tor , kom beuh /, n. (used with singular v.) See combinatorial analysis. * * * Branch of mathematics concerned with the selection, arrangement, and combination of objects chosen from a finite set. The number of possible… …   Universalium

• Time — This article is about the measurement. For the magazine, see Time (magazine). For other uses, see Time (disambiguation). The flow of sand in an hourglass can be used to keep track of elapsed time. It also concretely represents the present as… …   Wikipedia