Comparison of three scheduling algorithms

William J. Wolfe; Stephen E. Sorensen

doi:10.1117/12.294436

9 December 1997 Comparison of three scheduling algorithms

William J. Wolfe, Stephen E. Sorensen

Proceedings Volume 3203, Architectures, Networks, and Intelligent Systems for Manufacturing Integration; (1997) https://doi.org/10.1117/12.294436
Event: Intelligent Systems and Advanced Manufacturing, 1997, Pittsburgh, PA, United States

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.

Citation Download Citation

William J. Wolfe and Stephen E. Sorensen "Comparison of three scheduling algorithms", Proc. SPIE 3203, Architectures, Networks, and Intelligent Systems for Manufacturing Integration, (9 December 1997); https://doi.org/10.1117/12.294436

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available