AMC Barrel Home, OZONE/DITOPS Home, ICLL

1. Background

DITOPS is an advanced system for complex transportation and logistics planning and scheduling applications, developed by Carnegie Mellon University (CMU) under sponsorship of the DOD Advanced Research Projects Agency (DARPA). It utilizes novel constraint-based representation and search techniques to provide capabilities

• for incorporating all constraints and rules that must be accounted for in a given application domain,
• for rapidly generating large-scale schedules that heuristically optimize specified objectives,
• for flexible "what-if" analysis of alternative options, and further user-directed improvement of schedules, and
• for localized, minimally disruptive revision of schedules in response to new or changed requirements

These planning and scheduling capabilities are coupled with a sophisticated, graphical user interface that enables visualization of plans and schedules from resource-oriented, mission-oriented and geographical (map-based) perspectives, flexible editing of problem constraints and parameters as well as planning and scheduling decisions, and selective control over the automated scheduling process.

2. Architecture

DITOPS is built using an underlying scheduling framework called OZONE (or O³ which stands for Object-Oriented OPIS, an earlier scheduling system architecture developed at CMU; DITOPS actually stands for Distributed Transportation Scheduling in OPIS). The OZONE "application building framework" is designed to promote rapid configuration of planning and scheduling systems that incorporate the specific constraints, rules, and characteristics of a given application environment. At its core is a customizable, constraint-based modeling framework and search architecture, based around 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 state of the schedule, 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.

The Ozone framework is implemented in Commonlisp (scheduler component) and Java (user interface component) using object-oriented representation and programming techniques. It includes an extensive class library for modeling different types of domain activities, resources, demands and constraints, as well as other scheduling system and UI components. Protocols are provided for extending and customizing basic concepts into more specialized ones that match the characteristics of a given application, and for combining concepts from the library. The OZONE class library and architectural template provide a powerful basis for constructing customized, high performance planning and scheduling systems.

3. Application Status

The DITOPS scheduler was originally developed and demonstrated in the context of strategic deployment planning. In this domain, on full-scale "TPFDD" scheduling problems, DITOPS was shown to produce better schedules than current USTranscom transportation scheduling tools in a fraction of the time taken by these tools while also enforcing additional types of transportation constraints. DITOPS was subsequently adapted and applied to the problem of reactive aero-medical evacuation re-planning, where capabilities for interleaving itinerary planning and resource assignment in the movement of patients to required medical facilities were demonstrated. Starting in 1997, with joint funding from DARPA and AMC, work was initiated toward extending and customizing the DITOPS/OZONE technology for transition into CAMPS (Consolidated Air Mobility Planning System), the future operational system for the TACC at AMC. This has led to development of BARREL ALLOCATOR, a tool for integrated planning and tasking of airlift and tanker missions. This scheduler is was delivered to AMC in October, 1998 for initial user evaluation within the TACC, and current plans call for insertion into actual operations in 4^th Quarter, 1999. The current technical capabilities of BARREL ALLOCATOR are summarized below.

4. Current Capabilities

The BARREL ALLOCATOR provides a range of mission planning and scheduling capabilities:

4.1 Generation of airlift mission schedules

In basic operation, the scheduler accepts a set of planned airlift missions as input, and establishes time windows and wing assignments for each. An input airlift mission (minimally) specifies:

• a cargo onload and offload location (expressed as ICAOs),
• an itinerary, or set of mission legs for transit from onload to offload location (and optionally including positioning/de-positioning legs),
• an "available to load time" (ALD) at the onload site and "earliest /latest arrival time" (EAD/LAD) at the offload site,
• and a preferred airframe (MDS) type and quantity (optionally the input can specifiy a cargo type and amount might be provided — e.g., oversize, 10 stons — and used to determine viable MDS alternatives)

The scheduler produces an assignment of (notional) aircraft from specific wings to each mission (creating and inserting positioning/de-positioning flights as necessary) and an assignment of flight times to each mission leg.

Currently, the following constraints are taken into account and enforced in constructing a schedule for all current missions:

