The Robotics Institute

Carnegie Mellon Robotics Institute

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract

This paper describes a memory enhanced evolutionary algorithm (EA) approach to the dynamic job shop scheduling problem. Memory enhanced EAs have been widely investigated for other dynamic optimization problems with changing fitness landscapes, but only when associated with a fixed search space. In dynamic scheduling, the search space shifts as jobs are completed and new jobs arrive, so memory entries that describe specific points in the search space will become infeasible over time. The relative importances of jobs in the schedule also change over time, so previously good points become increasingly irrelevant. We describe a classifier-based memory for abstracting and storing information about schedules that can be used to build similar schedules at future times. We compared the memory enhanced EA with a standard EA and several common EA diversity techniques both with and without memory. The memory enhanced EA improved performance over the standard EA, while diversity techniques decreased performance.

Keywords

genetic algorithms, scheduling, dynamic optimization

Notes

Associated Center(s) / Consortia: Center for Integrated Manfacturing Decision Systems

Associated Lab(s) / Group(s): Intelligent Coordination and Logistics Laboratory

Number of pages: 10

Note: http://dx.doi.org/10.1007/978-3-540-78761-7_66

Text Reference

Gregory Barlow and Stephen Smith , "A Memory Enhanced Evolutionary Algorithm for Dynamic Scheduling Problems," Applications of Evolutionary Computing: EvoWorkshops 2008, April, 2008, pp. 606-615.

BibTeX Reference

@inproceedings{Barlow_2008_6025,
   author = "Gregory Barlow and Stephen {Smith }",
   editor = "Mario Giacobini et al.",
   title = "A Memory Enhanced Evolutionary Algorithm for Dynamic Scheduling Problems",
   booktitle = "Applications of Evolutionary Computing: EvoWorkshops 2008",
   pages = "606-615",
   publisher = "Springer",
   address = "Berlin / Heidelberg",
   month = "April",
   year = "2008",
   volume = "4974/2008",
   Notes = "http://dx.doi.org/10.1007/978-3-540-78761-7_66"
}

The Robotics Institute

Menu