1.1 Definitions

1.1.1 Given Parameters

nnumber of jobs to be scheduled
mnumber of machines
aj,kstart lag
bj,kstop lag
djdue date
ljlag time
pj,kprocessing time
rjready date
sj1,j2,ksetup time
tj,ktotal time = pj,k + sj,k
Known Values

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).

1.1.2 Schedule Values

Cj,kcompletion date
Ej,kearliness = max{ 0,−Lj }
Fjflow time = Cj − rj
Ljlateness = Cj − dj
Mmakespan = max{ Cj }
Npnumber of jobs with property p
Sj,kstart date = Cj,k − tj,k
Tjtardiness = max{ 0, Lj }
Wjwaiting time = Fj − tj
Optimizable Values

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.

1.1.3 Flowshops and Jobshops

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.

1.1.4 Idle 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.

1.1.5 Preemption

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

1.1.6 Processor Sharing

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.

1.1.7 Permutation Schedules

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.