Loading…

A robust simulated annealing based examination timetabling system

This paper is concerned with the development of an examination scheduling system that is sufficiently flexible to deal with the many different objectives and constraints found across a broad spectrum of universities and colleges. The problem is solved in two phases using simulated annealing. The fir...

Full description

Saved in:
Bibliographic Details
Published in:Computers & operations research 1998-07, Vol.25 (7-8), p.637-648
Main Authors: Thompson, Jonathan M., Dowsland, Kathryn A.
Format: Article
Language:English
Subjects:
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c363t-9c2fdb9d83512faf0d0f932c5abbcadfaa57e26da511d7973220317699c29e033
cites cdi_FETCH-LOGICAL-c363t-9c2fdb9d83512faf0d0f932c5abbcadfaa57e26da511d7973220317699c29e033
container_end_page 648
container_issue 7-8
container_start_page 637
container_title Computers & operations research
container_volume 25
creator Thompson, Jonathan M.
Dowsland, Kathryn A.
description This paper is concerned with the development of an examination scheduling system that is sufficiently flexible to deal with the many different objectives and constraints found across a broad spectrum of universities and colleges. The problem is solved in two phases using simulated annealing. The first phase seeks out a feasible solution and the second finds an improvement in terms of meeting the secondary objectives and soft constraints. As the quality of a simulated annealing solution is known to depend on the parameters used to control the algorithm and the way in which the problem is modelled within the simulated annealing framework a successful implemetation relies on judicious choices in both areas. A number of different choices are suggested and compared using a test-bed of problems derived from data from a variety of institutions. The final result is a robust system that is capable of dealing with a wide range of problem specifications and data characteristics. The examination scheduling problem varies in detail from institution to institution. Thus any generic approach must be robust enough to work well over the full spectrum of problem characteristics. It is well-known that the quality of solutions produced by any simulated annealing implementation depends on the correct choice of solution space and neighbourhood, as well as the parameters that govern the cooling schedule. As these choices are sensitive to the precise problem details the design of a generic simulated annealing based approach to examination scheduling needs to address this issue carefully. This paper examines this problem with respect to an implementation that has already been shown to work well at a single institution. The basic framework is used to test different neighbourhoods and cooling schedules over a variety of problems and to examine whether or not biases in sampling have a significant effect on solution quality. The results indicate that the choice of neighbourhood is the most important decision and that neighbourhoods based on the graph-theoretic concept of Kempe chains are the most effective regardless of the objectives or size of the problem.
doi_str_mv 10.1016/S0305-0548(97)00101-9
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_195826094</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><els_id>S0305054897001019</els_id><sourcerecordid>40356765</sourcerecordid><originalsourceid>FETCH-LOGICAL-c363t-9c2fdb9d83512faf0d0f932c5abbcadfaa57e26da511d7973220317699c29e033</originalsourceid><addsrcrecordid>eNqFkE1LAzEQhoMoWKs_QVjEgx5W89Ekm5OU4hcUPKjgLcwmWUnp7tYkK_bfm7aiR-cyzMzzzjAvQqcEXxFMxPUzZpiXmE-qCyUvMc7NUu2hEakkK6Xgb_to9IscoqMYFziHpGSEptMi9PUQUxF9OywhOVtA1zlY-u69qCHm2n1B6ztIvu-K5FuXoN5O4zom1x6jgwaW0Z385DF6vbt9mT2U86f7x9l0XhomWCqVoY2tla0YJ7SBBlvcKEYNh7o2YBsALh0VFjghVirJKMWMSKGyUDnM2Bid7fauQv8xuJj0oh9Cl09qonhFBVaTDPEdZEIfY3CNXgXfQlhrgvXGLL01S2-c0ErqrVlaZd35z3KIBpZNgM74-CcWTChcZexmh7n86Kd3QUfjXWec9cGZpG3v_zn0DavJffE</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>195826094</pqid></control><display><type>article</type><title>A robust simulated annealing based examination timetabling system</title><source>ScienceDirect Freedom Collection</source><creator>Thompson, Jonathan M. ; Dowsland, Kathryn A.</creator><creatorcontrib>Thompson, Jonathan M. ; Dowsland, Kathryn A.</creatorcontrib><description>This paper is concerned with the development of an examination scheduling system that is sufficiently flexible to deal with the many different objectives and constraints found across a broad spectrum of universities and colleges. The problem is solved in two phases using simulated annealing. The first phase seeks out a feasible solution and the second finds an improvement in terms of meeting the secondary objectives and soft constraints. As the quality of a simulated annealing solution is known to depend on the parameters used to control the algorithm and the way in which the problem is modelled within the simulated annealing framework a successful implemetation relies on judicious choices in both areas. A number of different choices are suggested and compared using a test-bed of problems derived from data from a variety of institutions. The final result is a robust system that is capable of dealing with a wide range of problem specifications and data characteristics. The examination scheduling problem varies in detail from institution to institution. Thus any generic approach must be robust enough to work well over the full spectrum of problem characteristics. It is well-known that the quality of solutions produced by any simulated annealing implementation depends on the correct choice of solution space and neighbourhood, as well as the parameters that govern the cooling schedule. As these choices are sensitive to the precise problem details the design of a generic simulated annealing based approach to examination scheduling needs to address this issue carefully. This paper examines this problem with respect to an implementation that has already been shown to work well at a single institution. The basic framework is used to test different neighbourhoods and cooling schedules over a variety of problems and to examine whether or not biases in sampling have a significant effect on solution quality. The results indicate that the choice of neighbourhood is the most important decision and that neighbourhoods based on the graph-theoretic concept of Kempe chains are the most effective regardless of the objectives or size of the problem.</description><identifier>ISSN: 0305-0548</identifier><identifier>EISSN: 1873-765X</identifier><identifier>EISSN: 0305-0548</identifier><identifier>DOI: 10.1016/S0305-0548(97)00101-9</identifier><identifier>CODEN: CMORAP</identifier><language>eng</language><publisher>Oxford: Elsevier Ltd</publisher><subject>Applied sciences ; Colleges &amp; universities ; Exact sciences and technology ; Operational research and scientific management ; Operational research. Management science ; Scheduling ; Scheduling, sequencing ; Studies ; Tests</subject><ispartof>Computers &amp; operations research, 1998-07, Vol.25 (7-8), p.637-648</ispartof><rights>1998 Elsevier Science Ltd</rights><rights>1999 INIST-CNRS</rights><rights>Copyright Pergamon Press Inc. Jul/Aug 1998</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c363t-9c2fdb9d83512faf0d0f932c5abbcadfaa57e26da511d7973220317699c29e033</citedby><cites>FETCH-LOGICAL-c363t-9c2fdb9d83512faf0d0f932c5abbcadfaa57e26da511d7973220317699c29e033</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,776,780,27901,27902</link.rule.ids><backlink>$$Uhttp://pascal-francis.inist.fr/vibad/index.php?action=getRecordDetail&amp;idt=1636908$$DView record in Pascal Francis$$Hfree_for_read</backlink></links><search><creatorcontrib>Thompson, Jonathan M.</creatorcontrib><creatorcontrib>Dowsland, Kathryn A.</creatorcontrib><title>A robust simulated annealing based examination timetabling system</title><title>Computers &amp; operations research</title><description>This paper is concerned with the development of an examination scheduling system that is sufficiently flexible to deal with the many different objectives and constraints found across a broad spectrum of universities and colleges. The problem is solved in two phases using simulated annealing. The first phase seeks out a feasible solution and the second finds an improvement in terms of meeting the secondary objectives and soft constraints. As the quality of a simulated annealing solution is known to depend on the parameters used to control the algorithm and the way in which the problem is modelled within the simulated annealing framework a successful implemetation relies on judicious choices in both areas. A number of different choices are suggested and compared using a test-bed of problems derived from data from a variety of institutions. The final result is a robust system that is capable of dealing with a wide range of problem specifications and data characteristics. The examination scheduling problem varies in detail from institution to institution. Thus any generic approach must be robust enough to work well over the full spectrum of problem characteristics. It is well-known that the quality of solutions produced by any simulated annealing implementation depends on the correct choice of solution space and neighbourhood, as well as the parameters that govern the cooling schedule. As these choices are sensitive to the precise problem details the design of a generic simulated annealing based approach to examination scheduling needs to address this issue carefully. This paper examines this problem with respect to an implementation that has already been shown to work well at a single institution. The basic framework is used to test different neighbourhoods and cooling schedules over a variety of problems and to examine whether or not biases in sampling have a significant effect on solution quality. The results indicate that the choice of neighbourhood is the most important decision and that neighbourhoods based on the graph-theoretic concept of Kempe chains are the most effective regardless of the objectives or size of the problem.</description><subject>Applied sciences</subject><subject>Colleges &amp; universities</subject><subject>Exact sciences and technology</subject><subject>Operational research and scientific management</subject><subject>Operational research. Management science</subject><subject>Scheduling</subject><subject>Scheduling, sequencing</subject><subject>Studies</subject><subject>Tests</subject><issn>0305-0548</issn><issn>1873-765X</issn><issn>0305-0548</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>1998</creationdate><recordtype>article</recordtype><recordid>eNqFkE1LAzEQhoMoWKs_QVjEgx5W89Ekm5OU4hcUPKjgLcwmWUnp7tYkK_bfm7aiR-cyzMzzzjAvQqcEXxFMxPUzZpiXmE-qCyUvMc7NUu2hEakkK6Xgb_to9IscoqMYFziHpGSEptMi9PUQUxF9OywhOVtA1zlY-u69qCHm2n1B6ztIvu-K5FuXoN5O4zom1x6jgwaW0Z385DF6vbt9mT2U86f7x9l0XhomWCqVoY2tla0YJ7SBBlvcKEYNh7o2YBsALh0VFjghVirJKMWMSKGyUDnM2Bid7fauQv8xuJj0oh9Cl09qonhFBVaTDPEdZEIfY3CNXgXfQlhrgvXGLL01S2-c0ErqrVlaZd35z3KIBpZNgM74-CcWTChcZexmh7n86Kd3QUfjXWec9cGZpG3v_zn0DavJffE</recordid><startdate>19980701</startdate><enddate>19980701</enddate><creator>Thompson, Jonathan M.</creator><creator>Dowsland, Kathryn A.</creator><general>Elsevier Ltd</general><general>Elsevier Science</general><general>Pergamon Press Inc</general><scope>IQODW</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>8FD</scope><scope>JQ2</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope></search><sort><creationdate>19980701</creationdate><title>A robust simulated annealing based examination timetabling system</title><author>Thompson, Jonathan M. ; Dowsland, Kathryn A.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c363t-9c2fdb9d83512faf0d0f932c5abbcadfaa57e26da511d7973220317699c29e033</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>1998</creationdate><topic>Applied sciences</topic><topic>Colleges &amp; universities</topic><topic>Exact sciences and technology</topic><topic>Operational research and scientific management</topic><topic>Operational research. Management science</topic><topic>Scheduling</topic><topic>Scheduling, sequencing</topic><topic>Studies</topic><topic>Tests</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Thompson, Jonathan M.</creatorcontrib><creatorcontrib>Dowsland, Kathryn A.</creatorcontrib><collection>Pascal-Francis</collection><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Technology Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts – Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><jtitle>Computers &amp; operations research</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Thompson, Jonathan M.</au><au>Dowsland, Kathryn A.</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>A robust simulated annealing based examination timetabling system</atitle><jtitle>Computers &amp; operations research</jtitle><date>1998-07-01</date><risdate>1998</risdate><volume>25</volume><issue>7-8</issue><spage>637</spage><epage>648</epage><pages>637-648</pages><issn>0305-0548</issn><eissn>1873-765X</eissn><eissn>0305-0548</eissn><coden>CMORAP</coden><abstract>This paper is concerned with the development of an examination scheduling system that is sufficiently flexible to deal with the many different objectives and constraints found across a broad spectrum of universities and colleges. The problem is solved in two phases using simulated annealing. The first phase seeks out a feasible solution and the second finds an improvement in terms of meeting the secondary objectives and soft constraints. As the quality of a simulated annealing solution is known to depend on the parameters used to control the algorithm and the way in which the problem is modelled within the simulated annealing framework a successful implemetation relies on judicious choices in both areas. A number of different choices are suggested and compared using a test-bed of problems derived from data from a variety of institutions. The final result is a robust system that is capable of dealing with a wide range of problem specifications and data characteristics. The examination scheduling problem varies in detail from institution to institution. Thus any generic approach must be robust enough to work well over the full spectrum of problem characteristics. It is well-known that the quality of solutions produced by any simulated annealing implementation depends on the correct choice of solution space and neighbourhood, as well as the parameters that govern the cooling schedule. As these choices are sensitive to the precise problem details the design of a generic simulated annealing based approach to examination scheduling needs to address this issue carefully. This paper examines this problem with respect to an implementation that has already been shown to work well at a single institution. The basic framework is used to test different neighbourhoods and cooling schedules over a variety of problems and to examine whether or not biases in sampling have a significant effect on solution quality. The results indicate that the choice of neighbourhood is the most important decision and that neighbourhoods based on the graph-theoretic concept of Kempe chains are the most effective regardless of the objectives or size of the problem.</abstract><cop>Oxford</cop><pub>Elsevier Ltd</pub><doi>10.1016/S0305-0548(97)00101-9</doi><tpages>12</tpages></addata></record>
fulltext fulltext
identifier ISSN: 0305-0548
ispartof Computers & operations research, 1998-07, Vol.25 (7-8), p.637-648
issn 0305-0548
1873-765X
0305-0548
language eng
recordid cdi_proquest_journals_195826094
source ScienceDirect Freedom Collection
subjects Applied sciences
Colleges & universities
Exact sciences and technology
Operational research and scientific management
Operational research. Management science
Scheduling
Scheduling, sequencing
Studies
Tests
title A robust simulated annealing based examination timetabling system
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-31T07%3A46%3A46IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=A%20robust%20simulated%20annealing%20based%20examination%20timetabling%20system&rft.jtitle=Computers%20&%20operations%20research&rft.au=Thompson,%20Jonathan%20M.&rft.date=1998-07-01&rft.volume=25&rft.issue=7-8&rft.spage=637&rft.epage=648&rft.pages=637-648&rft.issn=0305-0548&rft.eissn=1873-765X&rft.coden=CMORAP&rft_id=info:doi/10.1016/S0305-0548(97)00101-9&rft_dat=%3Cproquest_cross%3E40356765%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c363t-9c2fdb9d83512faf0d0f932c5abbcadfaa57e26da511d7973220317699c29e033%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=195826094&rft_id=info:pmid/&rfr_iscdi=true