Home > Research > Publications & Outputs > A Hidden Markov Model Approach to the Problem o...

Electronic data

  • EVCO2016

    Accepted author manuscript, 336 KB, PDF document

    Available under license: CC BY

Links

Text available via DOI:

View graph of relations

A Hidden Markov Model Approach to the Problem of Heuristic Selection in Hyper-Heuristics with a Case Study in High School Timetabling Problems

Research output: Contribution to journalJournal article

Published

Standard

A Hidden Markov Model Approach to the Problem of Heuristic Selection in Hyper-Heuristics with a Case Study in High School Timetabling Problems. / Kheiri, Ahmed; Keedwell, Ed.

In: Evolutionary Computation, Vol. 25, No. 3, 09.2017, p. 473-501.

Research output: Contribution to journalJournal article

Harvard

APA

Vancouver

Author

Bibtex

@article{ea59d1ddca364e7b9a51a2bebad455a5,
title = "A Hidden Markov Model Approach to the Problem of Heuristic Selection in Hyper-Heuristics with a Case Study in High School Timetabling Problems",
abstract = "Operations research is a well-established field that uses computational systems to support decisions in business and public life. Good solutions to operations research problems can make a large difference to the efficient running of businesses and organisations and so the field often searches for new methods to improve these solutions. The high school timetabling problem is an example of an operations research problem and is a challenging task which requires assigning events and resources to time slots subject to a set of constraints. In this article, a new sequence-based selection hyper-heuristic is presented that produces excellent results on a suite of high school timetabling problems. In this study, we present an easy-to-implement, easy-to-maintain, and effective sequence-based selection hyper-heuristic to solve high school timetabling problems using a benchmark of unified real-world instances collected from different countries. We show that with sequence-based methods, it is possible to discover new best known solutions for a number of the problems in the timetabling domain. Through this investigation, the usefulness of sequence-based selection hyper-heuristics has been demonstrated and the capability of these methods has been shown to exceed the state of the art.",
keywords = "combinatorial optimisation, computational design, educational timetabling, hidden Markov model, Hyper-heuristic",
author = "Ahmed Kheiri and Ed Keedwell",
year = "2017",
month = sep
doi = "10.1162/EVCO_a_00186",
language = "English",
volume = "25",
pages = "473--501",
journal = "Evolutionary Computation",
issn = "1530-9304",
publisher = "Massachusetts Institute of Technology",
number = "3",

}

RIS

TY - JOUR

T1 - A Hidden Markov Model Approach to the Problem of Heuristic Selection in Hyper-Heuristics with a Case Study in High School Timetabling Problems

AU - Kheiri, Ahmed

AU - Keedwell, Ed

PY - 2017/9

Y1 - 2017/9

N2 - Operations research is a well-established field that uses computational systems to support decisions in business and public life. Good solutions to operations research problems can make a large difference to the efficient running of businesses and organisations and so the field often searches for new methods to improve these solutions. The high school timetabling problem is an example of an operations research problem and is a challenging task which requires assigning events and resources to time slots subject to a set of constraints. In this article, a new sequence-based selection hyper-heuristic is presented that produces excellent results on a suite of high school timetabling problems. In this study, we present an easy-to-implement, easy-to-maintain, and effective sequence-based selection hyper-heuristic to solve high school timetabling problems using a benchmark of unified real-world instances collected from different countries. We show that with sequence-based methods, it is possible to discover new best known solutions for a number of the problems in the timetabling domain. Through this investigation, the usefulness of sequence-based selection hyper-heuristics has been demonstrated and the capability of these methods has been shown to exceed the state of the art.

AB - Operations research is a well-established field that uses computational systems to support decisions in business and public life. Good solutions to operations research problems can make a large difference to the efficient running of businesses and organisations and so the field often searches for new methods to improve these solutions. The high school timetabling problem is an example of an operations research problem and is a challenging task which requires assigning events and resources to time slots subject to a set of constraints. In this article, a new sequence-based selection hyper-heuristic is presented that produces excellent results on a suite of high school timetabling problems. In this study, we present an easy-to-implement, easy-to-maintain, and effective sequence-based selection hyper-heuristic to solve high school timetabling problems using a benchmark of unified real-world instances collected from different countries. We show that with sequence-based methods, it is possible to discover new best known solutions for a number of the problems in the timetabling domain. Through this investigation, the usefulness of sequence-based selection hyper-heuristics has been demonstrated and the capability of these methods has been shown to exceed the state of the art.

KW - combinatorial optimisation

KW - computational design

KW - educational timetabling

KW - hidden Markov model

KW - Hyper-heuristic

U2 - 10.1162/EVCO_a_00186

DO - 10.1162/EVCO_a_00186

M3 - Journal article

C2 - 27258841

AN - SCOPUS:85033406624

VL - 25

SP - 473

EP - 501

JO - Evolutionary Computation

JF - Evolutionary Computation

SN - 1530-9304

IS - 3

ER -