On-line dynamic scheduling represents the core engine for many Artificial Intelligence systems. Such systems are needed in various real applications such as workforce scheduling, autonomous satellite management or radar management. These applications are described in the first part of the roadmap. The second part describes what is new with on-line scheduling, compared to classic off-line scheduling. Several issues are discussed here. The third part outlines current techniques to answer the numerous questions raised by each issue and the difficulties which remain. All these questions are assembled in a table in the fourth section where a degree of maturity is associated to the current techniques for answering a question.

We use the term on-line to refer to operational constraints. An on-line system must interact with the outside world in a continuous and reactive way. Thus, on-line scheduling means bridging the gap between theoretical scheduling and real-world scheduling. In real-world problems, the notion of scheduling is not clearly differentiated from the notion of planning and implies reasoning about actions, states, resources and time globally. Moreover, real-world problems are dynamic, uncertain and often unpredictable.

The objective of scheduling is either to bring the controlled system into a given state or to perform a given level of service permanently. In either case, the classic features of a solution provided by scheduling are its feasibility and its quality. A new feature of any solution is its adequacy to the context as it is when the solution is provided. The faster the solution is produced, the higher its adequacy is. As finding feasible and high quality solutions may take a long time, there is an obvious contradiction between solution feasibility and quality on the one hand and solution adequacy on the other hand. We think that this contradiction is the main problem of on-line scheduling as compared to off-line scheduling and that it must be addressed.

There are different software architectures for on-line systems, such as blackboards or systems with reactive and deliberative components. Although the corresponding techniques are quite mature, it is still difficult to have a clear separation and interaction definition between the reactive and deliberative components.

When scheduling actions, it is necessary to specify on which temporal horizon one wants to schedule, i.e., which set of possible actions and which temporal windows for them one considers. This horizon may be fixed either statically or dynamically. In the latter case, it is difficult to determine a good trade-off between computation time and horizon length. In multi-level scheduling, a problem can be modeled by a set of nested horizons, with a scheduling granularity associated with each of them and increasing with size. The interactions between scheduling levels has to be defined. Instead of high levels making high-level decisions that are imposed on lower levels, these lower levels may continue to use as advice the solutions produced by higher levels. However, they must be able at any moment to make decisions by themselves, when the adequacy of these solutions has clearly become too bad. See hierarchical planning, blackboard systems and mixed-initiative problem solving.

Once scheduling horizons have been fixed, we have to decide when a new schedule should be computed. This will influence the solution adequacy. The scheduler should recompute a new schedule when new conditions invalidate the current schedule, or when the end of the current horizon is closed. An invalidating condition can be a new event (e.g. a new activity, a resource failure, a new criterion requested by the operational user) or a new estimation from sensors (e.g. an updated temporal constraint). Rescheduling can be either event driven or periodic. For detecting and repairing an invalidating schedule, we need tools for solution analysis, conflict explanation and relaxation proposal. There are many links with research on solving over-constrained problems.

A major operational constraint is temporal constraint on reasoning. We can distinguish three kinds of temporal constraint: (i) the temporal deadline is known, the system must deliver a good solution before the end of a given time contract, (ii) the temporal deadline is unknown, the system can be interrupted and asked for a solution at any time, the scheduler should perform well on average during a specified temporal interval, (iii) the temporal deadline is unknown, the system chooses the right moment to deliver its solution. The first case (i) implies using a mechanism for algorithm selection depending on time contracts. For tree search methods, it is important to estimate the number of nodes developed by the search. It is difficult to have a reliable estimation, especially in an optimisation context. The second case (ii) implies using iterative methods, which progressively increase the size of their exploration at each iteration, from a greedy search to a complete search. The last case (iii) implies using a meta-reasoning mechanism based on the notion of utility. Cases (ii) and (iii) are very challenging.

Most of the time, the scheduler has to solve a dynamic problem, in the sense that the new problem to be solved is different from the previous one (the scheduling horizon has been shifted, some of the previously scheduled actions have been executed, changes may have to be considered). However, it is not so different. The scheduler can benefit from a learning mechanism based on solution reuse, on reasoning reuse (set of no-goods), or on both. Special interest has been devoted to incremental constraint retraction mechanisms. Sometimes, problem changes are difficult to identify.

Robustness is an important property of solutions. A solution is said to be robust if it resists changes. A related property is flexibility. A solution is said to be flexible if it is easy to repair, in the case of problem changes. We need a model of the possible changes in order to produce change-proof or flexible solutions. Models of uncertainty have been studied in mathematical research, for example in Decision Theory, Utility Theory and Game Theory. The Markov Decision Process extended to problems with constraints is a promising research direction.

Solution stability is important in all applications where changes in schedule are costly or difficult to execute. A new solution is stable with respect to the previous one if there are few changes between the two solutions. But it must be noted that a contradiction appears between solution quality and stability. Several algorithms are currently being developed and experimented to produce stable solutions.

Sometimes, the problem or its solving method are distributed. The reason may be geographical (different places), organisational (different companies) or simply because it is easier to solve (problem decomposition). If we want to introduce either cooperation or conflict resolution, distributed decision-making protocols have to be proposed. See multi-agent scheduling techniques.

A difficult problem remains: how to validate an on-line scheduling system? And how to measure the solution adequacy ? We can compare the on-line scheduler with an optimal off-line scheduler, as is done in research about on-line algorithm.

In conclusion, we think that on-line scheduling requires further work on theory, algorithmic and experiments. It is a real challenge to obtain efficient generic tools for on-line scheduling, comparable with problem-dependent approaches.

On-line scheduling is a combination of several Artificial Intelligence research areas, e.g. Operations Research, Constraint Satisfaction Problems, Constraint Logic Programming, Planning, and realtime-oriented research areas, e.g. Hard-Real-Time Systems, Anytime problem solving. Other related research areas should be employed: Case-Based Reasoning, Machine Learning, Decision Theory, Utility Theory, Game Theory, Risk Management, Markov Decision Process, Reinforcement Learning, On-Line Algorithms, Multi-criteria techniques...

The novelty of on-line scheduling compared to off-line scheduling resides mostly in new solution properties, such as its adequacy, its robustness, its stability. Such properties can be in contradiction with its quality. Dealing with this issue is the main challenge of on-line scheduling.

Last changed: 23.09.2003