The Scheduling Problem


 Scheduling Problem
 Machine Environments
 Try It!



            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! ]


Copyright 1999 Professor Dorit S. Hochbaum