• Wing capacity constraints - Assignment of missions to wings does not exceed the number of aircraft available at each wing, taking into account aircraft that have been "fenced" for local wing use and percentages expected to be in maintenance.
• Mission time requirements - Missions must be scheduled within time windows designated by ALD, EAD and LAD constraints
• Aircraft onload, offload and minimum time-on-ground constraints (each specified as a function of MDS type). More generally, it is possible to specify a range of different flight preparation activities and time constraints.
• Flight duration constraints — currently computed using great circle route
• Aircraft range constraints — which are enforced when determining specific wing assignments (and hence when creating positioning/de-positioning flights)
• Crew duty day constraints — Depending on designated crew type — basic or augmented — crew rest is inserted at appropriate intermediate points of the mission to enforce crew duty day.
• Airport maximum-on-ground (MOG) constraints — limiting the number of aircraft that can be simultaneously on the ground at a given port.

The mission scheduling procedure is quite efficient —a 2 week interval of missions recently extracted from the current ADANs data base at AMC (approximately 1000 missions, 5000 flights) is scheduled from scratch in 45 seconds on a Sun Ultra-Sparc (roughly equivalent to a 300Mhz PC). In a more typical mode of operation, however, the problem is one of integrating sets of newly planned missions into an existing current global schedule (which is typically much faster). In this mode, the scheduler will attempt to assign aircraft and schedule new missions without disrupting the current set of assignments. Any mission that cannot be integrated into the schedule in this way (which implies that there is not enough lift capacity to accomplish the mission without changing existing resource assignments) is flagged as "unschedulable" (requiring subsequent user attention — see below). Alternatively, the scheduler can be directed to integrate new missions into the current schedule in "priority order", in which case the scheduler may reassign or pre-empt lower priority missions if necessary to get newly received missions into the schedule. This range of scheduling modes provides a continuum of scheduling actions that are progressively more disruptive in the changes that can be made to the current schedule.

4.2 Generation/Assignment of tanker missions

In addition to generating wing/aircraft assignments and mission schedules, capabilities are also provided for generating and assigning tanker missions to airlift missions that require arial refueling support. A set of refueling events is accepted as input, and tanker assignments can be generated either interactively or automatically. In automatic mode, the scheduler first attempts to link tanker missions that are already included in the schedule (e.g., training missions); tanker wing assignments are determined and tanker missions are created for any remaining unsupported airlift missions.

In interactive mode, a map-based display (similar to the display in Figure 3 below) is used to indicate candidate refueling tracks that are already covered by tanker missions in the temporal interval required by a given airlift mission. The user can select one of these highlighted refueling tracks (potentially changing the originally planned refueling location) or select the current track (which will result in creation of a new tanker mission if one is not already in the schedule). In the case of the selection of a pre-existing tanker mission, the system will also present opportunities to support multiple arial refueling events with the same tanker mission (provided that fuel requirements and tanker fuel capacity constraints are satisfied).

4.3 Visualization and Analysis of Schedules

The automated, semi-automated and interactive scheduling capabilities described above are embedded in a Java-based, graphical user interface that provides powerful capabilities for visualizing and analyzing schedules. Three basic perspectives are defined for viewing the current schedule:

