Tech Note

Title:               Proposed Interactive Scheduling Approach
Date:              May 6, 2003
Written by:     Peter C. Bosch
Number:        TN-008
Version:         0.1

This tech note captures the results of a discussion between several client developers and myself. It represents the SOM-specific part of a proposed approach to the challenge of satisfying the needs of long-term schedulers in particular, all schedulers in general, and presents a mechanism for alleviating performance issues if they arise when presenting a Shift View schedule.

A scheduling engineer, as well as software exploring the scheduling landscape, needs to be able to explore the effects of laying out batches and campaigns of variable and varying sizes against a physical plant, with assignments of specific pieces of equipment to specific batches and campaigns, and observe the effects of automatic and/or manual placement of such batches and campaigns against utilization, duration, yield and raw material availability.

The general approach is to create a time-based representation of the physical plant that allows all-at-once representation of resource, raw material and product levels over time, and then, in priority order, run distilled simulations representing batches and campaigns against that representation with equipment assignments made to varying degrees of specificity, afterward observing the effects of those runs on the physical plant representation.

This document describes the high-level approach, using mechanisms that are mostly in place, at least in part, in the SOM already. It is intended either to provide enough information to eliminate this approach, or to provoke further discussion at a deeper and more detailed level.

Resources

A resource is anything that is used by a process, and for which that use must be granted. If its availability can affect the progress through a process (such as a batch or campaign), it is a resource.

Resources have two orthogonal classifications. Resources are discrete or continuous, and resources are consumable or persistent[1].

A continuous resource is a resource that can be acquired and released fractionally, and for which the acquired resource does not have an identity separate from the whole, such as acquiring 24.5 lbs of steam from a 200 lb steam header, or 40 kg of sodium nitrite from inventory.

A discrete resource is a resource that can only be acquired 1 at a time (or 2 at a time, etc. – e.g. in integral quantities), and for which each integrally acquired resource has an identity and state, such as a piece of equipment, a barrel or a mixer.

A consumable resource is a resource for which consumption and provision events are decoupled – that is, once a consumable resource has been removed from the pool, there is no guarantee that it will be returned to the pool. Typically, consumable resources are taken from a pool, and never returned. A different entity or set of entities is typically responsible for reprovisioning the pool, and the resources with which it reprovisions are unrelated to those formerly removed from the pool. While a consumable resource is not persistent, the pool (probably an Inventory object) is persistent.

A persistent resource is a resource that is not consumed. It is taken from the pool, and later returned to the pool.

 

resource taxonomy

Figure 1 : Resource Taxonomy

 

Resource Usage Profiles

We envision equipping each resource with a time-sorted list of allocation and release (or replenishment) events. The following figure depicts a graphical representation of such a list. Equipment A1, for example, is an atomic, persistent resource that is acquired and subsequently released three times during the course of execution of the model. It has an approximately 40% utilization.

plant state timeline

Figure 2 : Plant State Timeline

 

Resource Acquisition

Resources are assigned to one or more pools. Resource pools are hierarchical. A resource pool has a resource manager, from which a resource user will request a resource, through an object (essentially an agent). The resource desirer submits a resource request to the appropriate resource pool. The resource manager begins handing the resources to the request one by one, and the request scores each one. The request may examine any attribute of the resource (in addition to anything else the request is coded to consider), but must score each object. The score is a double. Double.MinValue means “No, this is totally unsuitable,” double.MaxValue means “This is perfect. Give it to me now – I don’t need to see any more.” Any double in between is seen as a scalar value judgment, and if no resources received a double.MaxValue score, then after all resources have been scored, the one with the highest value is granted. We can add the ability for all resources, including those currently unavailable, to be provided to the request for scoring, in order to broaden the range of feasible scoring algorithms. The figure below depicts this mechanism.

 

resource pools

Figure 3 : Resource Requests & Pools

Physical Plant

“Physical plant” refers to the collection of all resource pools and the resources they manage. We may eventually need to develop an abstraction to represent location, with transportation costs and durations under each. Resources move between pools with varying (defaulting to zero) transportation costs.

Processes

Processes are activities that are described by a directed acyclic graph of tasks, representing, essentially, the workflow through that process. A process may acquire and release resources, and consume duration. Tasks are hierarchical, in that they may contain one or more child tasks. Some parent tasks run either/or in respect to their child task graphs, and some parent tasks run in addition to their child task graphs. Multiple tasks may be running at the same time, and tasks’ starts or completions may be dependent on other tasks’ starts or completions.

An enterprise process may be represented as a task, with tasks for each location running in parallel underneath them, tasks representing zero or more campaigns running under the location process, tasks for batches running under each campaign, tasks for operations running under each batch, tasks for operation steps running under each operation, and so on.

The smallest and most essential task, which can be used to represent any other set of occurrences, is shown below. It acquires one or more resources, waits a specified duration, during which time it may change the contents of the graphContext, and it finally releases some set of zero or more resources. The changes imposed on the GraphContext may be as simple as incrementing a counter or as complex as the mass-balance and chemistry computations that take place under the purview of the MAI Modeler. Note that the resources released are not necessarily those obtained by the task itself at its beginning, but perhaps some resource(s) present on the GraphContext. Furthermore, a consumable resource may be (probably will be) released to a different entity, such as a discharge sink or another inventory pool.

essential task

Figure 4 : Essential Task

A task’s execution begins at a specific time in the simulation engine, when the preVertex is notified that its’ preceding edges have all fired. At that point, it performs the functionality it was written for. If that functionality entails the task suspending itself for a period of time (as measured by the simulation executive), then the task is seen to consume simulation time, and to have duration. If it executes directly to completion, notifying its postVertex that it has completed, then it is seen to have occurred instantly, with respect to simulation time. If it suspends itself, other tasks may be given a chance to run at that same simulation clock time.

