The DITOPS Scheduling System

Introduction
DITOPS is an advanced tool for generation, analysis and revision of crisis-action logistics schedules. It was developed to address the shortcomings of existing transportation scheduling tools: these tools typically provide rather inflexible solution generators; the user is given no guidance in changing input constraints to achieve desired results, and has no control over how the schedule actually changes in response to revised inputs. As opposed to this, the DITOPS reactive scheduler is a mixed initiative decision-support tool similar in spirit to spreadsheet programs: sets of scheduling decisions and solution constraints are interactively manipulated by the user at (typically aggregate) levels consistent with user-task models. At each step, the system applies appropriate (re)scheduling procedures to impose the changes specified by the user, and provides localized consequences of each change. In other words, the user sees "the big picture" and can operate in terms of understandable and manageable real-world concepts, while the system "manages the details", takes care of the multitude of small and uninteresting albeit important scheduling decisions. System look-ahead analysis and scheduling techniques further provide functionality that transcends the spreadsheet decision-support analogy, supporting the user in identifying principal causes of observed solution deficiencies (e.g., resource bottlenecks), in analyzing various decision-making options (e.g., apportionment of additional resources), and in assessing solution sensitivity to various executional circumstances. The incremental nature of (re)scheduling in DITOPS makes it ideal for reactive scheduling. The system is capable of repairing a schedule as a response to unexpected events (such as resource breakdowns), minimizing disruption to other parts of the schedule.

The mixed initiative "spreadsheet" model of operation also makes DITOPS well suited to "what if" -experimentation. It should be observed that scheduling is often much more than just placing activities on a time-line; it is a process of "getting the constraints right", e.g. trying to assess resource requirements ("how many ships do I need to complete the mission in time?"). Traditional simulation approaches are not suited to this type of problem solving (it would effectively require one to "run the simulation backwards"). DITOPS, however, is capable of relaxing constraints in several dimensions, not just temporal ones, allowing it to be used efficiently when scheduling is tightly coupled with planning. This is often a more natural approach than having to artificially decouple the planning and scheduling tasks just because existing tools don't allow their easy integration.

Principle of Operation
The DITOPS system incorporates concepts of constraint-directed scheduling developed within the OPIS manufacturing scheduling system, together with extensions to address the specific characteristics of transportation scheduling problems. At the core of the system is an incremental, reactive framework for generating and revising schedules, integrating three principal components:
  • constraint propagation techniques, for incrementally updating solution constraints and recognizing inconsistencies as changes (extensions, additions) are made to the schedule,
  • look-ahead analysis techniques, which estimate the critical tradeoffs and opportunities for solution revision (or extension) implied by the current solution state, and
  • a set of heuristic scheduling procedures for carrying out specific schedule revisions (or extensions), each of which provides differential optimization and/or conflict resolution capabilities.
Scheduling proceeds opportunistically; decisions as to which procedure to apply and what decisions to make or revise on each cycle are made dynamically, based on the results of look-ahead constraint analyses.

The alternative scheduling procedures are specifically designed to provide differential optimization and conflict resolution capabilities. Local search methods exist for both "resource" and "movement" centered scheduling, respectively providing capabilities for manipulating (i.e., revising or extending) the schedules associated with particular sets of resources (e.g., a cargo ship fleet) or particular sets of temporally related movements (e.g., the movements associated with a particular force module). By virtue of search orientation, each of these methods emphasizes specific optimization biases; resource scheduling promotes efficient use of available transport capacity while attempting to minimize the tardiness of scheduled movements. Movement scheduling, alternatively, promotes enforcement of arrival constraints and efficient synchronization of dependent movements, while attempting to minimize asset capacity requirements. Both of these methods share a common search infra-structure that allows incorporation of additional allocation preferences. A number of more specialized revision procedures are also defined, providing additional capabilities to shift the scheduled interval of "trips", re-allocated batches associated with particular transportation assets, and do load balancing to exploit increases in port capacity.

Implementation
DITOPS is built using an underlying scheduling framework called OZONE (aka O3 aka Object-Oriented Opis). OZONE is implemented using object-oriented representation and programming techniques, providing an extensible modeling and scheduling framework that enables straightforward system customization to account for the principal constraints and objectives of different scheduling domains. The scheduler operates with respect to hierarchical models of the processes and resources of the problem domain. Because of a layered and extensible nature of the OZONE modeling and scheduling framework, new application development is not limited to transportation problems: the system can also be adapted to, say, manufacturing scheduling problems. In practical terms the framework is a class library that contains classes for the basic scheduling concepts and their specializations to some specific areas (e.g. transportation). Protocols are provided for combining concepts from the library, and extending the existing basic concepts into more specialized ones.

Due to the configurability of DITOPS/OZONE it is easy to integrate it or parts of its functionality with other planning systems. In an early technology integration experiment (TIE) with SRI, DITOPS was used to perform resource capacity analysis for higher level course of action planning by integrating it with SRI's SOCAP planner running on the Common Prototyping Environment (CPE) developed by BBN. Some DITOPS functionality was also embedded into BBN's TARGET mission planning system to perform feasibility checking and conflict diagnosis of course of action plans. More recently the OZONE class library has been applied to develop a prototype system for aero-medical evacutation (re)planning.

The current version of DITOPS runs on a Sun Sparcstation. A more portable version, aimed additionally at PC and Mac platforms and utilizing a Java-based interface is nearing completion. Interaction with the user takes place through a direct-manipulation user-interface which is centered around Gantt-diagrams of resource capacity usage (see Figure 1). In comparison to conventionally used simulation approaches to producing schedules for large-scale deployment problems, we have demonstrated that DITOPS is able to efficiently generate higher quality schedules while simultaneously satisfying a wider range of deployment constraints. For example, DITOPS is currently capable of generating a detailed 3000-movement TPFDD (Time-Phased Force Deployment Data) schedule in about 6 minutes (on a Sparcstation 10).

Current efforts are extending and adapting the OZONE/DITOPS framework for application in two different scheduling domains:

  • "Barrel scheduling" at the Air Mobility Command (AMC) - In collaboration with Kestrel Institute, Rome Laboratory and Logicon Corp., we are developing a scheduler for short-term, day-to-day airlift and tanker scheduling for integration into AMC's overall CAMPS system for inegrated airlift and tanker management.

  • Joint air operations planning - We are also developing a system for mixed-initiative, continuous management of air campaign plans and schedules.

Demonstrations

Marcel Becker,
Last modified: Fri Mar 10 18:13:41 EST 2000