Intelligent Workflow - State of the Art in Scheduling

Summary of literature search

There is a large body of work in the area of scheduling ranging from OR based "traditional" approaches to some exotic "AI" based approached such as genetic algorithms. However, there appears to be much in common with all the efforts. They are all constraint-based and either conform to a constructive or a repair (iterative improvement) approach to the problem.

Constraint-based Scheduling

Scheduling is an extremely difficult and complex problem with a huge variety of types of problem and application domains. There is a large body of work from the fields of operations research and artificial intelligence. Recent research and application of constraint-based or constraint-directed approaches to the problem of scheduling have demonstrated a surprising degree of effectiveness and generality. However, even within this class of algorithms there are a wide variety of techniques. The basis of the constraint approach is in the formulation of the problem. The topology of the problem is represented as a constraint graph or network where the nodes are activities to be scheduled and the acs represent the constraints between them.

Scheduling is often viewed as an optimization problem but in very large domains or domains where the definition of an optimal solution is more difficult than the problem itself scheduling is often classed as a constraint satisfaction problem (CSP).

Generative Techniques

Generative techniques start with an empty schedule and construct the schedule usually using some type of search technique. This usually involves steping through the instantiation of values to variables to prune the search space and backtracking when an inconsistency is detected. These techniques have many advantages: the search strategy is complete and straightforward; solution quality can be controlled dynamically through the variable amd value ordering. Variable orderingis the order in which values are instantiated to variables. Forward checking is the most common and well known constructive search algorithm for CSP problems, it uses a depth -first search procedure, backtracking when an infeasibility is found, but at each stage it uses the constraints to look ahead at the effect of the current choice on future choices. In recent years, more algorithms with greater levels of look ahead have been the basis of much research. Full look ahead including Maintaining Arc Consistency (MAC) is increasingly popular and some interesting results have been obtained when combining its study with the phenomenon of phase transition (Grant and Smith '95

Iterative Repair Techniques

The idea behind iterative repair is to start with a proposed solution, or population of solutions, which may or may not even be feasible. The solution, or solutions, are modified in some way and compared with the previous "best so far" solution. This process is called "instensification" and causes incremental improvement. To avoid local optima, these techniques normally also have a "diversification" strategy which will cause a worse than "best so far" solution to be retained. Some examples of these "anytime" algorithms are simulated anealing, genetic algorithms, ans varients on the min-conflict heuristic.

Research

It appear that research in the ares of intelligent scheduling has been moving forward in a number of different and perhaps complimentary directions. For example there has been a tendency towards distributed systems, e.g., (Musliner and Boddy '96) using the contract net protocol, DAS (Burke et al. '91) with hierarchical organisation of agents, REDS (Hadavi et al. '92) and (Ghedira and Verfaille '92). Also a move towards the use of stochastic or iterative repair techniques including scheduling the Hubble Space Telescope (Swanson et al. '94) (Zweben et al. '92), using learning to improve scheduling (Zweben '92), case-based programming in scheduling (Sycara and Miyashita '92), abstraction techniques (Berry et al.) and the improvement of constructive CSP algorithms (Prosser '92) as well as the use of capacity analysis and texture measures to improve schedule quality, (Berry '92) and (Sadeh '91).

Adaptive Scheduling

The approach we propose in this projects is to maintain a variety of scheduling algorithms envoking the algorithm most suited to a particular scheduling problem state. There has already been some work done in this area (Borrett et al.)

It is the intention of this project to implement and evaluate a suite of scheduling algorithms for agent tasking which can be applied according to the current problem situation and temporal interval concerned. This will include scheduling in the face of incomplete plans.

Some asset assignment may have to occur before a complete plan has been developed. It is important that a scheduling system be able to handle different levels of abstraction and reason effectively about constraint loading and availability. Thus, an adaptive algorithm will be able to apply the algorithm must suited to the level of temporal reasoning. There are several suitable algorithm suites available.

Commercial
Non-Commercial

Tim Duncan's Review: provides a good overview and evaluation of the commercial suites

References

Berry, P.M., (1992) "The PCP: A Predictive Model for Satisfying Conflicting Objectives in Scheduling Problems", Artificial Intelligence in Engineering, Vol.7, pp227-242, Elsevier.
Borrett, J., Tsang, E.P.K. & Walsh, N.R., (1996) Adaptive constraint satisfaction: the quickest first principle, Proceedings, 12th European Conference on AI, Budapest, Hungary.
Burke, P. & Prosser, P., (1991) "A Distributed Asynchronous System for Predictive and Reactive Scheduling", Artificial Intelligence in Engineering, 6(3):106-124,: Computational Mechanics Publication
Ghedira, K. & Verfaille, G., (1992) "A Multi-Agent Model for the Resource Allocation Problem: a Reactive Approach", Proceedings ECAI-92, Vienna, Aug., pp 252-254.
Grant, S. & Smith, B. (1995) The Phase Transition Behaviour of Maintaining Arc Consistency, Research Report 95.25, School of Computer Studies, University of Leeds.
Hadavi, K., Hsu, W., Chen, T. & Lee, C., (1992) "An Architecture for Real-Time Distributed Scheduling", AI Magazine, Fall 1992, pp 47-57
Musliner & Boddy (1996)
Prosser, P., (1992) "Scheduling as a Constraint Satisfaction Problem: Theory and Practice", ECAI-92 Workshop on Scheduling of Production Processes, (ed. J. Dorn), Wiley, Vienna.
Sadeh, N., (1991) "Look-Ahead Techniques for Micro-Opportunistic Scheduling", Ph.D Thesis, School of Computer Science, CMU, Pittsburgh.
Swanson, K., Bresina, J., and Drummond, M. (1994) Just-In-Case Scheduling for Automatic Telescopes, Knowledge-Based Artificial Intelligence Systems in Aerospace and Industry
Sycara, K. & Miyashita, K., (1992) "Incremental Schedule Modification", Working Notes: Symposium on Computational Considerations in Supporting Incremental Modification and Reuse, AAAI Spring Symposium Series, Stanford University.
Zweben, M., Davis, E., Daun, B. & Deal, M., (1992) "Scheduling and Rescheduling with Iterative Repair", Technical Report FIA-92-16, NASA Ames Research Centre, Artificial Intelligence Research Branch.
Zweben, M., Davis, E., Daun, B., Drascher, E., Deale, M. & Eskey, M., (1992) "Learning to Improve Constraint-Based Scheduling", Artificial Intelligence, Vol.58, Nos.1-3, pp271-296, December.