Resource based scheduling using permutation based representations is reviewed. Permutation based representations are used in conjunction with genetic algorithms and local search algorithms for solving three very different scheduling problems. First, the Coors warehouse scheduling problem involves finding a permutation of customer orders that minimizes the average time that customers' orders spend at the loading docks while at the same time minimizing the running average inventory. Second, scheduling the Air Force Satellite Control Network (AFSCN) involves scheduling customer requests for contact time with a satellite via a ground station, where slot times on a ground station is the limited resource. The third application is scheduling the tracking of objects in space using ground based radar systems. Both satellites and debris in space must be tracked on regular basis to maintain knowledge about the location and orbit of the object. The ground based radar system is the limited resource, but unlike AFSCN scheduling, this application involves significant uncertainty.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
L. Barbulescu, A.E. Howe, L.D. Whitley, and M. Roberts (2006) Understanding algorithm performance on an oversubscribed scheduling application. Journal of Artificial Intelligence Research (JAIR).
L. Barbulescu, J.P. Watson, D. Whitley, and A. Howe (2004) Scheduling Space-Ground Communications for the Air Force Satellite Control Network. Journal of Scheduling.
John Bresina, Mark Drummond, and Keith Swanson (1995) Expected solution quality. In Proceedings of the 14th International Joint Conference on Artificial Intelligence.
T. Cormen, C. Leiserson, and R. Rivest (1990) Introduction to Algorithms. McGraw Hill, New York.
Lawrence Davis (1985) Applying Adaptive Algorithms to Epistatic Domains. In Proc. IJCAI-85.
Lawrence Davis (1985) Job Shop Scheduling with Genetic Algorithms. In John Grefenstette, editor, Int’l. Conf. on GAs and Their Applications, pages 136–140.
Lawrence Davis (1991) Handbook of Genetic Algorithms. Van Nostrand Reinhold, New York.
M. R. Garey and David S. Johnson (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman.
David Goldberg (1989) Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, Reading, MA.
David Goldberg and Jr. Robert Lingle (1985) Alleles, Loci, and the Traveling Salesman Problem. In John Grefenstette, editor, Int’l. Conf. on GAs and Their Applications, pages 154–159.
D.E. Goldberg and M. Rudnick (1991) Genetic algorithms and the variance of fitness. Complex Systems, 5(3):265–278.
Felix R. Hoots and Ronald L. Roehrich (1980) Spacetrack report no. 3: Models for propagation of NORAD element sets. Technical report, Peterson Air Force Base.
Yuichi Nagata and Shigenobu Kobayashi (1997) Edge assembly crossover: A high-power genetic algorithm for the traveling salesman problem. In T. Bäck, editor, Proc. of the 7th Int’l. Conf. on GAs, pages 450–457. Morgan Kaufmann.
D.A. Parish (1994) A Genetic Algorithm Approach to Automating Satellite Range Scheduling. In Masters Thesis. Air Force Institute of Technology.
T. Starkweather, S. McDaniel, K. Mathias, D. Whitley, and C. Whitley (1991) A Comparison of Genetic Sequencing Operators. In L. Booker and R. Belew, editors, Proc. of the 4th Int’l. Conf. on GAs, pages 69–76. Morgan Kaufmann.
A. Sutton, A.E. Howe, and L.D. Whitley (2007) Using adaptive priority weighting to direct search in probabilistic scheduling. In The International Conference on Automated Planning and Scheduling.
A.M. Sutton (2006) A two-phase dynamic local search algorithm for maximizing expected success in on-line orbit track scheduling. MS thesis, Colorado State University, Fort Collins, CO.
Gilbert Syswerda (1991) Schedule Optimization Using Genetic Algorithms. In Lawrence Davis, editor, Handbook of Genetic Algorithms, chapter 21. Van Nostrand Reinhold, New York.
Gilbert Syswerda and Jeff Palmucci (1991) The Application of Genetic Algorithms to Resource Scheduling. In L. Booker and R. Belew, editors, Proc. of the 4th Int’l. Conf. on GAs. Morgan Kaufmann.
J.P. Watson, S. Rana, D. Whitley, and A. Howe (1999) The Impact of Approximate Evaluation on the Performance of Search Algorithms for Warehouse Scheduling. Journal on Scheduling, 2(2):79–98.
Darrell Whitley, Timothy Starkweather, and D’ann Fuquay (1989) Scheduling Problems and Traveling Salesmen: The Genetic Edge Recombination Operator. In J.D. Schaffer, editor, Proc. of the 3rd Int’l. Conf. on GAs. Morgan Kaufmann.
Darrell Whitley and Nam-Wook Yoo (1995) Modeling Permutation Encodings in Simple Genetic Algorithm. In D. Whitley and M. Vose, editors, FOGA - 3. Morgan Kaufmann.
L. Darrell Whitley (1989) The GENITOR Algorithm and Selective Pressure: Why Rank Based Allocation of Reproductive Trials is Best. In J.D. Schaffer, editor, Proc. of the 3rd Int’l. Conf. on GAs, pages 116–121. Morgan Kaufmann.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Whitley, D., Sutton, A., Howe, A., Barbulescu, L. (2008). Resource Scheduling with Permutation Based Representations: Three Applications. In: Yu, T., Davis, L., Baydar, C., Roy, R. (eds) Evolutionary Computation in Practice. Studies in Computational Intelligence, vol 88. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-75771-9_10
Download citation
DOI: https://doi.org/10.1007/978-3-540-75771-9_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-75770-2
Online ISBN: 978-3-540-75771-9
eBook Packages: EngineeringEngineering (R0)