Scheduling Problem
 Instructions
 Definitions
 Machine Environments
 Algorithms
 Objectives
 Try It!

Machine Environments

Single Machine:  Only one machine is available to process jobs.  Each job has a single task.  Every job is performed on the same machine.

Parallel 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.

Flow 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 i^th task can begin on machine i.

Job 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 again.