ijcai-99 Home Page

C2 - Knowledge-based Scheduling

Sunday, PM

Steve Chien & Stephen Smith

Increasingly, AI and knowledge-based techniques are providing a practical basis for effective solutions to complex scheduling problems. This tutorial will cover the principal concepts and techniques that underlie AI-based approaches to automated scheduling.

We will start by covering basic scheduling concepts such as representation of scheduling knowledge and constraints, search, constraint propagation, conflict resolution, bottleneck analysis, search control heuristics, and basic constructive and iterative approaches to schedule generation.

Next, more advanced scheduling topics will be covered, including scheduling under uncertainty, reactive scheduling, distributed scheduling, mixed-initiative scheduling, machine learning approaches to scheduling, and evolutionary computation approaches. We will conclude with a characterization of the current state of research and practice, and a discussion of the prospects and open issues in the field. The tutorial will be motivated with experiences drawn from real-world scheduling systems which have been or are currently being deployed, and concepts will be illustrated using examples drawn from these systems.

Prerequisite knowledge:
Knowledge of basic concepts from artificial intelligence will be presumed: search, expert systems, logic-like representations. Familiarity with some planning and scheduling systems, constraint propagation, and basic search strategies would be helpful but not essential.

Dr. Steve Chien is Technical Group Supervisor of the Artificial Intelligence Group at the Jet Propulsion Laboratory, California Institute of Technology, where he leads efforts in automated planning and scheduling. His current projects include basic research and deployment of planning systems for automated science analysis, spacecraft mission planning, spacecraft design, maintenance of space transportation systems, and Deep Space Network Antenna operations.

Dr. Chien holds B.S., M.S., and Ph.D. in Computer Science, all from the University of Illinois. Dr. Chien is also an Adjunct Assistant Professor with the Department of Computer Science of the University of Southern California. He is a 1995 recipient of the Lew Allen Award for Excellence, the highest honor JPL awards to researchers in the early years of their professional careers.

Dr. Stephen F. Smith is a Senior Research Scientist in the Robotics Institute at Carnegie Mellon University where he is Director of the Intelligent Coordination and Logistics Laboratory. Since joining the faculty at CMU/RI in 1982, Dr. Smith's research has focused on frameworks and techniques for flexible planning, scheduling and control in practical domains. Dr. Smith has directed the development of several innovative constraint-based scheduling systems, which have been fielded in numerous application domains spanning semiconductor manufacturing, military airlift and tanker mission management, and communications antenna scheduling. His current research interests include distributed, mixed-initiative and reactive planning and scheduling, reconfigurable and self-organizing scheduling system architectures, and agent-based modeling and analysis of supply chain dynamics.

Webmaster: Sven Olofsson, sveno@dsv.su.se
Last modified: Mar 13, 1999