The Scheduling Problem


  RIOT HOME

 Scheduling Problem
 Instructions
 Definitions
 Machine Environments
 Algorithms
 Objectives
 Try It!

Definitions

 

            There are a myriad of terms related to scheduling problems.  This page provides an explanation of each term as a quick reference for the user.

 

Job:  A job can be made up of any number of tasks.  It is easy to think of a job as making a product, and each task as an activity that contributes to making that product, such as a paint task.  A job usually has only a single task.  The exceptions are the cases of job shop and flow shop where a job is broken down into tasks because different orders of tasks make up different schedules.

 

Precedence:  Some jobs must be done before other jobs.  In addition, each job also has a specific order of performing the tasks of that job.  This order is referred to as a precedence constraint.

 

Machine:  A machine is available to execute jobs and tasks.  Different machine environments exist, such as single machine and parallel machines.  For a more detailed explanation, see the machine environments page.

 

Ready Time: Time at which a job begins to be available for processing, denoted by "r".  For example, a job may be ready at a later time than time 0 because it has not been completed in the last shop. 

 

Processing Time:  Length of time to process a job or a task, denoted by "t".

 

Completion Time:  Time at which a job is finished, denoted by "C".

 

Flow Time: Amount of time job i spends in the system.  Fi=Ci-ri, where Ci is the completion time of the ith job, and ri is the ready time of the ith job.

 

Waiting Time:  Length of time between the ready time of a job and the beginning of processing of a job, denoted by "W".

 

Slack Time:  Time until a job's due date minus the processing time of a job.

 

Due Date: Last "time" to complete a job, denoted by "d".

 

Lateness:  Difference between completion time and the due date.  Li=Ci-di, where Ci is the completion of job i and di is the due date of job i.

 

Tardiness:  The tardiness of job i, Ti, is defined as Ti=Max (0, Ci-di),  where Ci is the completion of job i and di is the due date of job i.


[Scheduling Problem Instructions Definitions Machine Environments Algorithms Objectives Try It! ]

RIOT HOME


Copyright 1999 Professor Dorit S. Hochbaum