MACHINE SCHEDULING

1.4 Ready Dates

In this section we consider single machine scheduling in which some or all jobs may not be initially available. Such a model is known as a dynamic scheduling problem, as the set of jobs available for processing changes with time. Under the preempt-resume model, inserted idle time may be removed, and so schedules without inserted idle time are a dominant set. Under the preempt-repeat model, preemptions and any inserted idle time not necessitated by a ready date may be removed, and so permutation schedules are a dominant set under preempt-repeat even though the schedules may contain inserted idle time.

1.4.1 Dispatching Rules

In a dynamic model there are two kinds of decision points: when a job becomes available, and when a machine becomes available. Any rule that allows one to construct an optimal schedule by choosing the job to be processed next at such a decision point using no information about jobs that are not yet available is known as a dispatching rule. Under the preempt-repeat model where inserted idle time may be required, a dispatching rule may not be optimal.

1.4.2 Minimizing Mean Lateness

Under a preempt-resume model, mean lateness (with ready dates) may be minimized by a dispatching rule known as SRPT (shortest remaining process time). At each decision point, the available but incompleted job requiring the smallest amount of processing to be completed is scheduled. This rule is sufficient but not necessary for constructing an optimal schedule.

1.4.3 Minimizing Maximum Lateness

Under a preempt-resume model, maximum lateness (with ready dates) may be minimized by a dispatching rule known as DEDD (dynamic earliest due date). At each decision point the available but uncompleted job with the earliest due date is scheduled. This rule is sufficient but not necessary for constructing an optimal schedule.