Optimal job scheduling is a class of optimization problems related to scheduling. The inputs to such problems are a list of jobs (also called processes or tasks) and a list of machines (also called processors or workers). The required output is a schedule – an assignment of jobs to machines. The schedule should optimize a certain objective function. In the literature, problems of optimal job scheduling are often called machine scheduling, processor scheduling, multiprocessor scheduling, or just scheduling. 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. 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 constraints, and γ the objective function. 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.

Single-stage jobs vs. multi-stage jobs

In the simpler optimal job scheduling problems, each job j consists of a single execution phase, with a given processing time pj. In more complex variants, each job consists of several execution phases, which may be executed in sequence or in parallel.

Machine environments

In single-stage job scheduling problems, there are four main categories of machine environments: These letters might be followed by the number of machines, which is then fixed. For example, P2 indicates that there are two parallel identical machines. 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:

Job characteristics

All processing times are assumed to be integers. In some older research papers however they are assumed to be rationals.

Precedence relations

Each pair of two jobs may or may not have a precedence relation. A precedence relation between two jobs means that one job must be finished before the other job. For example, if job i is a predecessor of job j in that order, job j can only start once job i is completed. [sx,ex) and job x is a predecessor of y if and only if the end of the interval of x is strictly less than the start of the interval for y.= In the presence of a precedence relation one might in addition assume time lags. The time lag between two jobs is the amount of time that must be waited after the first job is complete before the second job to begin. Formally, if job i precedes job j, then must be true. If no time lag \ell_{ij} is specified then it is assumed to be zero. Time lags can also be negative. A negative time lag means that the second job can begin a fixed time before the first job finishes.

Transportation delays

Various constraints

Objective functions

Usually the goal is to minimize some objective value. One difference is the notation \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 w_j per job. There are also variants with multiple objectives, but they are much less studied.

Examples

Here are some examples for problems defined using the above notation.

Other variants