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

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

School of Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

38 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 language	English
Title of host publication	Learning and Intelligent Optimization
Editors	T Stutzle
Place of Publication	Germany
Publisher	Springer-Verlag London Ltd.
Pages	89 - 103
Number of pages	15
ISBN (Print)	9783642111686
Publication status	Published - 2009
Event	International Conference on Learning and Intelligent OptimizatioN (LION) 2009 - Trento Italy, Trento, Italy Duration: 14 Jan 2009 → 18 Jan 2009 Conference number: 3rd http://www.intelligent-optimization.org/LION3/

Conference

Conference	International Conference on Learning and Intelligent OptimizatioN (LION) 2009
Abbreviated title	LION 3
Country/Territory	Italy
City	Trento
Period	14/01/09 → 18/01/09
Internet address	http://www.intelligent-optimization.org/LION3/

Cite this

@inproceedings{ec0382bf66554bb3ba5904bb10a78a80,

title = "A knowledge discovery approach to understanding relationships between scheduling problem structure and heuristic performance",

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.",

author = "Smith-Miles, {Kate Amanda} and James, {Ross J W} and Giffin, {John W} and Yiqing Tu",

year = "2009",

language = "English",

isbn = "9783642111686",

pages = "89 -- 103",

editor = "T Stutzle",

booktitle = "Learning and Intelligent Optimization",

publisher = "Springer-Verlag London Ltd.",

address = "Germany",

note = "International Conference on Learning and Intelligent OptimizatioN (LION) 2009, LION 3 ; Conference date: 14-01-2009 Through 18-01-2009",

url = "http://www.intelligent-optimization.org/LION3/",

}

Smith-Miles, KA, James, RJW, Giffin, JW & Tu, Y 2009, A knowledge discovery approach to understanding relationships between scheduling problem structure and heuristic performance. in T Stutzle (ed.), Learning and Intelligent Optimization. Springer-Verlag London Ltd., Germany, pp. 89 - 103, International Conference on Learning and Intelligent OptimizatioN (LION) 2009, Trento, Italy, 14/01/09.

A knowledge discovery approach to understanding relationships between scheduling problem structure and heuristic performance. / Smith-Miles, Kate Amanda; James, Ross J W; Giffin, John W et al.
Learning and Intelligent Optimization. ed. / T Stutzle. Germany: Springer-Verlag London Ltd., 2009. p. 89 - 103.

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

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

AU - Smith-Miles, Kate Amanda

AU - James, Ross J W

AU - Giffin, John W

AU - Tu, Yiqing

N1 - Conference code: 3rd

PY - 2009

Y1 - 2009

N2 - 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.

AB - 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.

UR - http://portal.acm.org/citation.cfm?id=1696564

M3 - Conference Paper

SN - 9783642111686

SP - 89

EP - 103

BT - Learning and Intelligent Optimization

A2 - Stutzle, T

PB - Springer-Verlag London Ltd.

CY - Germany

T2 - International Conference on Learning and Intelligent OptimizatioN (LION) 2009

Y2 - 14 January 2009 through 18 January 2009

ER -

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

Abstract

Conference

Other files and links

Cite this