• Mission window — A mission-oriented display is provided by the mission window, shown in Figure 1. This display is organized as a configurable "Gantt table", with each row containing information about a particular airlift or tanker mission. Columns on the left indicate various properties of the mission (e.g., its POE, POD, name, mission-type, priority, etc.) and columns of displayed information can be added or deleted dynamically according to user needs and preferences. The set of missions displayed can be sorted by clicking on any of the column headings (e.g., by descending priority, by mission type, by mission name, etc.). On the right of the table is a graphical representation of each mission’s current schedule. Referring to a single row (mission) in Figure 1, the blue rectangle represents the required time interval (ALD to LAD) and the black I-beam represents the scheduled interval (A grey interval designates that the mission does not yet have an assigned wing/aircraft — i.e., its not yet scheduled). One can drill down into a given mission to see the scheduled times of individual mission legs and crew rest periods (colored in tan in the mission window in Figure 1). The red links between missions in Figure 1 indicate airlift and tanker missions that have been linked. Within the mission window a number of "sheets" are defined that isolate specific sets of missions (e.g., all scheduled missions, all unscheduled missions, all unschedulable missions, all unrefueled missions, etc.), and a filtering mechanism provides a means for selectively isolating more arbitrary sets of missions on a separate sheet.
• Resource Commitment matrix — A second resource-oriented view of the schedule is provided by a resource commitment matrix. Figure 2 shows an aircraft commitment matrix for 4 CONUS C141 Wings. This display shows committed aircraft usage levels at an aggregate level for each wing, designating the percentage of the fleet expected to be in maintenance (in brown), the amount of "fenced" aircraft capacity retained locally for the wing’s use (green), and the amount of aircraft capacity currently allocated by AMC to support missions. The black line shown in the capacity profile for each wing designates the current "fence line" and gives a quick graphical basis for recognizing those intervals where wing aircraft capacity has been over-allocated (see discussion of option analysis below). By "boxing" a particular interval, the user can get a precise accounting of the types and numbers of missions currently being supported over that interval. Drill down on this display (not shown in the figure) would indicate the current schedules for individual (notional) aircraft. Similar resource displays are available for viewing current availability at various airports (as defined by MOG constraints). It is also possible to use the "boxing" selection capabilitty to reduce the capacity of a particular resource over a particular interval (e.g., specify that a particular aircraft is unavailable for some period).
• Map-Based Display — A third map-based display is provided through use of BBN’s OpenMap tool. This display is illustrated in Figure 3 in the context of interactive mission merging (discussed below). This display provides the capability to geographically visualize the itinerary of a give set of missions. It also provides the basic interface for interactively specifying airlift mission merging and tanker generation actions.

These three visual perspectives are highly integrated and managed in a coordinated fashion. Selections in the mission window can be used to create specific resource or map-based displays, and changes made to the schedule from any display are immediately reflected in all displays.

4.4 What-If Analysis of Options and Interactive Revision of Schedules

As mentioned earlier during discussion of airlift mission schedule generation, the scheduler, in default mode, will classify as "unschedulable", any mission that cannot be integrated into the current schedule without some change to previous assignments. In such cases, it is not possible to satisfy mission time constraints with existing available lift capacity. To support resolution of such situations, BARREL ALLOCATOR gives the user the ability to analyze and compare various constraint relaxation options. Specifically, for any given "unschedulable" mission (or set of unschedulable missions), the user can choose to:

• Allow bumping of lower priority missions — In this case the mission is rescheduled, considering possibilities to pre-empt lower priority missions already in the schedule. Any pre-empted missions are then rescheduled in succession and they may, in turn, pre-empt missions of lower priority still. At quiescence, any lower priority missions that cannot be fit back into the schedule are placed on the unschedulable list.
• Over-allocate — The user may alternatively choose to over-allocate a given wing. This happens with a fair amount of frequency in the case of barrel scheduling; it typically reflects extra knowledge that the barrel master may have about wing assets or agreement on the part of the wing to use fenced aircraft.
• Delay the mission — The user may consider the option of delaying the current mission until necessary resources are available. If delay seems like a potentially viable alternative then this information can be suggested to the mission planner
• Use alternatve MDS — Similarly, it might be possible to accommodate the mission if an alternative airframe can be utilized.

Any of these options can be invoked by the user in "what-if" mode; a general "undo" capability allows the retraction of any sequence of scheduling actions that have been issued by the user, and thus provide a basis for exploring alternatives. Alternatively, the user can ask the system to generate and and compare all options.

4.5 Interactive Mission Merging

A final interactive capability provided to the user to support more efficient usage of available aircraft is mission merging. Whereas missions are, by default, planned as round trips from a particular home base, mission merging attempts to exploit non-cargo-carrying positioning/de-positioning flights to support missions (such as retro-grade missions) that are flowing cargo in opposite directions. Using the map-based interface, a mission (perhaps currently unschedulable) for which merge candidates are sought is displayed, and a find merge candidates query is formulated by specifying 3 parameters:

• Maximum layover time — the maximum time delay that can be tolerated between offload (end) of one mission and onload (beginning) of second mission
• Maximum distance — the maximum distance that can be tolerated between location of first offload and second onload
• Percentage decrease in overall flying time — by reducing two missions into one (as opposed to flying both original round trips)

The interactive mission merging function is illustrated here.