An evaluation of scheduling heuristics for dynamic single-processor scheduling with early/tardy costs

In an endeavor to broaden the application of scheduling models to decisions involving the use of a manager’s time the authors use simulation to investigate the performance of a number of simple algorithms (including eight priority rules and a construction heuristic) in a dynamic setting with tasks arriving (randomly) and scheduling decisions being made, over time. They compare these simple methods relative to a bound that uses an adjacent pairwise interchange algorithm. The authors model uncertainty in task durations, and costs being incurred for early and tardy task completion (representative of JIT settings). In additon to evaluating the efficacy of the scheduling rules and various preemption strategies (using ANOVA), they highlight the managerial implications of the effects of eight environmental parameters.