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 days 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.
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 doesnt 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 algorithms behaviour to get the required result. Expert Systems have been built, attempting to capture the human schedulers 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.
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 dont 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
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 TasksSome 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.
A Non-Algorithmic scheduler uses techniques quite different to an algorithmic scheduler.
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.
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.
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.
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.
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.
The drawing editor allows for graphical construction of new operators or structure which would be clumsy or inefficient in textual form.
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.
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.
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.
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 ProblemInformation 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.