The Scheduling Problem 
RIOT HOME
Scheduling Problem 
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.
