Premium
An evaluation of scheduling heuristics for dynamic single‐processor scheduling with early/tardy costs
Author(s) -
Robb David J.,
Rohleder Thomas R.
Publication year - 1996
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/(sici)1520-6750(199604)43:3<349::aid-nav3>3.0.co;2-9
Subject(s) - heuristics , preemption , computer science , scheduling (production processes) , dynamic priority scheduling , pairwise comparison , operations research , rate monotonic scheduling , mathematical optimization , fair share scheduling , heuristic , fixed priority pre emptive scheduling , execution time , distributed computing , artificial intelligence , mathematics , schedule , operating system
In an endeavor to broaden the application of scheduling models to decisions involving the use of a manager's time we 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. We compare these simple methods relative to a bound that uses an adjacent pairwise interchange algorithm. We model uncertainty in task durations, and costs being incurred for early and tardy task completion (representative of JIT settings). In addition to evaluating the efficacy of the scheduling rules and various preemption strategies (using ANOVA), we highlight the managerial implications of the effects of eight environmental parameters. © 1996 John Wiley & Sons, Inc.