A knowledge discovery approach to understanding relationships between scheduling problem structure and heuristic performance

Kate Amanda Smith-Miles, Ross J W James, John W Giffin, Yiqing Tu

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

36 Citations (Scopus)

Abstract

Using a knowledge discovery approach, we seek insights into the relationships between problem structure and the effectiveness of scheduling heuristics. A large collection of 75,000 instances of the single machine early/tardy scheduling problem is generated, characterized by six features, and used to explore the performance of two common scheduling heuristics. The best heuristic is selected using rules from a decision tree with accuracy exceeding 97 . A self-organizing map is used to visualize the feature space and generate insights into heuristic performance. This paper argues for such a knowledge discovery approach to be applied to other optimization problems, to contribute to automation of algorithm selection as well as insightful algorithm design.
Original languageEnglish
Title of host publicationLearning and Intelligent Optimization
EditorsT Stutzle
Place of PublicationGermany
PublisherSpringer-Verlag London Ltd.
Pages89 - 103
Number of pages15
ISBN (Print)9783642111686
Publication statusPublished - 2009
EventInternational Conference on Learning and Intelligent OptimizatioN (LION) 2009 - Trento Italy, Trento, Italy
Duration: 14 Jan 200918 Jan 2009
Conference number: 3rd
http://www.intelligent-optimization.org/LION3/

Conference

ConferenceInternational Conference on Learning and Intelligent OptimizatioN (LION) 2009
Abbreviated titleLION 3
Country/TerritoryItaly
CityTrento
Period14/01/0918/01/09
Internet address

Cite this