GENERALIZED PREEMPTION MODELS FOR SINGLE-MACHINE DYNAMIC SCHEDULING PROBLEMS

In the extensive scheduling literature, job preemption, if allowed, im plies that the processing of a partly completed job is temporarily hal ted and later resumed at the same point. However, little attention has been given to problems where job preemption is allowed under the cond ition that either some startup time delay must be incurred or some fra ction of work must be repeated if preemption occurs. We generalize the notion of job preemption by using models representing these condition s. The models are applied to studying the dynamic single-machine sched uling problems of minimizing total flow time, and of minimizing maximu m lateness, subject to arbitrary and unknown job ready dates. On-line optimal dispatching rules, which consider only available - as opposed to look-ahead - information, are developed. These rules determine, on arrival or completion of each job, which available job should next be processed by the machine. A special case of our models, the preempt-re peat scenario, where preempted jobs must be totally repeated, is sugge sted as heuristic for the equivalent non-preemptive static problem whe re all ready dates are known and given. A computational study is perfo rmed to determine the potential benefits of reducing startup time dela ys or work repetition fractions in the context of continuous improveme nt of manufacturing systems.