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, load balancing, 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:
1: Single-machine scheduling. There is a single machine. P: Identical-machines scheduling. There are m {\displaystyle m} parallel machines, and they are identical. Job j {\displaystyle j} takes time p j {\displaystyle p_{j}} on any machine it is scheduled to. Q: Uniform-machines scheduling. There are m {\displaystyle m} parallel machines, and they have different given speeds. Job j {\displaystyle j} on machine i {\displaystyle i} takes time p j / s i {\displaystyle p_{j}/s_{i}} . R: Unrelated-machines scheduling. There are m {\displaystyle m} parallel machines, and they are unrelated – Job j {\displaystyle j} on machine i {\displaystyle i} takes time p i j {\displaystyle p_{ij}} . 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:
… excerpt ends here. Continue reading the full article.
