Brought to you by EarthWeb
IT Library Logo

Click Here!
Click Here!

Search the site:
 
EXPERT SEARCH -----
Programming Languages
Databases
Security
Web Services
Network Services
Middleware
Components
Operating Systems
User Interfaces
Groupware & Collaboration
Content Management
Productivity Applications
Hardware
Fun & Games

EarthWeb Direct EarthWeb Direct Fatbrain Auctions Support Source Answers

EarthWeb sites
Crossnodes
Datamation
Developer.com
DICE
EarthWeb.com
EarthWeb Direct
ERP Hub
Gamelan
GoCertify.com
HTMLGoodies
Intranet Journal
IT Knowledge
IT Library
JavaGoodies
JARS
JavaScripts.com
open source IT
RoadCoders
Y2K Info

Previous Table of Contents Next


3.2. RESOURCE MODELING IN GUESS

Another major component of GUESS deserves attention. This is the resource modeling capability. Almost all scheduling problems depend in part on the availability of the necessary resources being present at the time of execution of a scheduled event. Some problems are primarily resource constrained, while in other problems there are a sufficient abundance of resources such that resources do not seriously constrain the scheduling. For GUESS, it was deemed necessary to add a generic resource model, capable of handling most resources that could conceivably be used in scheduling situations.

For purposes of scheduling there appear to be two generic types of resources that could be used to model most resources used within a scheduling scenario. These are termed "binary" and "depletable" resources, respectively. A binary resource is a resource in which a fixed amount is available at any given time; the resource is not depleted or consumed by the events utilizing it. An example of a binary resource might be the crew members on a space shuttle mission. Crew members may be utilized on a specific task but are not depleted or destroyed by the event. They are immediately available to tackle another task on completion of the present task. The function of the scheduling algorithm is to make sure that these binary resources are not overcommitted at any given point in time.

Depletable resources, on the other hand, are in fact consumed by tasks using them. As different events occur, these events utilize a portion of the resource until the resource is completely consumed and there is nothing left to consume. As well as consuming the resource, it is possible for certain events to replenish the resource. Typical systems that might be modeled by this approach include the consumption of propellant by a spacecraft as a result of various maneuvering events or the drain on the spacecraft battery caused by the operation of electrical equipment. In the case of the propellant, it is unlikely that events would occur to replenish the resource -- in the case of the battery, recharging could occur by orienting the solar panels toward the sun.

The function of the resource scheduler is to schedule the activities to prevent depletion of the resource before all of the required activities are complete. In the case of resources that may be recharged, the scheduling algorithm must schedule sufficient recharging events between uses to keep adequate resources in hand to perform the necessary consuming activities. This involves alternating recharging and consuming activities in some pattern to sustain the resource.

These two types of resources are the most generic resources that can be used within a scheduling context; however, it was also deemed necessary to allow the addition of custom resource models that could be user-designed yet easily integrated within the GUESS scheduling engine. These custom models could be integrated as Dynamic Link Libraries (DLLs) and attached on the fly to the GUESS executable. This would allow unlimited flexibility for GUESS and would relieve the designers of having to anticipate unusual resource models or bloating the code in trying to incorporate every conceivable resource model within GUESS.

This choice of models provided a suitable methodology for the modeling of resources within GUESS while providing plenty of room for future expansion. The next decision was the scheduling algorithms to be used in satisfying the resource constraints and their relationship to the algorithms already being used to schedule other constraints within the schedule. Rather than attempting to build an external resource model, it was felt beneficial to integrate the resource constraint satisfaction mechanism within the existing constraint satisfaction methods.

There are in fact two reasons for deciding upon this approach:

  • Resource constraints are in fact just another form of constraint, and it is beneficial to treat them in the same manner as other constraints from both a computational efficiency standpoint, as well as eliminating the need for doing several iterative calculations going from resources to constraints, in a back and forth motion, until the optimal solution to both problems is found.
  • Having a single algorithmic model makes for a very elegant solution. In fact, the same optimization techniques can be used -- the difference between the two types of constraints lies in the computation of its satisfaction score. The optimization algorithm need not be different. The "satisfaction criteria" is the only difference between the two.

The main emphasis in implementing a resource model for GUESS becomes a matter of determining the appropriate functions to use in computing resource satisfaction. The resource satisfaction should be a low value, indicating a lack of satisfaction and forcing the offending event to be rescheduled if the event makes the resource usage exceed the total allowed. The resource usage, if below the maximum allowed, is an acceptable state of affairs and should give a satisfaction rating consistent with this. For a binary resource, maximum resource usage should be encouraged (as long as the maximum limit is not exceeded), since this will tend to decrease the schedule span and make use of the resource.

For a depletable resource, the situation is not quite so clear-cut, since once a resource is gone, it must be either recharged (if it can be) or the resource is unusable for future activities. Therefore, the same positive satisfaction value is returned for all depletable resources whose usage is below the limit. A further simplifying assumption was made that resource usage is constant throughout the duration of the event. To get a profile of resource usage, resource usage is sampled throughout the duration of each event. A resource constraint satisfaction is obtained for each resource utilized by an event. A binary resource constraint will compute usage by integrating the resource usage over the time period of the event.

The algorithm first discards all events that do not overlap with the time period of interest. Then an adjustment is performed to obtain an adjusted average over the period of time for which the event overlaps. The implicit assumption is made that resource usage is linear over the event duration and multiple parallel events affect depletion in a linear additive fashion.

Usage for a depletable resource is calculated in a similar manner as that for a binary resource, with the principal difference being that all events scheduled prior to the beginning of the time period of interest must also be summed. In this instance, an overlapping event is defined as an event whose start time is less than the end of the interval of interest.

To allow the resource model in GUESS to be readily extensible, a feature for allowing the addition of custom resources is incorporated. The most flexible approach to doing this is to allow the user to add a custom dynamic link library that can be linked on the fly to the GUESS application. Doing so requires the development of a standard application programming interface (API) to allow communication between the DLL and the GUESS engine. This requires a definition of entry points and types to be utilized within the DLL. The GUESS executable loads the DLL using the standard Windows function LoadLibrary function and then attempts to load each of the exported entry points by name. GUESS loads each of the entry points by name rather than the number, even though loading by number is slightly more efficient -- loading by name is easier to use and manage. As GUESS looks up the function pointers when the DLL is initially loaded, this causes an imperceptible performance penalty. If GUESS either cannot load the library or cannot find one of the required functions, then an error message is reported.

The scheduling engine in GUESS uses the suggestion tabulator. When a resource is over-committed and needs to be rescheduled, the suggestion preferred is to reschedule the current event to occur just after the last event using the resource. Since events are processed in priority order, this forces lower priority items to be scheduled later than high-priority events. A more sophisticated means of producing suggestions could be included as a later enhancement; however, for the test cases considered, the suggestion strategy yielded acceptable results.


Previous Table of Contents Next

footer nav
Use of this site is subject certain Terms & Conditions.
Copyright (c) 1996-1999 EarthWeb, Inc.. All rights reserved. Reproduction in whole or in part in any form or medium without express written permission of EarthWeb is prohibited. Please read our privacy policy for details.