Notation for theoretic scheduling problems
||This article needs attention from an expert in Mathematics. (November 2008)|
Each field may be a comma separated list of words. The α field describes the machine environment, β the job characteristics, and γ the objective function.
Single stage problems
Each job comes with a given processing time.
- there is a single machine
- there are parallel identical machines
- there are parallel machines with different given speeds, length of job on machine is the processing time divided by speed
- there are parallel unrelated machines, there are given processing times for job on machine
The last three letters might be followed by the number of machines which is then fixed, here stands then for a fixed number.
The processing time may be equal for all jobs (, or ) or even of unit length (, or ). 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 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
Most objective functions depend on the deadline and the completion time of job . We define lateness , earliness , tardiness , unit penalty if and otherwise. The common objective functions are or weighted version of these sums, where every job comes with a priority .
Adapted from 
- a single machine, general precedence constraint, minimizing maximum lateness.
- variable number of unrelated parallel machines, allowing preemption, minimizing total completion time.
- 3-machines job shop with unit processing times, minimizing maximum completion time.
- 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
- Graham, R. L.; Lawler, E. L.; Lenstra, J.K.; Rinnooy Kan, A.H.G. (1979). "Optimization and Approximation in Deterministic Suquencing 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.