Planning & Scheduling
ORION Planning and Scheduling
provides tools to permit a different and much more comprehensive approach to the planning
and scheduling of activities, a new level of interactivity with the plan, and a degree of
mechanisation of the plan unattainable with previous static methods.
Scheduling varies in difficulty from the simple,
where a glance at a planning board is sufficient to arrange the day’s work, to the
complex, where a set of dynamically interacting constraints controls how the various
events can be scheduled. Up to now the only tools on offer suited a simple static
application well, while leaving the more complex and dynamic tasks to human planners.
Complex scheduling requires the manipulation of
tentative information and structure - not only are we unsure when things will happen, we
are unsure IF they should happen, and if they don't happen, that will cause... The
information about tentative structure has up to now been kept in people's heads, because
there was no place for it in a rigidly mechanised plan where the existence of everything
is unquestioned. The Orion scheduling tools handle tentative structure simply and
efficiently, greatly increasing the scope and effectiveness of planning.
The system is well suited to graphical
interaction by planners, as all elements of the plan including its logic have a simple
intuitive visual representation.
The Planning and Scheduling software
tools sit on top of the ORION Active Structure system, providing a direct and general
representation of analytic and experiential knowledge. Planning and Scheduling is an
essential part of a knowledge handling tool, but all the other parts of knowledge handling
- dynamic representation, inferencing under uncertainty, representation of complex
non-analytic knowledge, knowledge visualisation tools, simulation, time series analysis -
can be brought to bear on the scheduling problem.
Why a Different Approach
The currently available scheduling tools are based around some form of algorithm, more or
less purpose-built, and rely on the operation of the algorithm matching the structure of
the scheduling problem. This is fine for static scheduling problems, where the structure
doesn’t change over time, but such problems are rare. However, while this approach
was the only one available, then every problem looked static - the "hammer and
nail" problem. Sometimes a strongly mathematical solution is derived for the long
term stable part of the problem, while the short term varying aspects are ignored. Without
the flexibility to handle the short term aspects, such a solution rapidly becomes junk.
More often, the algorithm takes months or years to develop, is marred by many hacks and
patches, and is often out of date before it is implemented, due to changes in the process
coming from new methods or different behaviour of plant.
Frequently, the process being scheduled must be run inefficiently or
capital wasted in excessive infrastructure because the scheduling algorithm requires slack
for it to function, or is insufficiently flexible to handle conditions slightly different
from that for which it was designed.
There have been many efforts to improve the operation of scheduling
algorithms, with each new advance increasing the specialisation of the application, or
requiring the planner to be even more inventive in attempting to twist the
algorithm’s behaviour to get the required result. Expert Systems have been built,
attempting to capture the human scheduler’s expertise in a rigid set of rules, only
to find that the human behaves non-algorithmically in complex problem solving, so no
pre-cooked set of rules is possible.
There are many Constraint Solvers, whose approach is to compile a
static structure with sets holding all the possibilities at each node, and then solve the
constraints, which are all directed to some specific purpose. This sounds great, until it
is realised that the entire structure and purpose must be known at the compile step, which
renders the solutions trivial.
Many scheduling problems are a mass of dynamic interactions, where the
structure is changing to reflect this interaction, and decisions need to be made based on
the current states in the current structure. For these sorts of problem it is difficult to
predict beforehand what those states will be, or create some rules which apply to just
that particular set of conditions. These types of problems have a swirl of interactions
and alternatives, not an orderly set of constraints.
ORION Planning and Scheduling uses a Constraint Reasoning technique (CR
for short) to allow a much more realistic description of the scheduling problem. The
description of the problem in terms of its constraints and interactions provides the
structure for its analysis. The network structure is undirected and self-modifying, and
can transmit tentative information about possible solutions. There is no external
algorithm attempting to schedule while obeying the constraints. Instead, there is a
scheduling machine built out of the constraints and interactions. This is the Non-Algorithmic
approach.
How Much is Different
What has been removed is the need for transformation of business and
technical requirements into the form of an algorithm or directed constraints. This is
usually a complex and time-consuming task, particularly its tuning for acceptable
performance. The major difficulty is the requirement to phase the operation of the
algorithm running on a sequential instruction computer so that the relevant states of the
process are examined at the appropriate time. This requires that the programmer have an
intimate knowledge of the process (and any future changes to the process), and develop a
mental model of the algorithm so that it may be written out in the form of a program. Once
written and left for some time (weeks, months), the program is very difficult to change
because the mental model the programmer used to produce it has evaporated. Changes can now
damage the fabric of the algorithm, because the detailed understanding of the interactions
woven into it has been lost.
What has been added in Constraint Reasoning is multi-layering of
control and the manipulation of the existence of structure. Control states are moving
through numeric, logical and existential structure - whatever is needed to describe the
constraints. This is not switching some bit in a set on or off, but controlling which
parts of the structure are actively involved in the problem - controlling what is possible
as a basis for controlling what occurs.
The Non-Algorithmic approach takes the descriptions of the interactions
and constraints, and directly creates an active structure where they are still evident
(and visible). Changes can be made to the original description at the business knowledge
level. Inconsistencies in the structure resulting from invalid changes are immediately
flagged. The most obvious difference between the two approaches is the elimination of
phasing by the programmer, the operators within the structure controlling the phasing of
information flow in the structure in response to changes at their connections. Each operator implements only a small simple operation, like PLUS or AND, with
the results immediately available to other operators throughout the structure, so
scheduling remains in synchronisation.
Tasks, resources, durations are expressed in terms of interacting
operators in a network that can be examined graphically. The planner can ignore the way
knowledge about the plan is represented while building the simpler aspects of the plan,
and for many scheduling plans 90% of the plan construction can be done using task entry
and editing and Gantt chart facilities already familiar to planners or schedulers who have
used algorithmic tools like CPM.
The more complex aspects of the plan are easily expressed in terms of
constraints using the ORION Textual or Drawing Editors. The Drawing
Editor in particular provides the ability to point at elements of the plan, and connect
them through assemblages of analytic operators to form constraints.
Building Variability Into The Schedule
Planning has two stages, one where it is helping you plan what to do,
and one where it is published to show everyone else what to do. The greater modelling
freedom provided by CR allows the inclusion of new types of activities and modelling in
the network supporting the schedule, modelling which will allow rapid re-scheduling if
problems arise.
Alternative Activities
Sometimes you are not sure how events will unfold in the plan, so
cannot decide between two or more potential and mutually exclusive paths (something as
simple as which resource should be used, or perhaps different technologies might be used
to produce similar outcomes). One path might be shorter but more expensive, or expose the
plan to greater risk of failure to complete some task. The logic deciding between the two
paths can be built into the network, and draw on as many influences as you wish. The two
alternative paths can themselves be mini-schedules, and don’t need to have common
starting and ending points as shown in the diagram.
Some activities in the plan may have risks associated with them - risks
that they may not occur, or that the duration becomes extended. There are two ways of
handling this, backup activities and contingent activities.
An ACTIVITY Lying In Wait
A task to be scheduled is represented in the network by an ACTIVITY
operator. The network can decide on whether a particular task is to be carried out by
switching its logical control pin. If an ACTIVITY operator does not yet have a TRUE or
FALSE state on its control pin, and it has a zero in its range of duration, it observes
any changes taking place on its Start and Finish pins. If the possible duration between
the Start and Finish values becomes less than its minimum real duration, the ACTIVITY
switches its duration to zero and sends FALSE out of its Logical Control pin. If connected
through an XOR to another activity, the other ACTIVITY will switch TRUE, forcing it to
exist and be scheduled.
Other influences on the existence of the ACTIVITY can be exerted by
cost, duration, and use of resources. A constraint on cost can feed back to force the
duration to zero, or a lack of resources may force the duration to zero. Activities can
fragment - that is, scatter their duration over a longer time period than their duration,
useful if planning necessary but peripheral tasks.
The Planning Environment
The environment that a knowledge network system can provide is
exceptionally flexible, because all of the knowledge about the plan is continually
"live", and can interact with the user, as well as grow and change with user
interaction.
The user has several graphical interfaces available to work on the
plan, the main one being a Gantt chart of the tasks to be scheduled, coupled with a plot
of all resource usage. Behind the Gantt chart, and controlling the placement of the tasks
on the chart, is an active structure. It represents the complete logical structure of the
plan, incorporating all the tasks, costs, risks, resources, constraints and alternative
ways of doing things that are in the plan. The network is carrying tentative information
through its connections, and the connections themselves can change as the tentative
information changes (changing connections is far more powerful and dynamic a means of
describing the behaviour of complex systems than is changing of values).
IF A + B = C THEN D + E = F
Using the tools provided with the Network Display and Gantt chart, the
planner can push the tasks around, couple them to specific resources, or add or remove
resources anywhere in the projected period, or switch alternatives on and off. The Linker
allows you to play with predecessor-successor relations here to get the effects you want,
after the obvious ones have been added in the Task Editing window.
After each user action, information flows through the new network
structure added as a result of the action, but now fully integrated in the plan. The
chart, resource plot and display of costs are updated to represent the new state of the
network. If a logical error, or inconsistency, is encountered while updating the active
structure, the user can examine the site of the inconsistency, work out ways of avoiding
the problem, and the plan then reverts to the previous state. The user can see a list of
the changes they have made, undo any of the changes, roll forwards and backwards in the
planning process.
As the automatic allocator is running, you can stop it, backtrack a few
steps, add another constraint while a schedule is being developed "live"- this
level of interaction demonstrates the difference between a solution only of the long term
stable aspects of the problem and a complete solution of both the long term and short term
aspects in an integrated and dynamic structure.
The User Interface
The Graphical User Interface, or GUI, to the planning model ensures
that the effects of any change are immediately shown to the user. The effects propagate
through the network, and the network represents the complete logical structure of the
plan, so no effect is overlooked, or delayed until a program runs. The planner is not
limited to changing parameters for a program, but is here changing what in conventional
terms would be the scheduling algorithm. Instead of struggling with several versions of
output from a program, and trying to reconcile the good features of several run outputs,
here the network structure itself can be smoothly changed in the desired direction, while
any missteps are simply undone. The planner can be sure that nothing has been done which
will later need to be undone because it violates some contractual obligation or resource
constraint.
The main
focus of the planner's interaction is to add constraints that represent new limitations,
and to fix gross resource hot spots that would prevent any plan at all from being obtained
(the system will show a red light on resource conflicts it couldn't fix). When the planner
is satisfied that the plan represents all of the tasks to be planned, including
alternatives where appropriate, and all of the constraints on the plan, the automatic
scheduler can be started. This has multiple goals, minimising the cost, meeting time
constraints, maintaining feasibility. It will normally begin by looking for the point of
maximum resource overload, and attempt to reduce that overload by hard booking a task.
Hints embedded in the network provide guidance as to whether the task should start as soon
as possible, as late as possible, or some dynamic variation based on what else is
happening. The allocator can choose among several alternatives by trying each in turn,
noting the cost and the severity of any new resource overload, and then choosing the best
alternative. Hard booking will usually have the effect of making other tasks undo their
tentative resource bookings at the point of conflict, and as a result reduce their start
time ranges. The automatic scheduler then searches for the new point of maximum resource
conflict, and repeats the process. If hard booking causes an inconsistency, the scheduler
undoes the booking and tries some other alternative.
Automatic
scheduling of the tasks is not being done through a clever algorithm operating on the data
the planner has supplied, but instead is using the structure of the knowledge network, and
allowing the interaction of the constraints, the resource usages, and any other logic the
planner has implanted in the network. Its method of undoing its actions is the same as the
planner achieves by pressing the Undo button. As the automatic scheduler progresses, the
Gantt chart and resource plot are updated to monitor its progress. The scheduler can be
interrupted, and changes made, even new constraints added to drive it in a particular
direction. This ability, to interact with the user while in the middle of its planning,
comes from the knowledge about the plan being expressed in a network of operators, instead
of in a stack of procedure calls in a scheduling algorithm.
The graphical tools provided for manipulating the tasks are used to add
new constraints to the network, but they are relatively simple constraints, involving
reducing the end points of a range, or linking starts and finishes of tasks together, or
dumping resources at a particular spot. To add more complex constraints or new ways of
doing things, the Drawing Editor or the Text Editor can be used. Either of these tools
allows the planner to connect as many nodes in the network as desired, using simple or
complex logic. Complete new tasks can be created, interacting with the existing tasks and
resources. At the limit of interaction, the planner can even temporarily "hot
wire" the structure, without going back to the plan's creation.
Using The ORION Planning System
The scheduling structure that you build using Constraint Reasoning has
many more uses than an algorithmic schedule or static structure. The network behaves much
more like the real environment, and can be used as a simulation model to determine the
response of the real environment to various effects, decisions, failures. Some of the
uses:
You can switch alternatives on and off manually, and observe the effect
on the schedule risk and cost, or run the Allocator to find a viable resource limited
schedule for any combination of events you have set up.
You can automate the switching on and off of alternatives, allowing the
system to find a lowest cost/lowest risk solution, where you have set up risk profiles,
cost versus time relationships and resource costs and limits.
You can put in cost functions instead of hard resource limits, so the
Allocator can "buy" extra resources at a cost, and find the lowest cost/risk
schedule within these more realistic limitations. Additional resource costs can be
nonlinear - if you need extra resources for a day, you must pay for a week, so then any
additional use within that week is for free.
You can use a Monte Carlo analysis, where some tasks have a probability
of success (20%, 90%, etc.), the system repeatedly throwing the dice to generate random
numbers to determine success or failure of particular task, and then solve the resulting
network for the particular set of random numbers. With many runs, this becomes an
excellent way of doing sensitivity analysis on a complex schedule that has many
alternative paths and tasks with completion risks.
You can use the plan to "plan under pressure" when something
goes wrong, and the snapping of alligators’ jaws makes it hard to think. Critically
examining several alternatives is a good way of preventing the hole you are in getting
deeper.
An advantage of the active structure approach is that you can wrap more
analysis around the scheduling model at any time, and add more detailed logic inside the
schedule as well. The model is extensible in any direction at any time.
A good plan requires adequate planning detail, and appropriate
behaviour built in so it responds realistically to change. As you work with the plan and
develop it, your mental model of the plan is also being refined, as you find combinations
of constraints blocking you that you may not have thought of. The more closely the plan
simulates the real environment, the more subtle and sophisticated your mental model will
be.
Undirected Interaction
in the Network
Scheduling Complexities
Refurbishment Of Aircraft Undercarriage
A high value spare like an undercarriage is held in small quantities,
and is refurbished after removal and replacement. The refurbishment takes some time, so
the repair cycle may be considerably out of sync with the necessary replacement times on a
fleet of aircraft, especially if they were all procured at around the same time.
Consumable Resources provide the ability to model this sort of situation. The usage may be
positive or negative, and the lag between production and consumption may be as complex as
one desires. Use of a spare on one aircraft will cause the position for all other aircraft
to be re-evaluated.
Tasks Swallowing Other Tasks
Heavy
equipment usually has a preventative maintenance program, and aircraft are obviously no
exception. The larger checks occur infrequently, but if they need to be pulled forward for
any reason, they should swallow the smaller checks that would otherwise have been carried
out. The logical control pin on activities makes this modelling trivially easy to
implement.
Piggybacking of Tasks
Some tasks should move to coalesce with
other tasks that are in their time range, but if the task on which they have piggybacked
moves out of range, the task must jump to another possibility. This kind of logic is hard
to build into an algorithm, easy when the logic is built into the scheduling model.
The network activity resulting from the interaction of many renewable
and consumable Resource Usage operators, jostling with each other for resources and
continually reversing the information flows at their connections as the constraints
tighten, and the ability to control existence of tasks and turn resource usage on and off
from other parts of the network, provides a large part of the flexibility of the knowledge
network for scheduling applications.
The swirl of activity in the network model as changes occur mirrors the
swirl of activity and change in the preparation and running of the schedule. The ability
to embed all the logic within the model, and have it participate in the swirl of activity,
is unique to ORION.
Planning Concepts
A Non-Algorithmic scheduler uses techniques quite
different to an algorithmic scheduler.
Constraint Reasoning
Set up constraints - Start_Date_A < Start_Date_B - and make sure
that no constraint is ever violated. Constraints can be numeric, or involve logic - IF A
< B THEN C > D, with the test or assertion as yet undecided. ORION's constraints use
reasoning at the operators that make up the constraints, rather than treating the
constraints as black boxes, so many more inferences are possible.
Consistency
If a constraint is violated, a logical error or inconsistency results.
The inconsistency may be used to cut a range of values, or may require backtracking out of
the decision that caused the inconsistency.
Ranges Of Values
A variable, like a start time, can have a singular value, say 5, or a
range of values, say 5..25, meaning the variable can have any integer value between 5 and
25. One important use of ranges is to allow switching off a task, by having a range, say
0,10 for duration. The duration can be either 10, or if forced to zero by a constraint,
the task effectively disappears. Ranges can also range negative to positive, to model
reversible conditions of supply and use. Interaction of a number of ranges at an operator
can have subtle effects. These ranges can be dynamically created by input
conditions, and do not need to be predefined or compiled, as they are propagated
symbolically through connections.
Forward Cutting
When optimising, there is usually a hierarchy of choices to make.
One can either make each choice in turn, or propagate the effects of one choice to reduce
the number of downstream choices. As a result of propagation, either the ranges of
downstream variables are reduced, or inconsistencies are encountered, forcing an immediate
backtrack without wasted effort. This technique can reduce the number of choices to be
tried by a factor of thousands or millions, making the optimisation of complex planning
models possible.
Backtrack 
Sometimes you need to make a decision, observe the
effects, then dig yourself out of the resulting hole. A planning system has the same need.
If a decision leads to an inconsistency, the system must undo that decision, so that it
can make another one. ORION has the ability to backtrack while maintaining user
interaction. Backtracking includes structural backtrack - a structure can be created,
hypothesised about, undone. It is important to notice that the structure is transiently
realised - made visible so other entities can interact with it - ensuring it stays in
context. The structure is not built out of stack frames, which would make it invisible to
the rest of the network.
Some Screen Shots
Model Editor
The editor is used to enter model statements. The global states in the
model are preserved, with changes limited to their local effects. The model shown
is for optimisation of bonus payments among project staff. The statements are undirected
relations among entities. The Begin/End structures represent logical environments or
contexts in the model. The objects in the model can be enumerated in the text or
dynamically created during operation.
Drawing Editor
The drawing editor allows for graphical construction of new operators
or structure which would be clumsy or inefficient in textual form.
Network
Display
The network is realised at all times. Tools are provided to visualise
it, and change states and values within it.
The LISTLINK operator shown is a dynamic device which has made
connections from the MAX operator to all the members of the list when it arrived (the blue
connection to the operator).
The solver provides structural debug, allowing information flow to be
trapped, solving halted and then the network visualised, making construction of large
complex models much easier.
Stochastic Editor
The Stochastic Editor permits visualisation of structures mined
from data, and ad hoc construction of distributions and relations. These operators, when
embedded in the network, assist in probabilistic reasoning about outcomes. The information
in them is not static, as reduction in range or change of distribution in one dimension
affects range or distribution in another direction through the multi-dimensional relation
connecting them. The operators can also learn through activation, allowing later
scheduling to benefit from experience.
Some Scheduling Examples
Different scheduling applications require different approaches
depending on the amount of information that needs to be assembled and mechanised. Some
examples:
Heats Through A Continuous Caster
Heats of different steels need to be scheduled through a caster.
Contamination of alloying constituents can occur from one heat to another, and different
heats have different erosion effects on the consumable elements of the caster. There are
overall production requirements for different heats, so an overall schedule can be
created, but the individual sequencing may be varied as expedient. The shutdown time for
change of the consumable elements is costly and may occur unexpectedly, so it may be
necessary to reschedule within a few minutes.
Aircraft Departures
A daily timetable of departures is available, with slots nominated
for various aircraft and headings. There are strict constraints on operation, ranging from
limits on number of aircraft on the same heading to wake vortices from large aircraft,
speed differentials between jets and prop aircraft, etc. The detailed sequence needs to be
scheduled to take account of gate delays, and possibility of interleaving of large and
small aircraft on the strip. An optimised schedule may be skittled by a need to use the
takeoff strip for an emergency landing, requiring rescheduling to minimise further delays
on already delayed aircraft, and recovery of normal operation only when a slack period is
reached.
Aircraft Heavy Maintenance
Aircraft require regular inspection and maintenance, based on flying hours,
takeoffs, etc. Each plane has a detailed history, and may require modifications,
refurbishment, and unscheduled repairs. It is necessary to mechanise the assembly of a
large amount of information about the aircraft in the fleet, and match this with the
current availability of the maintenance facilities. A separate model is used to assemble
the information and create the network for the scheduling model.
On top of the work which can be automatically planned is the
requirement for ad hoc or opportunistic addition of work. Due to the complexity of the
tasks, the regulations and the high cost, the scheduling becomes complicated by the need
for some tasks to swallow others depending on when they are scheduled, and high cost/low
holding spares to dictate refurbishment points. Planning of the work may be occurring on a
shift, daily, and weekly cycles, with infrastructure planning on a six monthly or yearly
cycle.
Rostering of Flight Crew
Cockpit and cabin crew can bid for trips they would like to take to
make up their flying hours. The trips are allocated on the basis of seniority, with
complexities added by pairing, language and training. The problem is difficult because of
the large numbers of crew involved, and their propensity to favour particular trips.
Scheduling is done by moving down a list segmented by rank and ordered by seniority,
rather than attempting to schedule all of the problem at once.
Scheduling Of Locomotives
Locomotives need to be scheduled across train movements, where
different trains have different traction requirements, and locomotives can be ferried to
different positions on the network attached to trains, or if necessary run free if a slot
is spare. The scheduling of the locomotives cannot be independent of their crewing or
maintenance requirements. Some locomotives and lines have restrictions on their
operations. The resulting schedule must wrap over a fortnightly or monthly cycle, so the
schedule is repeatable. The scheduling problem is solved simultaneously in its entirety.
Scheduling Of Examinations
There is a set of rooms, a set of subjects, a set of
supervisors, a requirement to accomplish the schedule in the minimum time or supervision
cost. One subject may spread across several rooms, or several subjects may be held in the
same room. Some supervisors are multi-skilled, so they can supervise several subjects in
the one room.
Working out a schedule of rooms and supervisors for a group of subjects
is complicated, but not too difficult if all the constraints are known before a scheduling
algorithm is built.
Where difficulties with a scheduling system arise is when ad hoc constraints of arbitrary
complexity need to be added after the scheduling algorithm is thought about and built. In
other words, constraints between any identifiable objects in the model must be able to be
added (and be effective) at any time. This imposes a severe restriction on the structure
of the scheduling system, in that logical connectives need to be added and become active
when suitable conditions arise. What usually happens is that a program is constructed,
found to be too unwieldy and inflexible, and people go back to pencil and paper figuring
of a schedule.
The Orion approach, of making all the constraints out of the same
stuff, permits ad hoc constraints to be added at any time, their logical effect being
identical to the effect of the pre-existing constraints. There is no attempt to catch all
possible constraints in a preconceived algorithm, and there is no artificial separation of
numbers and logic into a numeric network and a logical control stack, as there is with
other constraint solvers that are a mix of programming and constraint network.
The Orion model identifies the objects (the rooms, the subjects, the
supervisors) and their groupings well enough to allow a simple translation from a
subjective constraint to a constraint in the model by the people who need the schedule -
usually people unfamiliar with programming or who do not wish to invest time in rethinking
an algorithm.
The handling of constraints is sufficiently generalised and flexible to allow constraints
of arbitrary complexity to be added even during the scheduling operation, while the other
constraints are active and partial results are already available. A one time analysis of
this kind of scheduling problem, with its structure subject to change, results in either
crudity of solution or an unsupportable maintenance load.
The Ultimate Scheduling Problem
Information Extraction from free text
requires the solution of a dynamic, multi-layered scheduling problem. Text can easily be
tagged as parts of speech. There is ambiguity in this, and there is also ambiguity when
grammatical rules are applied in parsing. There are many active elements in the parsing
process, conjunctions for one - they can assert symmetry on the surrounding structure at
any level of the parsing process. The ambiguity fluctuates as pronouns and other anaphora
are resolved, using both grammatical rules and mapping from a knowledge structure, which
is dynamically analysing the alternatives. The resulting structure needs to be mapped to
the knowledge structure and update it (so clearly the structure has to be dynamically
modifiable). The structure itself is changing in response to what the text is telling it,
during the process of analysis and mapping. This is not an area for an algorithm or a
compiled set of constraints, rather one for a dynamically self-organising structure such
as an Active Structure. The application uses every skerrick of functionality that Active
Structure has - sentential logic, predicate logic, existence, time, dynamic construction
of tentative structure, embedding active devices in the structure for later activation,
constraint reasoning, structural backtrack - each of them occurring simultaneously at many
levels in the process.
See NLP treated as a
scheduling problem.
Orion Products
Home