A graph-based hyper heuristic for timetabling problems

This paper presents an investigation of a simple generic hyper-heuristic approach upon a set of widely used constructive heuristics (graph coloring heuristics) in timetabling. Within the hyperheuristic framework, a Tabu Search approach is employed to search for permutations of graph heuristics which are used for constructing timetables in exam and course timetabling problems. This underpins a multi-stage hyper-heuristic where the Tabu Search employs permutations upon a different number of graph heuristics in two stages. We study this graph-based hyper-heuristic approach within the context of exploring fundamental issues concerning the search space of the hyper-heuristic (the heuristic space) and the solution space. Such issues have not been addressed in other hyper-heuristic research. These approaches are tested on both exam and course benchmark timetabling problems and are compared with the fine-tuned bespoke state-of-the-art approaches. The results are within the range of the best results reported in the literature. The approach described here represents a significantly more generally applicable approach than the current state of the art in the literature. Future work will extend this hyper-heuristic framework by employing methodologies which are applicable on a wider range of timetabling and scheduling problems.

Hybrid Graph Heuristics within a Hyper-heuristic Approach to Exam Timetabling Problems

This paper is concerned with the hybridization of two graph coloring heuristics (Saturation Degree and Largest Degree), and their application within a hyperheuristic for exam timetabling problems. Hyper-heuristics can be seen as algorithms which intelligently select appropriate algorithms/heuristics for solving a problem. We developed a Tabu Search based hyper-heuristic to search for heuristic lists (of graph heuristics) for solving problems and investigated the heuristic lists found by employing knowledge discovery techniques. Two hybrid approaches (involving Saturation Degree and Largest Degree) including one which employs Case Based Reasoning are presented and discussed. Both the Tabu Search based hyper-heuristic and the hybrid approaches are tested on random and real-world exam timetabling problems. Experimental results are comparable with the best state-of-the-art approaches (as measured against established benchmark problems). The results also demonstrate an increased level of generality in our approach.

Case-Based Reasoning as a Heuristic Selector in a Hyper-Heuristic for Course Timetabling Problems

This paper studies Knowledge Discovery (KD) using Tabu Search and Hill Climbing within Case-Based Reasoning (CBR) as a hyper-heuristic method for course timetabling problems. The aim of the hyper-heuristic is to choose the best heuristic(s) for given timetabling problems according to the knowledge stored in the case base. KD in CBR is a 2-stage iterative process on both case representation and the case base. Experimental results are analysed and related research issues for future work are discussed.

Knowledge discovery in hyper-heuristic using case-based reasoning on course timetabling

This paper presents a new hyper-heuristic method using Case-Based Reasoning (CBR) for solving course timetabling problems. The term Hyper-heuristics has recently been employed to refer to 'heuristics that choose heuristics' rather than heuristics that operate directly on given problems. One of the overriding motivations of hyper-heuristic methods is the attempt to develop techniques that can operate with greater generality than is currently possible. The basic idea behind this is that we maintain a case base of information about the most successful heuristics for a range of previous timetabling problems to predict the best heuristic for the new problem in hand using the previous knowledge. Knowledge discovery techniques are used to carry out the training on the CBR system to improve the system performance on the prediction. Initial results presented in this paper are good and we conclude by discussing the con-siderable promise for future work in this area.

A graph-based hyper heuristic for timetabling problems

This paper presents an investigation of a simple generic hyper-heuristic approach upon a set of widely used constructive heuristics (graph coloring heuristics) in timetabling. Within the hyperheuristic framework, a Tabu Search approach is employed to search for permutations of graph heuristics which are used for constructing timetables in exam and course timetabling problems. This underpins a multi-stage hyper-heuristic where the Tabu Search employs permutations upon a different number of graph heuristics in two stages. We study this graph-based hyper-heuristic approach within the context of exploring fundamental issues concerning the search space of the hyper-heuristic (the heuristic space) and the solution space. Such issues have not been addressed in other hyper-heuristic research. These approaches are tested on both exam and course benchmark timetabling problems and are compared with the fine-tuned bespoke state-of-the-art approaches. The results are within the range of the best results reported in the literature. The approach described here represents a significantly more generally applicable approach than the current state of the art in the literature. Future work will extend this hyper-heuristic framework by employing methodologies which are applicable on a wider range of timetabling and scheduling problems.

Clustering through post inhibitory rebound in synaptically coupled neurons

Post inhibitory rebound is a nonlinear phenomenon present in a variety of nerve cells. Following a period of hyper-polarization this effect allows a neuron to fire a spike or packet of spikes before returning to rest. It is an important mechanism underlying central pattern generation for heartbeat, swimming and other motor patterns in many neuronal systems. In this paper we consider how networks of neurons, which do not intrinsically oscillate, may make use of inhibitory synaptic connections to generate large scale coherent rhythms in the form of cluster states. We distinguish between two cases i) where the rebound mechanism is due to anode break excitation and ii) where rebound is due to a slow T-type calcium current. In the former case we use a geometric analysis of a McKean type model to obtain expressions for the number of clusters in terms of the speed and strength of synaptic coupling. Results are found to be in good qualitative agreement with numerical simulations of the more detailed Hodgkin-Huxley model. In the second case we consider a particular firing rate model of a neuron with a slow calcium current that admits to an exact analysis. Once again existence regions for cluster states are explicitly calculated. Both mechanisms are shown to prefer globally synchronous states for slow synapses as long as the strength of coupling is sufficiently large. With a decrease in the duration of synaptic inhibition both systems are found to break into clusters. A major difference between the two mechanisms for cluster generation is that anode break excitation can support clusters with several groups, whilst slow T-type calcium currents predominantly give rise to clusters of just two (anti-synchronous) populations.

Relationship between therapeutic changes in blood pressure and outcomes in acute stroke: a metaregression

Both low and high blood pressure (BP) during the acute phase of stroke are associated independently with a poor outcome. Several small clinical trials have involved the alteration of BP and this study assessed the relationship between change in BP and functional outcome. Randomised controlled trials of interventions that would be expected, on pharmacological grounds, to alter BP in patients within one week of the onset of acute ischaemic or haemorrhagic stroke were sought using electronic searches. Data were collected on BP and clinical outcome. The relationship between the difference in on-treatment BP and odds ratios (OR) for outcomes was assessed using meta-regression. Thirty-seven trials involving 9,008 patients were included. A ‘U’ or ‘J’ shaped relationship were found between on-treatment BP difference and early death, death at the end of 90 day follow up, and combined death or dependency at the end of follow up. Although outcomes were not significantly reduced at any level of change in BP, the lowest odds occurred at: early death (OR 0.87, 95% confidence interval, CI 0.54 to 1.23) - 8.1 mmHg; death at end of follow up (OR 0.96, 95% CI 0.31 to 1.65) - 14.4 mmHg; and combined death or dependency at end of follow up (OR 0.95, 95% CI 0.11 to 1.72) - 14.6 mmHg. Although large falls or increases in BP are associated with a worse outcome, modest reductions may reduce death, and combined death or dependency, although the confidence intervals are wide and compatible with overall benefit or hazard.