• [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

Research
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 vehicle routing). 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] below). And of course, the study of algorithms and problems is both fascinating and rewarding.

Research Grants
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 and problems).

• [1990-1992] Joint grant holder on BT funded project Real-time resource allocation using distributed and cooperative knowledge-based architectures. 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. (principal investigator).
• [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.
• [1998] 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

Research Students
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
Over the past 9 years I have developed 5 new courses.

• [1989-1991] Functional programming in ML, 4th year course
• [1989-1998] Artificial Intelligence, 4th year course
• [1995-1997] The Functional Interpretation of Programs, 2nd year course
• [1996-1998] Computer Science Literature, 3d year course (with Ian Gent)
• [1998-now] Data Structures and Algorithms in Java, 2nd year, 2 semester course

Departmental Duties

• Member of Departmental Management Committee (DMC)
• Chair of Research Committee (since August 1998)
• Member of Faculty Research Committee
• Research Seminar Coordinator

• BT Research Labs in Martelsham.
• ILOG, most recently with the development of ILOG Dispatcher in the GreenTrip project
• Pirelli in Milan
• Tollpost-Globe AS Norway
• SINTEF, Department of Optimisation, in Oslo.

• Member of editorial board of the Journal of Artificial Intelligence Research (JAIR).
• 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 MASCADA.

• 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, Topical Conference on NP-hardness and Phase Transitions, Trieste, September 1999
• The Next Generation: panel discussion at the First CONSNET meeting Edinburgh, 17th September 1999

Personal
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.

Note: electronic versions of many of these papers are available from the APES pages

Journals

1. P Burke and P. Prosser,``A Distributed Asynchronous System for Predictive and Reactive Scheduling,'' The International Journal for Artificial Intelligence in Engineering, 6(3), 106-124, July 1991
2. P. Prosser, C Conway, C Muller ``A constraint maintenance system for the distributed resource allocation problem'', Intelligent Systems Engineering, 1(1), 76-83, Autumn 1992
3. P. Prosser ``Hybrid algorithms for the constraint satisfaction problem'' Computational Intelligence, 9(3), 268-299, August 1993
4. P. Prosser, and J.T. Buchanan, ``Intelligent Scheduling: past, present, and future'', Intelligent Systems Engineering, 3(2), 67-78, Summer 1994
5. C. Brind, C. Muller, and P. Prosser, ``Stochastic Techniques for Resource Management'', the BT Technology Journal, 13(1) (1995) 55-64
6. P. Prosser ``An empirical study of the phase transition in binary constraint satisfaction problems'', Artificial Intelligence 81 (1996) 81-109
7. B. De Backer, V. Furnon, P.J. Kilby, P. Prosser, P. Shaw, ``Solving Vehicle Routing Problems using Constraint Programming and Meta Heuristics'', Journal of Heuristics, to appear 1999
8. P.J. Kilby, P. Prosser, P. Shaw, ``A comparison of traditional and constraint-based heuristic methods on vehicle routing problems with side constraints'', Journal of Constraints 5(4) 389-414 (2000)
9. I.P. Gent, E. MacIntyre, P. Prosser, B.M. Smith and T. Walsh ``Random Constraint Satisfaction: flaws and structures'', submitted to Journal of Constraints, October 1998
10. I.P. Gent, P. Prosser, T.Walsh ``A theory of constrainedness" submitted to JACM 1999
11. I.P. Gent, B. Johnston, P. Prosser ``Thinking on your feet in undergraduate computer science: a constructivist approach to developing and assessing critical thinking" Journal of Teaching in Higher Education 4(4) 511-522 (Special Issue on Critical Thinking) 1999

Conferences

1. P. Prosser ``A hybrid genetic algorithm for pallet loading'' Proceedings European Conference on Artificial Intelligence (ECAI-88), 159-164, Munich, August 1988
2. P. Prosser ``A reactive scheduling agent'', IJCAI-89, Proceedings of eleventh joint international conference on Artificial Intelligence, August 1989, Detroit Mi, 1004-1009
3. P. Burke and P. Prosser, ``Simulating Distributed Decision Making Under Constraints,'' Proceeding of Summer Conference on Computer Simulation, Calgary, 1990
4. P. Burke and P. Prosser ``Distributed Asynchronous Scheduling'', In Applications of Artificial Intelligence in Engineering V, Vol 2: Manufacture and Planning, 503-522 Proceedings of the 5th International Conference, Boston, USA, 1990, Editor: G. Rzevski
5. J.T. Buchanan and P. Prosser ``Resource Allocation - A Distributed Approach'', in Advanced Software Technology for Air Transport, ed R Behrendt and L Bertsch, AIT Press, 37-48, 1992
6. P. Prosser, C. Conway, C. Muller, ``A distributed constraint maintenance system'' AVIGNON-92, 221-231, 1992
7. P. Prosser, ``BM+BJ=BMJ'', Proceedings CAIA-93 (Conf Artif Intell Appln) Orlando, 257-262, Florida, March 1-5, 1993
8. P. Prosser ``Domain filtering can degrade intelligent backjumping search'' Proceedings IJCAI-93 (Int Joint Conf Artif Intell), 262-267, Chambery, France, 1993
9. J.T. Buchanan and P. Prosser ``A Distributed Dynamic Scheduling Architecture Applied to an Aluminium Plate Plant'', in Proc of Production Planning and Control in the Metals Industry, March 1993
10. P. Prosser, ``Binary constraint satisfaction problems: some are harder than others'', Proceedings ECAI-94 (European Conf A I), 95-99, Amsterdam, August 1994
11. I.P.Gent, E. MacIntyre, P. Prosser, T. Walsh ``Scaling effects in the CSP phase transition'' in Proceedings of the first International Conference on Principles and Practices of Constraint Programming, CP95, pages 70-87, 1995
12. I.P. Gent, E. MacIntyre, P. Prosser, B.M. Smith, T. Walsh ``An empirical study of dynamic variable ordering heuristics for the constraint satisfaction problem'' Proceedings CP96, pages 179-193, 1996
13. I.P. Gent, E. MacIntyre, P. Prosser, T. Walsh ``The constrainedness of search'' in Proceedings AAAI-96, pages 246-252, 1996
14. I.P. Gent, E. MacIntyre, P. Prosser, T. Walsh, ``The scaling of search cost'' in Proceedings AAAI-97, pages 315-320, 1997
15. I.P. Gent, E. MacIntyre, P. Prosser, P. Shaw, T. Walsh ``The constrainedness of arc-consistency'' in Proceedings CP97, pages 327-340, 1997
16. P.J. Kilby, P. Prosser and P. Shaw, ``Guided Local Search for the Vehicle Routing Problem with time windows'', in Meta Heuristics: advances and trends in local search paradigms for optimisation, pages 473-486, Kluwer Academic Publishers, 1999 pages 89-90
17. P.J. Kilby, P. Prosser, and P. Shaw ``Generating Solutions for Real-World Vehicle Routing Problems'' in Proceedings INFORMS 1998
18. E. MacIntyre, P. Prosser, B.M. Smith, and T. Walsh ``Random Constraint Satisfaction: theory meets practice'', Proceedings CP98, pages 325-339, 1998
19. P. Prosser ``The Dynamics of Dynamic Variable Ordering Heuristics'' Proceedings CP98, pages 17-23, 1998
20. M. Bouzoubaa, G. Hasle, P. Prosser ``The GGT: a generic toolkit for VRP applications and modelling". proceedings of the International Conference of Practical Applications of Constraint Logic Programming, PACLP99, 1999
21. I.P. Gent, H. Hoos, P. Prosser, T. Walsh ``Morphing: combining structure and randomness" in proceedings American Association of Artificial Intelligence, AAAI99, 1999
22. I.P. Gent, P. Prosser, T. Walsh ``The Constrainedness of Constraint Satisfaction" The Topical Conference on NP-hardness and Phase Transitions, ICTP, Trieste, September 1999

Books (invited chapters)

1. P. Prosser, ``Forward checking with backmarking'', in M. Meyer (ed); Constraint Processing, LNCS 923, Springer-Verlag, Heidelberg, ISBN 3-540-59479-5, pages 185-204, 1995
2. P. Burke and P. Prosser, ``Distributed Asynchronous Scheduling'' in Intelligent Scheduling, editors M.Zweben and M.S.Fox, published by Morgan Kaufmann, ISBN 1-55860-260-7 1994
3. P. Prosser, ``Scheduling as a constraint satisfaction problem: theory and practice'' in Scheduling of Production Processes, J. Dorn and K.A. Froeschl (eds), Ellis Horwood, 22-30, ISBN 0-13-075136-7 1993.
4. P. Prosser, ``Data Integrity and Security'' in Database Management Systems, editor R.A. Frost, Granada Publishing Ltd, 199-220, ISBN 0-246-11974-8, 1984

Workshops

1. J.T. Buchanan, P Burke, J Costello, P Prosser, ``An Intelligent knowledge-based scheduler for heavy manufacturing.'' Colloquium on Artificial Intelligence in Planning and Production Control, pp 61-63, The Institution of Electrical Engineers, Computing and Control Division, Savoy Place, London, 1988.
2. P. Prosser ``Reactive Factory Scheduling as a Dynamic Constraint Satisfaction Problem,'' Report of the 8th Workshop of The Planning Special Interest Group (PLANSIG), Nottingham, 1988.
3. P. Burke and P. Prosser, ``Distributed Scheduling: An Approach to Executional Uncertainty,'' Report of the 9th Workshop of The Planning Special Interest Group (PLANSIG), Nottingham 1990.
4. P. Prosser, ``Hybrid Algorithms for the Constraint Satisfaction Problem: BMJ and BM-GBJ'' Proceedings of the 10th UK Planning SIG, April 1991
5. P. Prosser, ``A Hybrid Algorithm for the Constraint Satisfaction Problem: EFC-GBJ, Checking Forwards while Jumping Back'', Proceedings of the 10th UK Planning SIG, April 1991
6. P. Prosser, ``The future of scheduling - DAI?'' IEE Colloquium on Advanced software technologies for scheduling, April 1993
7. P. Prosser ``Predicting really hard scheduling problems'', IFIP WG5.7 SIG on Knowledge-based Reactive Scheduling, 1994
8. P. Prosser ``Phase transitions: a brief history of the phenomenon in binary constraint satisfaction problems'' AISB-95 workshop on Automated Reasoning, Bridging the gap between theory and practice. April 1995
9. B. DeBaker, V. Furnon, P.J. Kilby, P. Prosser, and P. Shaw ``Local Search in Constraint Programming: Application to the Vehicle Routing Problem'' in Proceedings of CP97 Workshop on Industrial Constraint-Directed Scheduling, pages 1-15

1. J.C. Hendry and P. Prosser, ``The clamping force at die-container interface for the forward extrusion of rod'' NEL Report 523, DTI, September 1972
2. P. Prosser, ``Performance Tests on a Reactive Scheduling Agent,'' Technical Report AISL-45, Department of Computer Science, University of Strathclyde, January 1990.
3. P. Prosser, ``Backjumping Revisited'', Research Report AISL-47-92, August 1992
4. P. Prosser ``MAC-CBJ: maintaining arc consistency with conflict directed backjumping'' Research Report 95/177, March 1995
5. I.P. Gent, P. Prosser ``The 50% point in the constraint satisfaction problem'' Research Report 95/180, May 1995
6. P. Prosser, P. Shaw ``Study of greedy search with multiple improvement heuristics for vehicle routing problems'', Research Report 96/201
7. I.P. Gent, S.A. Grant, E. MacIntyre, P. Prosser, B.M. Smith, T. Walsh, ``How Not To Do It'', Research Report 97.27, School of Computer Studies, University of Leeds, 1997
8. P. Prosser and P. Shaw ``Study of greedy search with multiple improvement heuristics for vehicle routing problems'', Research Report 96/201, University of Strathclyde, December 1996.
9. P. Kilby, P. Prosser, and P. Shaw ``Implementation of LNS for Constrained VRPs'' APES Technical Report APES-01-1998, April 1998
10. P. Kilby, P. Prosser, and P. Shaw ``Dynamic VRPs: A Study of Scenarios'', APES Technical Report APES-06-1998, September 1998

Non-Professional Publications

1. P. Prosser, ``Observations on tetrahedral kites'' The Kiteflier, Newsletter of the Kite Society of Great Britain, Issue 54, 20-24, January 1993. An electronic copy is here.
2. P. Prosser ``Beobachtungen zu tetraedischen Drachen'' Drachen Magazine, Summer 1993