This line of research started in 1997 and involves joint work of Amedeo Cesta and Angelo Oddi
with a long term collaboration with Steve Smith (CMU).
The general idea is to build scheduling heuristics on top of a temporal representation based on
a Simple Temporal Network. Additional ideas have been:
Extending the Precedence Constraint Posting Algorithm by Cheng&Smith (AAAI-94) with the idea
of heuristically biased random restart
[Oddi, A. and S.F. Smith, "Stochastic Procedures for Generating Feasible Schedules",
Proceedings 14th National Conference on Artificial Intelligence (AAAI-97), July, 1997].
Implementing a tabu search algorith using the efficient dynamic services of our STP
implementation. In this paper for example we address a scheduling problem in which contrait
violations can be accepted but minimized [Oddi, A. and Cesta, A., A Tabu Search Strategy to
Solve Scheduling Problems with Deadlines and Complex Metric Constraints, In Sam Steel,
Rachid Alami (Eds.), Recent Advances in AI Planning, Fourth European Conference on Planning
(ECP-97), LNAI 1348, pp. 351-363, Springer-Verlag 1997].
In a number of papers we have studied problems with multi-capacity resources and temporal
separation constraints between activities. It is to be noted that specifying maximum distance
constraint between two activities of the Schedule makes the satisfability problem NP-Hard
(see [Bartush et al. 88]). We have studied various scheduling problems having both these features:
An extension of Job-Shop called Multi-Capacity Metric Scheduling Problem (MCM-SP):
[Cesta, A., Oddi, A., Smith, S.F., Profile-Based Algorithms to Solve Multiple Capacitated Metric
Scheduling Problems, Proceedings of the Fourth International Conference on Artificial
Intelligence Planning Systems (AIPS 98), Pittsburgh, PA, June 1998.];
[Cesta, A. Oddi and S.F. Smith (1999). Greedy Algorithms for the Multi-Capacitated Metric Problem.
European Conference on Planning ECP-99, Durham University, UK, 8-10 Settembre, 1999. pp. 215-227.
Il Multi-Capacity Job-Shop (MCJSSP) also addressed by Nuijten. Here the main result is connected
to addressing problems of relevant size:
[Cesta, A. Oddi, A. and S.F. Smith (2000). Iterative Flattening: A Scalable Method for Solving
Multi-Capacity Scheduling Problems. Seventeenth National Conference on Artificial Intelligence
(AAAI 2000). July 30-August 3, 2000, Austin, Texas (USA)].
A number of studies have driven as to the Resource Constrained Project Scheduling Problem with
Generalized Precedence Relations (RCPSP/max) and to synthesize the ISES algorithm that integrates
several of our basic techniques: [Cesta, A. Oddi, A. and S.F. Smith (1999). An Iterative
Sampling Procedure for Resource Constrained Project Scheduling with Time Windows. Proceedings
International Joint Conference on Artificial Intelligence '99 (IJCAI-99). 31 Luglio - 6 Agosto,
1999, Stoccolma, Svezia.pp.1022-1029];
[Cesta, A. Oddi and S.F. Smith (2002). A Constrained-Based Method for Project Scheduling with
Time Windows. Journal of Heuristics, 8:109-136].
Being a research group that survives with external funding we have recently worked at solving
specialized scheduling problems in various application domains. This is an example from a space
domain scheduling problem:
[Oddi, A., Policella, N., Cesta, A. and Cortellessa, G., Constraint-Based Random Search for
Solving Spacecraft Downlink Scheduling Problems, Proceedings of MISTA-03, Nottingham, UK,
We are currently enlarging our interest to problems connected to the schedule execution, schedule
robustness, and reactive revision of schedules. As soon as we'll have stable results they will
integrate this page.