Graph Context

A graph context is a representation of a collection of state information as it progresses through time. It changes as time passes in the simulation, and represents the “current state of things” relevant to a particular task graph. Any changes that a task makes to the physical plant, that need to be communicated to downstream tasks, or that need to be known at the finish of the graph’s execution, are communicated through the GraphContext. Several tasks that are in progress at a given simulation time could each affect the state of the GraphContext, as shown below, when TaskA1 changes something in the GraphContext, followed by TaskB1, and then again by TaskA1.

Figure 5 : Graph Context w.r.t. Concurrent Tasks

In the SOM under the MAI Modeler, there is one GraphContext for each batch, and each GraphContext contains current mixture state, as well as snapshots of all prior states at the start and finish of each operation’s execution, as well as a wide range of other information.

Task Effect Aggregation

A task has the previously-mentioned effects – it may acquire resources, it may modify unit state, it may consume time, and it may release resources. If we can ignore the mixture dynamics, (chemistry and thermodynamics), this abstraction holds as a simplification of each task in a recipe. From a scheduling perspective, we can represent an operation as a set of time specified acquisitions, releases, and modifications of GraphContext. The quantities of resource acquired & released, and the relative timing information are dependent (often in non-intuitive ways) on batch size and allocated equipment capabilities. Steve Morrison is working on a way to characterize these relationships, such that we can derive these external effects of a task, to a relatively good fidelity, as a function of batch size. Depending of the degree of success we see in this effort, it is reasonable to envision an entire batch, abstracted out to a series of time-specified events that acquire and release resources to a physical plant model. See below for an example of this concept. A campaign could be seen as a cascaded set of these überTasks, with their resource acquisition times affected by the resource availability as dictated by the resource utilization profile. Note that it is more likely that we will construct task graphs for each batch that drive down to the operation (or even operation step) level, but which are “gutted” of their physics and chemistry effects, and have duration driven off an analytical engine of Steve’s design. This would (a) achieve high performance with reasonably good fidelity in the task timing relationships, particularly as they relate to timing changes due to resource contentions, and (b) eliminate the chemistry, physics and thermodynamic effects about which we care little in a scheduling application.

 

 

task effect aggregation

Figure 6 : Task Effect Aggregation

Note: We will probably not aggregate to as high a level as this diagram suggests.

All Together, Now!!!

We create a physical plant, resources and resource pools. We attach raw material provisioning events to the pools that manage materials, and define a start time. Remembering that resources can be contained in more than one pool, resource pools are created for each campaign or batch, and equipment & raw material inventories are assigned to those resource pools. We then take our most important campaign and run it against the plant, commencing at time zero. Using a greedy acquisition scheme, it acquires and releases resources, produces product, and consumes materials, affecting the resource utilization profile. This defines the temporal availability of resources and materials with that campaign having run.

Now, we define and run another campaign (our second-most-important one) against that resource utilization profile, commencing it, too, at time zero. Alternatively, the user or exploring software could give it a later time to start. If it cannot commence immediately, it will start as soon as the resources it needs to start are available, so you will see, when it has run, its earliest start time, and the temporal availability of resources and materials with the two most important campaigns having run.

If, after placing several campaigns, one is deemed undesirable, it may be removed. By scanning the allocation and release event list and removing allocations and releases attributable to tasks in that campaign, we can update the resource usage profile to reflect the effect of having removed that campaign.

Note that such a removal (of a released/returned resource) may have an effect on the ability of existent (still active) campaigns to run. For example, a campaign that produced an intermediate product may have replenished the level of a particular source material for a subsequent campaign, enabling it to run. This only applies to consumable resources, since in the case of persistent resources, the same campaign that released it, will have subsequently acquired it, and both the acquire and release events will be removed at the same time. In this situation, the violation (indicated by negative levels of a consumable resource) should be highlighted, and the schedule marked invalid. To revalidate, the operator will re-run the layout algorithm, clearing all acquisition/release events and re-running the sequence of simulations (primary campaign, then secondary campaign, then tertiary, etc.) The timing of each will settle at (absent other algorithmic mechanisms) its earliest occurrence.

In the following figure, we show the results of a (very simplified) schedule development effort in which we have placed three sulbactum campaigns against a very simplified plant with two vats, two dryers (both sets of equal sizes) a source material inventory and a product material inventory. Many resources of all four types are not shown. With different sized vats and different capabilities for each, the resource requests’ scoring logic might be more complex than, “if it’s available, take it,” but otherwise, the outcome would be the same. It is important to realize that when placing campaign B, the resource utilization profile would already have been affected by batch A.

three campaigns

Figure 7 : Three Campaigns Scheduled

In the next figure, we show the effects of rescinding campaign B. Campaign C remains where it originally settled, and the resource utilization profile has changed to reflect the no-longer-present campaign B, but with a re-running of the scheduling algorithm, campaign C would slide left, to run at the time that campaign B originally ran.

If we use the same, or similar mechanism to the one in place in the SOM for modeler validation, we can ensure that resimulation is necessary only from the point of a change, onward.

This approach could (and probably should) be applied at the batch level, with each batch’s effect modeled against the resource utilization profile. This would permit the scheduling operator to explore the effects of using more or fewer batches, assigning different configurations of resource pools, and assigning different resources to them.

 

 

 

resource track, three added, one removed

Figure 8 : Three Scheduled, One Removed

 



[1] In this case, the word ‘persistent’ does not have the typical meaning of ‘stored to disk’, but rather means that something has an existence in which it may be used serially by one or more unrelated entities.