[1973-1977] University of Strathclyde, BSc Computer Science
[1987-1991] University of Strathclyde, PhD Computer Science
[1970-1973] National Engineering Laboratory, Scientific Assistant
[1977-1979] Burroughs Machines, computer programmer
[1979-1983] University of Strathclyde, Research Fellow
[1983-1987] Britoil (previously BNOC), systems manager
[1987-1989] University of Strathclyde, Senior Research Fellow
[1989-1998] University of Strathclyde, Lecturer
[1998-now] University of Strathclyde, Senior Lecturer
I am interested in the nature of computation, the behaviour of algorithms and
heuristics, and what makes problems hard.
This has focussed my research onto combinatorial search (in particular constraint satisfaction)
and its practical application (typically jobs shop scheduling, workforce management, and
In 1995 I jointly founded the APES (Algorithms, Problems, and Empirical Studies) research group,
with Dr Ian Gent (St. Andrews),
Dr Toby Walsh (York), and
Dr Barbara Smith (Leeds).
Recently the APES group has grown, with Prof's Peter van Beek and Joe Culberson from Alberta
joining us, along with Josh Singer from Edinburgh.
Although we are no longer under the one roof, we work together closely via the internet,
we meet regularly, and we make a point of enjoying each other's company whenever possible.
Twelve years outside of academia (3 at NEL, 2 at Burroughs, 3 at Alcan, 4 at Britoil)
have flavoured the way I do research. I try and face up to two question: the classic MIT
question ``So?'' (resurrected by Peter van Beek) and the Toby
Walsh question ``What general lessons can we learn?'' (see the Conclusion of any APES papers with Toby).
The ``So?'' question is usually easy to answer, as most of our
results carry over quickly to commercial applications (and that is the nature of research
in algorithms and heuristics). For examples see the GreenTrip project, ILOG's subsequent product
Dispatcher, Toby's DDS algorithm (now reduced to a method within ILOG Solver), Paul Shaw's
large neighbourhood search, the work done with BT on workforce
management, and the Distributed Asynchronous Scheduler.
One of our more ``general lessons'' has
come from our theory of constrainedness.
Our measure of constrainedness has been
applied to many NP-complete problems and has been shown to hold across complexity classes (i.e. downwards
to P and upwards to Pspace). Two surprising results from our theory is that it can be used as a guiding
principle when designing heuristics to solve problems, and when allied with techniques from statistical
mechanics allows us to estimate the computational costs associated with solving problems.
The natural sciences are
now lending a hand in our studies of algorithms and problems, with the realisation that the behaviour of algorithms
and problems have much in common with the behaviour of natural systems (see conference papers [10,11,13,14,19,21,22]
And of course, the study of algorithms and problems is both fascinating and rewarding.
Over the last 10 years I have attracted in excessive of 1.25 million pounds of research
funds to this University, from industry, the EU, and EPSRC. The research has been a mix
of applied (scheduling, routing, resource allocation) and theoretical (the study of algorithms
[1990-1992] Joint grant holder on BT funded project Real-time resource
allocation using distributed and cooperative knowledge-based
Total grant value
approximately 300,000 pounds (co-investigator)
[1993-1995] Joint grant holder on BT funded project A study of DAI
techniques for resource allocation.
Total grant value approximately 242,600 pounds (co-investigator).
[1995-1996] BT funded project, Study of stochastic search applied to
workforce management; grant value approximately 54,000 pounds (principal investigator).
[1995-1998] EPSRC Grant GR/K/65706
An Empirical Study of Constraint Satisfaction Problems,
grant value 101,000 pounds (principal investigator).
[1996-1999] EU ESPRIT 20603 GreenTrip, The incorporation of stochastic search
techniques into a constraint toolkit. Grant value approximately 240,000 pounds.
[1996-1999] EPSRC Grant GR/L2401
Constrainedness of Computational Problems.
Grant value 157,000 pounds. Grant jointly held with Dr. Ian Gent, and proposed
with Dr Toby Walsh.
[1998-2000] I am one of the initial nodes within the EU Network of Excellence (NoE)
in planning and scheduling, namely PLANET.
 EPSRC Visiting Fellowship GR/M54605, for Dr Joe Culberson (Alberta) to visit
Strathclyde (Dr. Ian Gent is principal investigator, I am co-investigator).
[1999-2001] EPSRC Grant GR/M66110, UK Constraint Network:
CONSNET, a national Network of Excellence
in constraint programming. Jointly with Imperial College, Royal Holloway, City University, and
Cardiff. Grant value 40,000 pounds
[2000-2003] EPSRC grant GR/M90641
Problem Reformulation and Search. Grant value appox 156,000 pounds
I have supervised Dr. Claude Muller (jointly with Evan Magill), Mr. Craig Brind
(now data mining in Glasgow with KWIZ Solutions), Mr Ewan MacIntyre and Mr Dave Clark (now both with
AtLanTec), and Kostas Stergiou
(jointly with Ian Gent and Toby Walsh). Craig, Ewan, and Dave could not resist the commercial world.
I now have my money firmly on Kostas.
Teaching is a kind of research. The development and delivery of a new lecture course has all
the ingredients of research. We have an idea (hypothesis) of how we can best do something
(i.e. transfer knowledge) and we must then measure how effective that has been (i.e. assessment).
One feature of teaching is the tight coupling between what is actually learned and how it is assessed.
This has been investigated recently, with Bill Johnston, Ian Gent and myself in the
Computer Science Literature course above
(see journal publication  below). My most recent course, on Algorithms and Data Structures
in Java, makes extensive use of the internet, automated assessment, plagiarism detection,
and peer assistance. Bill Johnston and I are in the process of analysing the course, and we will again
publish our findings.
Over the past 9 years I have developed 5 new courses.
Member of Departmental Management Committee (DMC)
Chair of Research Committee (since August 1998)
Member of Faculty Research Committee
Research Seminar Coordinator
I have been on numerous workshop and conference programme
committees. These are listed below.
Member of editorial board of the Journal of Artificial Intelligence
EPSRC College Member, IT and Computer Science Program, 1995/96
EU Expert Reviewer for Long Term Research proposals, 1997 to 1998
Project Reviewer for EU research project 22728
European Conference on Artificial Intelligence (ECAI-92), Workshop W7,
Scheduling of Production Processes, Vienna, Austria
Committee member for the International Joint Conference on Artificial
Intelligence (IJCAI-93) Special Interest Group on Manufacturing (SIGMAN),
Committee member IFIP TC5/WG.5.7, Special Interest Group on Knowledge
Based Reactive Scheduling, Budapest, Hungary.
Chairman of the 13th UK Special Interest Group on Planning and Scheduling
Committee member for the 1994 European Conference
on Artificial Intelligence (ECAI-94) workshop on Constraint
Satisfaction Issues Raised by Practical Applications, Amsterdam, The Netherlands
 Committee member CONSTRAINTS-95, International
Workshop on Constraint Based Reasoning (in conjunction with FLAIRS-95),
Programme Committee member of 14th UK Special Interest
Group on Planning and Scheduling
 Programme Committee member of CONSTRAINTS-96, the Second
International Workshop on Constraint Based Reasoning, Florida.
Programme Committee member of 3d International Conference
on Artificial Intelligence Planning Systems (AIPS-96).
Programme Committee member ECAI-96 workshop on Intelligent Scheduling.
Programme Committee member ECAI-96 workshop on
Empirical Artificial Intelligence.
Programme Committee member of 15th UK SIG on Planning and Scheduling.
 Programme Committee member CONSTRAINTS-97, the third International
Workshop on Constraint Based Reasoning.
Programme Committee member European Conference on Planning
Programme Committee member Constraint Programming 97,
Workshop on Industrial Constraint Directed Scheduling.
 Programme Committee member 16th UK SIG on Planning and Scheduling.
Programme Committee member 4th International Conference on Artificial
Intelligence Planning Systems (AIPS-98)
 Programme Committee member, 16th UK SIG on Planning and Scheduling
 Programme Committe member,
The Constraints Stream of the Computational Logic Conference 2000.
Genetic algorithms for Pallet loading, BBN, Boston USA (1988)
Distributed Asynchronous Scheduling, Turing Institute, (1989)
Phase transitions in constraint satisfaction problems, John Moores
University, Liverpool (1995)
The Constrainedness of Search, Aberdeen University, (1997)
A Look Back at the Distributed Asynchronous Scheduler, Dept AI, Edinburgh University (1997)
Panel Session, The First Research Seminar on Constraints, Royal Holloway,
May 6th 1998
The Behaviour of Heuristics, Fourth International Conference on Principles and Practice of Constraint Programming - CP98, Pisa, November 1998
Heuristics for Constraint Satisfaction, Cardiff, January 1999
Reactive scheduling: from DAS to Dispatcher, the 1st PLANET Workshop on Dynamic
Scheduling, LAAS-CNRS, Toulouse, February 1999
The Constrainedness of Constraint Satisfaction, ICTP,
on NP-hardness and Phase Transitions, Trieste, September 1999
The Next Generation: panel discussion at the First
CONSNET meeting Edinburgh, 17th September 1999
I am married, happily, to Andrea, even though she admits that on occasion she would gladly
kill me. I have a 7 year old daughter, Zoe. I swim, cycle, and
in my free time I build and fly kites.