A New Model for Automated Examination Timetabling

Automated examination timetabling has been addressed by a wide variety of methodologies and techniques over the last ten years or so. Many of the methods in this broad range of approaches have been evaluated on a collection of benchmark instances provided at the University of Toronto in 1996. Whilst the existence of these datasets has provided an invaluable resource for research into examination timetabling, the instances have significant limitations in terms of their relevance to real-world examination timetabling in modern universities. This paper presents a detailed model which draws upon experiences of implementing examination timetabling systems in universities in Europe, Australasia and America. This model represents the problem that was presented in the 2nd International Timetabling Competition (ITC2007). In presenting this detailed new model, this paper describes the examination timetabling track introduced as part of the competition. In addition to the model, the datasets used in the competition are also based on current real-world instances introduced by EventMAP Limited. It is hoped that the interest generated as part of the competition will lead to the development, investigation and application of a host of novel and exciting techniques to address this important real-world search domain. Moreover, the motivating goal of this paper is to close the currently existing gap between theory and practice in examination timetabling by presenting the research community with a rigorous model which represents the complexity of the real-world situation. In this paper we describe the model and its motivations, followed by a full formal definition.

Adaptive linear combination of heuristic orderings in constructing examination timetables

In this paper, we investigate adaptive linear combinations of graph coloring heuristics with a heuristic modifier to address the examination timetabling problem. We invoke a normalisation strategy for each parameter in order to generalise the specific problem data. Two graph coloring heuristics were used in this study (largest degree and saturation degree). A score for the difficulty of assigning each examination was obtained from an adaptive linear combination of these two heuristics and examinations in the list were ordered based on this value. The examinations with the score value representing the higher difficulty were chosen for scheduling based on two strategies. We tested for single and multiple heuristics with and without a heuristic modifier with different combinations of weight values for each parameter on the Toronto and ITC2007 benchmark data sets. We observed that the combination of multiple heuristics with a heuristic modifier offers an effective way to obtain good solution quality. Experimental results demonstrate that our approach delivers promising results. We conclude that this adaptive linear combination of heuristics is a highly effective method and simple to implement.

A constructive approach for examination timetabling based on adaptive decomposition and ordering

In this study, we investigate an adaptive decomposition and ordering strategy that automatically divides examinations into difficult and easy sets for constructing an examination timetable. The examinations in the difficult set are considered to be hard to place and hence are listed before the ones in the easy set in the construction process. Moreover, the examinations within each set are ordered using different strategies based on graph colouring heuristics. Initially, the examinations are placed into the easy set. During the construction process, examinations that cannot be scheduled are identified as the ones causing infeasibility and are moved forward in the difficult set to ensure earlier assignment in subsequent attempts. On the other hand, the examinations that can be scheduled remain in the easy set.

Within the easy set, a new subset called the boundary set is introduced to accommodate shuffling strategies to change the given ordering of examinations. The proposed approach, which incorporates different ordering and shuffling strategies, is explored on the Carter benchmark problems. The empirical results show that the performance of our algorithm is broadly comparable to existing constructive approaches.

Documents relative to the colonial history of the state of New-York : procured in Holland, England, and France /

Includes index.

The register of New Netherland, 1626 to 1674 /

Includes index.

A review of the conduct of the Prince of Wales in his various transactions with Mr. Jefferys, during a period of more than twenty years ; containing a detail of many circumstances relative to the Prince and Princess of Wales, Mrs. Fitzherbert, &c.&c.&c. /

Shaw and Shoemaker ;

Relation des îles Pelew, situées dans la partie occidentale de l'ocean Pacifique : composée sur les journaux et les communications du Capitaine Henri Wilson, et de quelques-uns de ses Officiers, qui, en août mil sept cent quatre-vingt-trois, y ont fait naufrage sur l'antelope, paquebot de la Compagnie des Indes orientales /

La obra completa consta de dos volúmenes.

Relation des îles Pelew, situées dans la partie occidentale de l'ocean Pacifique : composée sur les journaux et les communications du Capitaine Henri Wilson, et de quelques-uns de ses Officiers, qui, en août mil sept cent quatre-vingt-trois, y ont fait naufrage sur l'Antelope, paquebot de la Compagnie des Indes orientales /

Mode of access: Internet.

An account of the Pelew Islands, situated in the western part of the Pacific Ocean : composed from the journals and communications of Captain Henry Wilson and some of his officers who, in August 1783, were there shipwrecked, in the Antelope ... /

A vocabulary of the pelew language: p. 365-378.

Catalogue of historical papers and parchments received from the Office of the Secretary of State, and deposited in the New York State Library /

Catalogue by E.B. O'Callaghan

Ferney: an epistle to Monsr. de Voltaire.

In verse.

Relación de las islas de Pelew situadas en la parte occidental del Océano Pacífico : deducida de los diarios y noticias verbales del capitán Enrique Wilson ... /

Mode of access: Internet.

The documentary history of the State of New-York /

Vol. 4 has imprint: Albany : C. Van Benthuysen, public printer.

Specimen inaugurale sistens medicamenta graveolentia /

Also published in Linné's Amoenitates academicae, v. 5, ed. 1, 1760; ed. 2, 1788, p. 148-173: Gilibert's Systema plantarum Europæ, v. 6, 1786, p. 181-205.