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.  F_i=C_i-r_i, where C_i is the completion time of the i^th job, and r_i is the ready time of the i^th 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.  L_i=C_i-d_i, where C_i is the completion of job i and d_i is the due date of job i.

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