| n | number of jobs to be scheduled |
|---|---|
| m | number of machines |
| aj,k | start lag |
| bj,k | stop lag |
| dj | due date |
| lj | lag time |
| pj,k | processing time |
| rj | ready date |
| sj1,j2,k | setup time |
| tj,k | total time = pj,k + sj,k |
| wj | weight |
These parameters will all be known in advance by the scheduler.
Each job will be subscripted by a j
, and each machine by a k
(unless there is only one machine,
in which case its subscript is usually omitted).
| Cj,k | completion date |
|---|---|
| Ej,k | earliness = max{ 0,−Lj } |
| Fj | flow time = Cj − rj |
| Lj | lateness = Cj − dj |
| M | makespan = max{ Cj } |
| Np | number of jobs with property p |
| Sj,k | start date = Cj,k − tj,k |
| Tj | tardiness = max{ 0, Lj } |
| Wj | waiting time = Fj − tj |
These values may be determined from the above parameters for any given schedule. It is our aim to find schedules optimizing some of these measures of performance.
If each job must be processed on all machines and occupy the machines in the same order as all other jobs, flowshop If the order of processing need not be the same for all jobs or if a job may be processed on the same machine more than once, jobshop In either case, no job may be processed by more than one machine at the same time.
If in a given schedule there exist times t1 and t2 such that 0 ≤ t1 < t2 ≤ M during which a machine is not processing any job, then the interval (t1, t2) idle time If there is an interval (t1, t2) during which the machine is idle, and there is at least one job j such that rj ≤ t1 < t2 ≤ Cj and Ci ≤ t1 for all predecessors i of j, inserted idle time During such an interval the machine is idle, but there is at least one job available for processing.
In a situation without preemption, once a job begins processing on a machine, it continues without interruption on that machine until completed. If instead at some time before its completion, the job is removed from the machine and then later allowed to finish its processing, the job is said to preempted When the job is returned to the machine, if it may resume processing in the same state in which it was when preempted preempt-resume If instead the job has to start processing all over again, the situation is preempt-repeat
In a processor sharing model, more than one job may be assigned to a machine at the same time. Associated with each job t is a non-negative value, Rj(t) ≤ 1, indicating the rate at which it is processed at any time t. A 0 value indicates that the job is not being processed, while a 1 value indicates that one of the machines is dedicated to processing the job. Fractional values mean that the job is sharing one of the machines with other jobs and is thus being processed at less than full rate. At any time t, we require that ∑{ R(t):∀ j } (i.e. the sum of Rj(t) over all jobs j) be no greater than m in order to ensure that no machine is processing jobs faster than its maximum rate. For each job j we require that ∫ Rj(t)dt be equal to tj in order to ensure that the job has all of its processing completed.
If a schedule can be represented by a permutation of the job names (numbers) then the schedule is known as a permutation schedule For any set of n jobs, there are exactly n! (n factorial) different permutation schedules. Such schedules cannot contain preemptions, and in a flow-shop or job-shop all jobs must be processed in the same order on each machine.