The required output is a schedule – an assignment of jobs to machines.
There are many different problems of optimal job scheduling, different in the nature of jobs, the nature of machines, the restrictions on the schedule, and the objective function.
A convenient notation for optimal scheduling problems was introduced by Ronald Graham, Eugene Lawler, Jan Karel Lenstra and Alexander Rinnooy Kan.[1][2] It consists of three fields: α, β and γ.
The α field describes the machine environment, β the job characteristics and constraints, and γ the objective function.
[3] Since its introduction in the late 1970s the notation has been constantly extended, sometimes inconsistently.
As a result, today there are some problems that appear with distinct notations in several papers.
Pm indicates that there are m parallel identical machines, where m is a fixed parameter.
In contrast, P indicates that there are m parallel identical machines, but m is not fixed (it is part of the input).
In multi-stage job scheduling problems, there are other options for the machine environments: All processing times are assumed to be integers.
In the presence of a precedence relation one might in addition assume time lags.
where the goal is to maximize the number of jobs that complete before their deadline.