|The Scheduling Problem|
Machine: Only one machine is available to process jobs.
Each job has a single task. Every
job is performed on the same machine.
Machines: Multiple machines are available to process jobs.
The machines can be identical, of different speeds, or specialized to
only processing specific jobs. Each
job has a single task.
Shop: In the general flow shop model, there are a series of
machines numbered 1,2,3ům. Each job has exactly m tasks. The first task of every job is done on machine 1, second task
on machine 2 and so on. Every job
goes through all m machines in a unidirectional order. However, the processing time each task spends on a machine
varies depending on the job that the task belongs to.
In cases where not every job has m tasks, the processing times of the
tasks that don't exist are zero. The
precedence constraint in this model requires that for each job, task i-1 on
machine i-1 must be completed before the ith task can begin on
Shop: In the general job shop model, there are a set of machines
indexed by k. Jobs are indexed by i,
and tasks are indexed by j. Each
task on a machine is indicated by a set of three indices, i, the job that the
task belongs to, j, the number of the task itself, and k, the machine that this
particular task needs to use. The
flow of the tasks in a job does not have to be unidirectional.
Each job may also use a machine more than once.
For example, the following table describes a job shop with two jobs.
The entries denote the machine that task j of job i needs.
Job 1 has only two tasks, requiring machine 5 and 6 respectively.
Job two has three tasks, requiring machine 2, 7, and then machine 2