Aurora is a general-purpose scheduling framework that has been successfully applied in a wide range of settings, including aerospace, manufacturing, defense, and service industries. Aurora derives its success in such sectors from its ability to minimize the time and cost associated with large complex projects. The customizability of the framework allows the software to develop a valid schedule that reflects each domain’s specific preferences and constraints. In all domains, the software quickly solves a complex scheduling problem (generally in less than two minutes) and produces a schedule that is significantly better than those reached by previous methods.
The following poster from 2018 provides an overview of some of Aurora’s complex scheduling decision capabilities. Text from the poster is provided below with references to further information. Note that Aurora’s capabilities have continued to be enhanced since 2018 and further improvements are an ongoing process.
Scheduling Model
Let’s take a look at a scheduling model so we can establish a better understanding of what kind of information Aurora typically works with.
To begin, there are typically a set of tasks that need to be completed and constraints that need to be considered. It is important to take note of the fact that some constraints interfere with and/or overlap one another, which adds another layer of complexity.
Aurora combines graph analysis with heuristic scheduling techniques to quickly produce an effective schedule based on this defined set of tasks and constraints.
Tasks: Jobs that need to be completed, e.g., InstallCockpitDoor.
Constraints: Limitations on when a task can be completed. E.g.
While constraints vary across domains, they generally include:
- Temporal: InstallCockpitDoor must be completed by 5:00 PM on June 1, 2025.
- Tasks must be scheduled between the project start and end dates. Each task has a duration and an optional start date and optional end date.
- Ordering: PaintCockpitDoor must happen before InstallCockpitDoor with a lag of at least 48 hours in between to allow the paint to cure.
- Tasks can optionally be assigned to follow either immediately after/before another task or sometime after/before another task; optionally with a specific lag time in between.
- Resource: InstallCockpitDoor requires a specific resource (CockpitArea), three mechanics from the Mechanics resource set.
- Each task can require that resources be available for the task to be scheduled.
- Calendar: Individual Mechanics work one of two shifts M-F, while the CockpitArea is generally available at any time.
- Tasks can only be scheduled during working shifts; tasks cannot be scheduled on holidays. Resources may also have calendar constraints as well.
The framework distills the various operations involved in creating a schedule that respects all of these constraints into reconfigurable modules that can be exchanged, substituted, adapted, and extended. This framework acts as a foundation for creating scheduling tools that respect domain-specific constraints and use heuristics tuned to each domain to ensure a high-quality schedule.
Scheduling Framework: Scheduling Engine and the User Interface
The scheduling framework consists of two primary components: the engine and the user interface. The scheduling engine is responsible for creating an explanation for each task, describing why the task was placed in its particular position (which includes both time and resources) as the schedule is created. The user interface is responsible for presenting the explanation to the user and helping them understand why a task was scheduled here and not there. This information helps direct the user’s attention to the driving constraints and supports carrying out what-if analysis on how changing these specific constraints might improve the schedule.
In order to understand the explanation, it is helpful to provide a brief overview of the scheduling engine and the three distinct phases it goes through:
- Initialization Phase: First, Aurora applies the Preprocessor to the tasks to prepare for scheduling. Examples of preprocessor tasks are setting the schedule direction for the tasks and marking resource constrained tasks for special handling. Second, the Prioritizer is applied to determine the order of the tasks in the scheduling queue. The Prioritizer may be re-applied within the scheduling loop.
- Scheduling Phase: Then, the Scheduler calls constraint propagation on the highest priority schedulable element to be sure that all its requirements and restrictions are up to date. Second, the Scheduler assigns the task to a time window and resources such that all constraints are satisfied. It also returns a list of the conflicts resulting from the given assignment, if any. Third, the Scheduler calls constraint propagation on the task (again) to update all the neighbors so that they are appropriately restricted by the newly scheduled element. This process may result in additional conflicts; if so, these are added to the list of conflicts from scheduling. Fourth, the Scheduler asks the Conflict Manager to resolve those conflicts. This process is repeated until every task in the scheduling queue is scheduled.
- Finalization Phase: When the queue is empty, Aurora goes through a final conflict management step, this time at the global level. Aurora calls the Postprocessor on the schedule, so that any additional analysis may be done before Aurora returns the schedule results.
Example Results
With consideration to the various phases that the scheduling model goes through in order to render the most efficient schedule, Aurora provides the following:
Generating Explanations
The Aurora scheduling engine generates explanations for each of its decisions, which is especially helpful when trying to understand why certain tasks were scheduled in a particular way. Ultimately, schedulers across a variety of real-world domains often ask: why was a task scheduled here and not there? The transparency to see why inspires greater confidence in the results and facilitates understanding of how constraints affect the schedule, enabling the user to further improve the schedule by assessing specific constraints.
The scheduling order determines when a task is given a chance to schedule relative to the other tasks, where it will be placed in the first available time slot in which all of its constraints can be satisfied. An explanation is composed of multiple text descriptions that describe the decisions made and why they were made leading up to the assignment of a task to a particular time and set of resources.
In the initialization phase, the Prioritizer assigns the schedule order, which is an integral part in understanding why scheduling decisions are made. Initial constraints are also applied to each task by the Preprocessor in this phase. For example, one constraint is that a task’s late end date (the date it must be finished by) can be no later than the project end date. This constraint narrows the schedule window and is recorded in the explanation.
The scheduling phase adds to the explanation in two ways. First, constraint propagation is applied before any tasks are scheduled and again after each task is scheduled. The temporal, calendar, and resource constraints (and their interactions) will further narrow the early start dates and/or late end dates of each task. Any time the scheduling window is narrowed an explanation is recorded, as seen in lines 3-5 in the explanation field. Second, when a task reaches the front of the scheduling queue it will be placed at the first available time that meets all of the constraints. If this time does not match the early start date, then the constraints responsible for the delay are recorded in the explanation. Lines 6 and 7 in the explanation field were generated when the task was actually scheduled. Finally, in the finalization phase the Postprocessor may move scheduled tasks and record the reason in the explanation. This supports domain-specific finalization of schedules.
Further details are provided in the paper associated with this poster:
Would you like a FREE Demo? Contact Us
Please enter your contact details, company name and a short message below and we will answer your query as soon as possible.
Contact Us