A Survey of Search Methodologies and Automated System Development for Examination Timetabling

Exam timetabling is one of the most important administrative activities that takes place in academic institutions. In this paper we present a critical discussion of the research on exam timetabling in the last decade or so. This last ten years has seen an increased level of attention on this important topic. There has been a range of significant contributions to the scientific literature both in terms of theoretical andpractical aspects. The main aim of this survey is to highlight the new trends and key research achievements that have been carried out in the last decade.We also aim to outline a range of relevant important research issues and challenges that have been generated by this body of work.

We first define the problem and review previous survey papers. Algorithmic approaches are then classified and discussed. These include early techniques (e.g. graph heuristics) and state-of-the-art approaches including meta-heuristics, constraint based methods, multi-criteria techniques, hybridisations, and recent new trends concerning neighbourhood structures, which are motivated by raising the generality of the approaches. Summarising tables are presented to provide an overall view of these techniques. We discuss some issues on decomposition techniques, system tools and languages, models and complexity. We also present and discuss some important issues which have come to light concerning the public benchmark exam timetabling data. Different versions of problem datasetswith the same name have been circulating in the scientific community in the last ten years which has generated a significant amount of confusion. We clarify the situation and present a re-naming of the widely studied datasets to avoid future confusion. We also highlight which research papershave dealt with which dataset. Finally, we draw upon our discussion of the literature to present a (non-exhaustive) range of potential future research directions and open issues in exam timetabling research.

Adaptive automated construction of hybrid heuristics for exam timetabling and graph colouring problems

In this paper, we present a random iterative graph based hyper-heuristic to produce a collection of heuristic sequences to construct solutions of different quality. These heuristic sequences can be seen as dynamic hybridisations of different graph colouring heuristics that construct solutions step by step. Based on these sequences, we statistically analyse the way in which graph colouring heuristics are automatically hybridised. This, to our knowledge, represents a new direction in hyper-heuristic research. It is observed that spending the search effort on hybridising Largest Weighted Degree with Saturation Degree at the early stage of solution construction tends to generate high quality solutions. Based on these observations, an iterative hybrid approach is developed to adaptively hybridise these two graph colouring heuristics at different stages of solution construction. The overall aim here is to automate the heuristic design process, which draws upon an emerging research theme on developing computer methods to design and adapt heuristics automatically. Experimental results on benchmark exam timetabling and graph colouring problems demonstrate the effectiveness and generality of this adaptive hybrid approach compared with previous methods on automatically generating and adapting heuristics. Indeed, we also show that the approach is competitive with the state of the art human produced methods.

Geometric bonding effects in the X2A1, A2∑+u, and B2IIg states of Li2F

Published ab-initio and pseudopotential calculations for the dialkali halide systems suggest that the preferred co-linear geometry is for the metal to approach the metal end of the alkali halide. Here, ab-initio calculations on the Li2F system reveal that the well depth on the halide side in this radical is much deeper and is a local saddle-point associated with the ionic non-linear global minima. Although many features of the pseudopotential surfaces are confirmed, significant differences are apparent including the existence of a linear excited state instead of a triangular one, a considerably deeper global minimum some 50% lower in energy and a close approach between the X2A1 and the states, with the minimum 87 kJ mol-1 below the ground state asymptote. All the results can be rationalised as the avoided crossings between a long range, covalent potential dominant within the LiLiF geometry and an ionic state that forms the global minimum. Calculations on the 3rd 2A' potential indicate that even for Li + LiF collisions at ultracold temperatures the collision dynamics could involve as many as three electronic states.

Intracellular accumulation of polyphosphate by the yeast Candida humicola G-1 in response to acid pH

Cells of a newly isolated environmental strain of Candida humicola accumulated 10-fold more polyphosphate (polyP), during active growth, when grown in complete glucose-mineral salts medium at pH 5.5 than when grown at pH 7.5. Neither phosphate starvation, nutrient limitation, nor anaerobiosis was required to induce polyP formation. An increase in intracellular polyP was accompanied by a 4.5-fold increase in phosphate uptake from the medium and sixfold-higher levels of cellular polyphosphate kinase activity. This novel accumulation of polyP by C. humicola G-1 in response to acid pH provides further evidence as to the importance of polyP in the physiological adaptation of microbial cells during growth and development and in their response to environmental stresses.

Compact Toffoli gate using weighted graph states

We introduce three compact graph states that can be used to perform a measurement-based Toffoli gate. Given a weighted graph of six, seven, or eight qubits, we show that success probabilities of 1/4, 1/2, and 1, respectively, can be achieved. Our study puts a measurement-based version of this important quantum logic gate within the reach of current experiments. As the graphs are setup independent, they could be realized in a variety of systems, including linear optics and ion traps.