n | number of jobs to be scheduled |
---|---|

m | number of machines |

a_{j,k} | start lag |

b_{j,k} | stop lag |

d_{j} | due date |

l_{j} | lag time |

p_{j,k} | processing time |

r_{j} | ready date |

s_{j1,j2,k} | setup time |

t_{j,k} | total time = p_{j,k} + s_{j,k} |

w_{j} | 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).

C_{j,k} | completion date |
---|---|

E_{j,k} | earliness = max{ 0,−L_{j} } |

F_{j} | flow time = C_{j} − r_{j} |

L_{j} | lateness = C_{j} − d_{j} |

M | makespan = max{ C_{j} } |

N_{p} | number of jobs with property p |

S_{j,k} | start date = C_{j,k} − t_{j,k} |

T_{j} | tardiness = max{ 0, L_{j} } |

W_{j} | waiting time = F_{j} − t_{j} |

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
`t _{1}` and

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,
`R _{j}(t) ≤ 1`,
indicating the rate at which it is processed at any time

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.