Software systems and technologies

Human Selection of Scheduling Heuristics (HuSSH):  The HuSSH system has been the first software system of its kind to act  as a  work-ground for a humanised hyper-heuristic system. This system allows the expert user to work at the higher level of generating/selecting heuristics for construction and modification of the solutions. This aims to provide the user with more control on the construction and modification of the solution than simple decisions/moves available in other systems.  This software has been subject of an international competition in PATAT2002 in Belgium.

Semantically Transparent Approach to Representing Knowledge (STARK): The STARK system uses an innovative  representation for timetabling problems based on  principles of representational design, from cognitive science, to present timetables in a way which minimises the cognitive load associated with understanding and editing them. This system allows the user to observe and modify a timetable where all the specifications and the problems with the timetable are visually presented and changes to the solution are made possible in an intuitive way. This software has been subject of an international competition in PATAT2002 in Belgium.

New benchmarks for the Capacitated Clustering Problems

Standard benchmarks for the Capacitated Clustering Problems have been small in size (50 and 100 points). We have introduced  new sets of data with similar characteristics to the standard benchmarks but in larger sizes. Our data sets are in sizes of 150, 300 and 500 points. The smaller instances are already adapted by researchers in this area and the larger instances, due to difficulty of even finding bounds for their solutions, have introduced new challenges for handling this problem to the researchers. The data sets with the instructions and the best found solutions so far can be downloaded from our web site.

An Extensible Modelling Framework for Timetabling Problems

We have introduced a new modelling language for optimisation and specifically timetabling problems. This framework has been used in our VAST system which aims to:

1. To translate between different standard formats of data in literature and hence reducing the burden on researchers for handling the data. This promotes standardisation of  the formats for data for timetabling problems.  The system could be extended by providing a mechanism to define new formats.
2. Use of graph theoretical approaches to reduce the problem space to a smaller scale and hence making it feasible to manually schedule an exam timetable for complex real world cases.
3. Provide rich visualisation which extends the STARK system and enables the user to  understand the problem and generate solutions manually
4. Act as an optimisation system where new algorithms in java could be plugged in and used for improving the solutions.

The work on VAST system has been by Mr Dave Ranson (DPhil student in Sussex University) and Dr Samad Ahmadi through several projects at different levels and as part of DPhil project of Mr Ranson.

Density Search Constructive Method (DSCM): We have introduced Density Search Constructive Method (DSCM) for solving clustering problems. The DSCM finds patterns of natural sub-groupings in the input data using the concept of density of points. Elements of adaptive computation and periodic construction-deconstruction have been implemented within the constructive heuristic which also develops a general framework for building efficient heuristics.

GRAMPS: We have also introduced a powerful merger of greedy random adaptive search procedure (GRASP) and adaptive memory programming (AMP) into a new GRAMPS framework for the CCP. A learning process was kept in charge of tracking information on the best components in an elite set of GRAMPS solutions and the information was strategically combined with problem-domain data to restart the construction search phase. We have proposed a perturbation based local search algorithm based on perturbations of input data with a controlled perturbation strategy and intensification and diversification strategies.