Share Email Print

Proceedings Paper

Comparison of three scheduling algorithms
Author(s): William J. Wolfe; Stephen E. Sorensen
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper Abstract

This paper describes three approaches to assigning tasks to resources. A fast and simple priority dispatch method is described and shown to produce acceptable schedules most of the time. A look ahead algorithm is then introduced that outperforms the dispatcher by about 12% with only a small increase in run time. These algorithms set the stage for the introduction of a genetic algorithm that uses job permutations as the population. The genetic approach presented here is novel in that it uses two additional binary variables, one to allow the dispatcher to occasionally skip a job in the queue and another to allow the dispatcher to occasionally allocate the worst legal position to the job. These variables are included in the recombination step in a natural way. The resulting schedules improve on the look ahead by as much as 15% at times and 3% on average. We define the 'window- constrained packing' problem and use it for simulations.

Paper Details

Date Published: 9 December 1997
PDF: 10 pages
Proc. SPIE 3203, Architectures, Networks, and Intelligent Systems for Manufacturing Integration, (9 December 1997); doi: 10.1117/12.294436
Show Author Affiliations
William J. Wolfe, Univ. of Colorado/Denver (United States)
Stephen E. Sorensen, Hughes Information Technology Systems (United States)

Published in SPIE Proceedings Vol. 3203:
Architectures, Networks, and Intelligent Systems for Manufacturing Integration
Bhaskaran Gopalakrishnan; San Murugesan; Odo Struger; Gerfried Zeichen, Editor(s)

© SPIE. Terms of Use
Back to Top
Sign in to read the full article
Create a free SPIE account to get access to
premium articles and original research
Forgot your username?