|The Scheduling Problem|
There are a myriad of terms related to scheduling problems.
This page provides an explanation of each term as a quick reference for
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
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.
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.
Time: Length of time to process a job or a task, denoted by
Time: Time at which a job is finished, denoted by "C".
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.
Time: Length of time between the ready time of a job and the
beginning of processing of a job, denoted by "W".
Time: Time until a job's due date minus the processing time of a
"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.
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.