![]() |
|||
![]()
|
![]() |
![]() |
![]() |
3. THE OBJECT-ORIENTED STRUCTURE OF GUESSA schedule has an events list and the resource list. A resource list is made up of resources of different types that directly or indirectly have an impact on the schedule. The events list is made up of different kinds of events. Most of the events have to be scheduled, while some act more like markers in the schedule to support the resource modeling. The primary organizing construct is a class that describes an object. GUESS is a generic scheduling system. It can schedule different kinds of things. The OOPS feature of GUESS is that classes represent various abstractions of scheduling objects, such as events, constraints, resources, etc. An event in the schedule is implemented as a class that has members and functions acting on it. An event has its priority, start time, end time, a constraint list acting on it, an effects list, and finally a text-based name for human benefit to improve the readability and maintenance. All events are inputted with a start and stop time. If an event has time conflicts, the event will be rescheduled. Technically, this qualifies GUESS as a repair-based scheduling system. Always having start and stop times avoids the concept of having to track an event's status as scheduled versus unscheduled. Also, the many objects in the system that deal with events don't have to know about scheduled/unscheduled status as an event is always considered scheduled. The constraint list in an event has different kinds of constraints acting on the event. A constraint class has the weight of the constraint and the constraining resource or event. A constraint can indicate its satisfaction level. An event's satisfaction level is computed as a weighted average of its constraints satisfaction. An event's satisfaction is a measure of how well scheduled it is. In addition to after-the-fact measuring, constraints are also used to generate start and stop times for events. A constraint by an event is a relational constraint. Relational constraints have the following subclasses: Before, After, During, NotDuring, StartsWith, EndsWith. A relational constraint is time based and can be between any two events. Suppose event E1 has to come before event E2. Event E1 would then have a Before constraint to E2. The other relational constraints operate as expected. Note, the previous case of E1 having a Before constraint does not imply that E2 has an After constraint. If desired, the After constraint would have to be separately created for event E2. Event classes, constraint classes, and resource classes all have names for user readability and inputting. With inheritance, they can all use the same name handling code by inheriting from a common parent class. The subclasses of events, constraints, and resources get the same name handling code by default. Also by inheritance, the list handling code is used by many classes. Objects in lists are accessed by the cached reference system. A cached reference to an object has both the name of the object in question and a pointer to the object. The pointer is found once by searching the list. By caching the pointer, the cached reference needs only to look up an object in a list once, saving time. A more important feature of cached references is the ability to refer to an object that hasn't been created yet. Interdependent object systems can have the problem of needing to reference an object before it exists. We don't look up the reference until it is needed, thus allowing a legal reference to an object before it exists. 3.1. MAJOR SCHEDULING APPROACHES USED IN GUESSGUESS currently uses three major techniques for scheduling. The first scheduling method uses the Suggestion Tabulator, which is a heuristic approach where GUESS uses information derived from the constraints. The second method is a hill-climbing algorithm. The last scheduling method used in GUESS is a genetic algorithm approach, which is novel in that few scheduling systems have tried using such an approach. The first two techniques will be briefly discussed since they are more commonly used in intelligent scheduling systems. The genetic algorithm approach will be described more fully as it has rarely been used in intelligent scheduling applications. 3.1.1. Suggestion Tabulator (Sugtab) The input file is read first. Depending on the technique chosen, the scheduling of the events takes place and the overall schedule is generated as output. Events are scheduled one at a time, starting with an event of highest priority. To start, an event is scheduled by asking all of its constraints for their suggestions. A suggestion tabulator is given to an event, and the event passes it to each of the event's constraints. Each constraint can make zero or more suggestions to the suggestion tabulator, after which it can deduce the best beginning and ending times for the event based on the accumulated suggestions. The sugtab for an event is of four types: beginning range, ending range, beginning and ending equal suggestions. The range is controlled by greater and less than suggestions. Some constraints suggest a specific time for the beginning or end. An equal tabulator tabulates the equal condition suggestions and returns the value. The range tabulator tabulates the range by keeping a low and high limit. 3.1.2. Hill Climbing This is another technique available for scheduling events in GUESS. The initial beginning time and satisfaction of the event is assumed to be the best, and a nonlinear search for better values is done on both sides of the initial value of time to search for better time and satisfaction. As the search transverses through either sides of the hill, the exponential increment for the time change can be adjusted for speed improvement. Similar to other techniques, the satisfaction of a particular event is calculated based on the satisfaction level of all its corresponding constraints. The higher the satisfaction level of an event, the happier it is in the schedule.
|
![]() |
|
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. |