=Paper=
{{Paper
|id=Vol-2068/exss4
|storemode=property
|title=Explaining Complex Scheduling Decisions
|pdfUrl=https://ceur-ws.org/Vol-2068/exss4.pdf
|volume=Vol-2068
|authors=Jeremy Ludwig,Annaka Kalton,Richard Stottler
|dblpUrl=https://dblp.org/rec/conf/iui/LudwigKS18
}}
==Explaining Complex Scheduling Decisions==
https://ceur-ws.org/Vol-2068/exss4.pdf
Explaining Complex Scheduling Decisions
Jeremy Ludwig, Annaka Kalton, & Richard Stottler
Stottler Henke Associates, Inc.
San Mateo, CA, USA
ludwig; kalton; stottler @ stottlerhenke.com
ABSTRACT • Temporal: Tasks must be scheduled between the
The work presented in this paper describes the explanation project start and end dates. Each task has a duration
facility of an intelligent scheduling software framework that and an optional start date and optional end date. For
has been customized and deployed in a variety of domains. example, InstallCockpitDoor must be completed by
The customizability of the framework allows the software to 5:00 PM on March 1, 2018.
develop a valid schedule that reflects each domain’s specific • Ordering: Tasks can optionally be assigned to follow
preferences and constraints. In all domains, the software either immediately after/before another task or
quickly solves a complex scheduling problem (generally in sometime after/before another task; optionally with a
less than five minutes) and produces a schedule that is specific lag time in between. For example,
significantly better than those reached by previous methods. PaintCockpitDoor must happen sometime before
The primary contribution of this paper is to describe the InstallCockpitDoor with a lag of at least 48 hours in
explanation facility used by schedulers across a variety of between to allow the paint to cure.
real-world domains to answer the ever-present question: why • Resource: Each task can require that resources be
was a task was scheduled here and not there? The available for the task to be scheduled. A task might
transparency to see why inspires greater confidence in the require a specific resource (e.g. CockpitArea) or might
results and facilitates understanding of how constraints affect select from a pool of resources (e.g. three mechanics
the schedule, enabling the user to further improve the from the Mechanics pool).
schedule by assessing specific constraints. This paper also • Calendar: Tasks can only be scheduled during working
outlines future work that will improve upon the existing shifts; tasks cannot be scheduled on holidays. Resources
explanations. may also have calendar constraints as well. For example,
Author Keywords individual Mechanics work one of two shifts M-F while
scheduling framework; heuristics; explanations the CockpitArea is generally available at any time.
ACM Classification Keywords The framework distills the various operations involved in
• Human-centered computing~Interactive systems and creating a schedule that respects all of these constraints into
tools. reconfigurable modules that can be exchanged, substituted,
INTRODUCTION
adapted, and extended. This framework acts as a foundation
Scheduling, at its most basic, is the process of assigning tasks for creating scheduling tools that respect domain-specific
to resources over time, with the goal of optimizing the result constraints and use heuristics tuned to each domain to ensure
according to one or more objectives [5]. Scheduling is a high-quality schedule.
heavily used in aerospace, manufacturing, defense, and The remainder of this paper will describe related work,
service industries to minimize the time and cost associated followed by an overview of the explanation facility. The
with the completion or production of large and complex explanation facility relies on the scheduling engine to
projects. generate explanations and the user interface to visualize
The Aurora scheduling framework is one example of a these explanations. The goal of the combined system is to
general-purpose scheduler that has been successfully help users understand the decisions that were made during
applied in a variety of domains, including all of those listed the process of creating large and complex schedules.
above [3,4,6]. Aurora combines graph analysis with Following this is a discussion of explanations in Aurora and
heuristic scheduling techniques to quickly produce an next steps for improving the explanation facility.
effective schedule based on a defined set of tasks and Related Work
constraints. Tasks are the actions that need to be completed, There is a body of prior work outside of Aurora towards
e.g. InstallCockpitDoor. Constraints define limits on when creating a general-purpose scheduling framework that forms
a task could be completed. While constraints vary across the basis of domain-specific scheduling tools. The OZONE
domains, they generally include: Scheduling Framework [7] is one example. [1] describes the
validation of the OZONE concept through its application to
a diverse set of real-world problems, such as transportation
logistics and resource-constrained project scheduling. [2]
© 2018. Copyright for the individual papers remains with the authors. presents a design for a general scheduling framework for
Copying permitted for private and academic purposes.
ExSS '18, March 11, Tokyo, Japan.
manufacturing. [5] presents an overview of several modern Initialization Phase
general-purpose scheduling systems such as the SAP First, Aurora applies the Preprocessor to the tasks to prepare
Production Planning and Detailed Scheduling System, for scheduling. Examples of preprocessor tasks are setting
ASPROVA Advanced Planning and Scheduling, Preactor the schedule direction for the tasks and marking resource
Planning and Scheduling Systems, and ORTEM Agile constrained tasks for special handling. Second, the
Manufacturing Suite. Each of these modern systems has a Prioritizer is applied to determine the order of the tasks in
distinct feature set while sharing some aspects in common the scheduling queue. The Prioritizer may be re-applied
with Aurora and each other. within the scheduling loop.
The primary contribution of this paper is to describe the
Scheduling Phase
explanation generation facility in the Aurora framework,
how the resulting explanations are used by schedulers to First, the Scheduler calls constraint propagation on the
understand the decisions that drive complex schedules, and highest priority schedulable element to be sure that all its
to outline future work that would improve the utility of the requirements and restrictions are up to date. Second, the
explanations. Scheduler assigns the task to a time window and resources
such that all constraints are satisfied. It also returns a list of
EXPLANATION FACILITY
the conflicts resulting from the given assignment, if any.
The scheduling framework consists of two primary Third, the Scheduler calls constraint propagation on the task
components: the engine and the user interface. The (again) to update all the neighbors so that they are
scheduling engine is responsible for creating an explanation appropriately restricted by the newly scheduled element.
for each task, describing why the task was placed in its This process may result in additional conflicts; if so, these
particular position (which includes both time and resources)
are added to the list of conflicts from scheduling. Fourth, the
as the schedule is created. The user interface is responsible
Scheduler asks the Conflict Manager to resolve those
for presenting the explanation to the user (Figure 1) and conflicts. This process is repeated until every task in the
helping them understand why a task was scheduled here and scheduling queue is scheduled.
not there. This information helps direct the user’s attention
to the driving constraints and supports carrying out what-if Finalization Phase
analysis on how changing these specific constraints might
improve the schedule. When the queue is empty, Aurora goes through a final
conflict management step, this time at the global level.
For example, perhaps the user would like to see the Aurora calls the Postprocessor on the schedule, so that any
InstallCockpitDoor task happen earlier in the schedule to additional analysis may be done before Aurora returns the
avoid conflicting with the InstallCockpit task. The schedule results.
explanation shows that PaintCockpitDoor is driving the date
Generating Explanations
of InstallCockpit. Digging deeper, the driver for
Explanations are generated for each task and are constructed
PaintCockpitDoor is the delivery date of the door itself. The
from decisions made in each of the scheduling phases. The
scheduler can perform a what-if analysis by changing the
cumulative decisions work together to narrow the window in
availability date of the part and rescheduling. If this has the
which the task can be scheduled by adjusting its early start
desired effect, the next step is talking to the supplier to see if
and late end dates. The scheduling order determines when a
the date can be moved up.
task is given a chance to schedule relative to the other tasks,
Generation where it will be placed in the first available time slot in which
Explanations are created by the scheduling engine as it works all of its constraints can be satisfied. An explanation is
to generate a schedule. In order to understand the composed of multiple text descriptions that describe the
explanation, it is helpful to provide a brief overview of the decisions made and why they were made leading up to the
scheduling engine first, followed by how explanations are assignment of a task to a particular time and set of resources.
created in this process.
In the initialization phase, The Prioritizer assigns the
Scheduling Engine schedule order as shown in Figure 1, which is an integral part
The scheduling engine runs through three distinct phases: in understanding why scheduling decisions are made. Initial
initialization, scheduling, and finalization. constraints are also applied to each task by the Preprocessor
Figure 1. A scheduling explanation for a task in Aurora. Task and resource names are obfuscated to protect client data.
Figure 2. A plot of tasks scheduled before the explained task. The x-axis is time; the y-axis are resource constraints. The plot
starts on 01/06/2018, which is the first time the task could be scheduled due to constraint propagation as shown in Figure 1.
LWUA is the constraining resource, pushing out the start of the task to 01/16/2018. A mechanic from the pool of MECH is also
required, but as seen in the image this is not a constraining resource.
in this phase. For example, one constraint is that a task’s late this particular task, along with its schedule order. Where
end date (the date it must be finished by) can be no later than other tasks are referenced, hyperlinks provide browsing
the project end date. This constraint narrows the schedule support so that the user may follow the cascade of inter-
window and is recorded in the explanation. Preprocessor related explanations through the dependent series.
results are seen in lines 1 and 2 in the explanation field of
The explanations displayed in the UI are a filtered view of
Figure 1.
all of the individual decisions contained in the explanation.
The scheduling phase adds to the explanation in two ways. As generated, the explanation would be a complex tree of
First, constraint propagation is applied before any tasks are decisions – not a simple list. The explanation presented to the
scheduled and again after each task is scheduled. The user only includes the most specific path through the tree
temporal, calendar, and resource constraints (and their leading up to the task being scheduled. This represents the
interactions) will further narrow the early start dates and/or decisions that led to the final schedule but does not show all
late end dates of each task. Any time the scheduling window of the other possibilities that were examined.
is narrowed an explanation is recorded, as seen in lines 3-5
Additionally, there are cases where the same constraint
in the explanation field. Second, when a task reaches the
would be responsible for a number of changes. For example,
front of the scheduling queue it will be placed at the first
TaskP precedes TaskQ. Every time the early start of TaskP
available time that meets all of the constraints. If this time
gets changed, TaskQ gets changed as well. In this case, only
does not match the early start date, then the constraints
the most recent change to TaskQ caused by TaskP is
responsible for the delay are recorded in the explanation.
presented to the user.
Lines 6 and 7 in the explanation field were generated when
the task was actually scheduled. The collapsing of constraints produces an unintuitive result
(although still very useful) for scheduled tasks with resource
Finally, in the finalization phase the Postprocessor may
constraints. The primary issue is cascading unavailability of
move scheduled tasks and record the reason in the
resources. For example, first ZoneA is unavailable. Then a
explanation. This supports domain-specific finalization of
Crane is unavailable. Finally, Labor is unavailable. In this
schedules. The example in Figure 1 does not include any
case, only Labor will be shown in the explanation, as it is the
explanation information from this phase.
most recent cause of delay. This can be confusing to the user
Visualization if they only look at the Labor requirement because it may
The user interface is responsible for presenting the appear that Labor had availability earlier; the user misses the
explanation to the user in an understandable form. As shown fact that either ZoneA or the Crane was also needed but not
in Figure 1, the scheduling explanation is part of the available. The alternative of adding a line for each of the
Scheduling Results display. The explanation portion of the possible resources responsible for the schedule delay over
result lists the constraints that have driven the scheduling of
time generally results in too much information and relatively improvement. First, as pointed out constraint collapsing for
little utility for the user. scheduled tasks with resource constraints produces
confusing results, such as showing that Labor is causing the
Instead, the schedule order and explanation are paired with
delay because it was the most recent unavailable resource. It
graphic visualization to help the user understand the
would be more informative and more accurate to report the
scheduling decisions. The graph shown in Figure 2 provides
multiple resource delays in a way that doesn’t overwhelm the
the context in which the scheduling decision is made. The x-
user. For example, collapsing all the resource delays into a
axis is time and the y-axis represents the possible resources
single line where each resource or set of resources is included
that would be needed by this task. The graph starts on the
only once might provide a better at-a-glance summary.
first available date that the task could be scheduled. Only the
Second, it would be a significant improvement to have a one-
tasks that were scheduled before this task (based on schedule
click button that produces a graph like the one in Figure 2 for
order) are plotted on the resources they use and the time they
a given scheduling explanation. Currently it is tedious to
use them. This graph allows the user to visually confirm the
configure such a graph manually; it also requires significant
task’s final scheduling decision given the preceding
knowledge on how to use the Aurora filtering mechanisms.
decisions.
Third, it would be helpful to improve the visual
DISCUSSION representation of the explanation. A small improvement
Much of this paper so far has focused on what an explanation would be to number the lines and use icons and colors to note
in the Aurora scheduling framework is and how users which part of the scheduling process generated each
interact with it. In order to discuss the utility of explanations, explanation line (Preprocessor, Constraint Propagation,
we need to examine why a scheduler wants an explanation to Forward/Backward Scheduler, PostProcessor). A larger
begin with. Generally, the users of Aurora are intimately improvement might visualize the explanation list as a
familiar with the schedule they are creating. Whether it is horizontal timeline, with markers for the changes that adjust
running a machine shop, assembling an airplane, or the early start and late end dates. We plan to address all three
managing a pharmaceutical packing line, a user is attuned to changes as part of future work.
their schedule and have an intuitive sense of what the
REFERENCES
schedule should look like. When all is working correctly,
1. Marcel Antoine Becker. 1998. Reconfigurable
explanations are rarely examined by the user.
Architectures for Mixed-initiative Planning and
However, when the schedule does not look ‘as expected’ is Scheduling. Carnegie Mellon University, Pittsburgh, PA,
exactly when explanations are brought into play. The USA.
explanation facility fills one of two roles in this case. If it 2. Jose M. Framinan and Rubén Ruiz. 2010. Architecture of
demonstrates that the correct scheduling decision was made, manufacturing scheduling systems: Literature review and
it builds trust in the overall system. On the other hand, if it an integrated proposal. European Journal of Operational
demonstrates that the right decision was not made, the Research 205, 2: 237–246.
explanation facility usually points to problems in the domain https://doi.org/10.1016/j.ejor.2009.09.026
specific Prioritizer or, more often, reveals an error in the 3. Annaka Kalton. 2006. Applying an Intelligent
scheduling model itself (tasks, resources, and constraints). Reconfigurable Scheduling System to Large-Scale
For both of these reasons, we have found that scheduling Production Scheduling. In International Conference on
explanations are an invaluable part of the Aurora framework. Automated Planning & Scheduling (ICAPS) 2006.
4. J. Ludwig, R. Richards, A. Kalton, and D. Stottler. 2017.
Additionally, the explanation provides another perspective
Applying a heuristic-based scheduling framework in
into the schedule, facilitating understanding. For example, if
manufacturing, service, and communication domains. In
many tasks of interest have an explanation that shows the 2017 IEEE International Conference on Systems, Man,
same resource causing the delay, the user would review the and Cybernetics (SMC), 1–4.
histogram for that resource. At this point, the user would https://doi.org/10.1109/SMC.2017.8122568
discover that while the resource is never overloaded 5. Michael L. Pinedo. 2016. Scheduling. Springer
according to the schedule, based on the user’s experience it International Publishing, Cham.
is likely that during execution there will be times when that https://doi.org/10.1007/978-3-319-26580-3
resource will be not as available as modeled (due to 6. Robert Richards. 2010. Critical Chain: Short-Duration
unplanned maintenance or PTO). The user then might run Tasks & Intelligent Scheduling in e.g., Medical,
some scenarios to determine the effect of higher than normal Manufacturing & Maintenance. In 2010 Continuous
absences or downtime on this critical resource. With the
Process Improvement (CPI) Symposium.
results of these scenarios, changes to the scheduling model
7. S.F. Smith, O. Lassila, and M. Becker. 1996.
or resource pool may be made. Configurable, Mixed-Initiative Systems for Planning and
FUTURE WORK Scheduling. In Advanced Planning Technology, A. Tate
While the current explanation facility has demonstrated its (ed.). AAAI Press, Menlo Park, CA.
utility for numerous deployments, there is still room for