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


4. TESTING AND PERFORMANCE OF GUESS

Scheduling problems are often complicated by large numbers of constraints relating activities to each other, resources to activities and to each other, and either resources or activities to events external to the system (Morton and Pentico, 1993). For example, there may be "precedence constraints" connecting activities that specify which activities must precede other activities, and by how much of a delay, or by how much allowed overlap. Or two particular activities may interfere with each other and be unable to use the same required resource simultaneously. Or it may not be possible to use two resources simultaneously during certain parts of the day or on the same activity. Or a resource may be unavailable during specified intervals due to planned maintenance or planned use outside the system. Since these complex interrelationships can make exact or even approximate solutions of large scheduling problems very difficult, it is natural to attempt to solve simpler versions of a problem first in order to gain insight. Then one can test how sensitive the solution is to this complexity and find approximate solutions to difficult problems where the complexity proves central (Morton and Pentico, 1993). This is the approach that the GUESS team followed in testing GUESS for proper verification and validation, as well as for its generic capabilities.

Morton and Pentico (1993) point out that a major need exists for the development of generic heuristic scheduling shells that would allow software houses or even sophisticated users to craft a scheduling system by inputting a description of the system structure and general parameters. Pinedo (1995) also suggests the need for a generic scheduling system. He indicates the following typical features of a generic scheduler (1995):

  • Most generic scheduling systems have automatic scheduling routines to generate a "first" schedule for the user.
  • Almost all generic scheduling systems have user interfaces that include Gantt charts and enable the human scheduler to manipulate schedules manually.
  • Generic scheduling systems usually have report generators.
  • Generic scheduling systems have a number of advantages over application-specific systems, including if the scheduling problem is a fairly standard problem and only a minor customization of a generic system suffices, then such an option is usually less expensive than developing an application-specific system from scratch.

GUESS is currently being tested in a number of applications. For NASA applications, such as scheduling satellite experimenter requests to use the NASA supported satellites, GUESS can schedule 2551 events and over 14,000 constraints in 45 seconds on a Dell 486 computer. This performance corresponds well with other NASA expert scheduling systems that can schedule up to 6000 events in 2.5 to 3 minutes.

We are also currently testing GUESS in other scheduling domains. These include: (1) scheduling for an Army strategic decision support application (i.e., force mobilization in a deployed theater); (2) scheduling Department of Computer Science courses and corresponding sections for a local college; (3) scheduling the baseball games; and (4) scheduling Army battalion training exercies. From preliminary results, we are optimistic that GUESS is generic enough to be easily used in these different scheduling applications.

5. SUMMARY

In the coming years, the major trends in intelligent scheduling systems will be:

  • The majority of the AI approaches to scheduling will continue to be constraint-based.
  • Movement will continue toward expert scheduling system shells/generic constraint-based satisfaction problem-solvers.
  • Interest will expand in object-oriented/agent-based programming paradigms and hierarchical architectures used in intelligent scheduling systems.
  • Increased use will occur of hybrid intelligent systems for scheduling (knowledge-based, neural networks, fuzzy logic, genetic algorithms, optimization/operations research, etc.).

We feel that GUESS is an effort that supplements well these future directions in intelligent scheduling. More testing for the generic qualities of GUESS will be conducted in the near term, as will the expansion of the number of scheduling techniques in the GUESS toolkit.

ACKNOWLEDGMENTS

The authors appreciate the support from Colonel Wilkes and Professor Campbell at the Center for Strategic Leadership at the U.S. Army War College, George Washington University, and support from NASA Goddard Space Flight Center.

REFERENCES

Brown, D. And W. Scherer (Eds.) (1995), Intelligent Scheduling Systems, Kluwer Publishers,
MA.
Eom, S. (1995), "Survey of operational expert system applications in business and
management," Interfaces, TIMS.
Fox, M. and M. Zweben (Eds.) (1994), Intelligent Scheduling, AAAI Press/MIT Press, Menlo
Park, CA.
Gill, T.G. (1995), "Early expert systems: where are they now?" MIS Quarterly, SIM, Minnesota,
Vol. 19, No. 1, March.
Lee, J.K., M. Fox, and P. Watkins, Special issue on "Scheduling Expert Systems and
Their Performances," Expert Systems with Applications: An International Journal (J. Liebowitz, Ed.), Elsevier/Pergamon Press, New York, Vol. 6, No. 3, 1993.
Liebowitz, J. (1993), Mapping Problem Requirements to Solution Scheduling Approaches in
Expert Scheduling Systems for Mission Planning, Phase I Report, American Minority Engineering Corporation, NTIS, Arlington, VA.
Liebowitz, J. (Ed.) (1994), Worldwide Expert System Activities and Trends, Cognizant
Communication Corp., New York.
Liebowitz, J. and P. Lightfoot (1993), "Scheduling approaches in expert systems: a study of
their applicability," Expert Systems with Applications Journal, Elsevier, Oxford, Vol. 6, No. 3, July-September.
Liebowitz, J., P. Lightfoot, and P. Dent (1991), "Conflict resolution strategies in expert
scheduling systems: survey and case study," The Knowledge Engineering Review, Cambridge University Press, England, Vol. 6, No. 4.
Morton, T. And J. Pentico (1993), Heuristic Scheduling Systems, John Wiley & Sons, New
York.
NASA Goddard Space Flight Center, Proceedings of the 1995 Goddard Conference on
Space Applications of Artificial Intelligence, Greenbelt, MD, May, 1995.
Noronha, S.J. and V.V.V. Sarma (1991), "Knowledge-based approaches for scheduling
problems: a survey," IEEE Transactions on Knowledge and Data Engineering, IEEE, Vol. 3, No. 2, June.
Pinedo, M. (1995), Scheduling Theory, Algorithms, and Systems, Prentice Hall, Englewood
Cliffs, NJ.
Stolte, A., An object-oriented approach to scheduling, AI Expert, Miller Freeman
Publications, San Francisco, CA, 1994.
Wentworth, J.A. and R. Knaus (1994), "Highway Applications of Expert Systems:
Guide for Test and Evaluation," White Paper, U.S. Federal Highway Administration Research Center, Washington, D.C.
Yoon, Y., T. Guimaraes, and Q. O'Neal (1995), "Exploring the factors associated with expert
systems success," MIS Quarterly, SIM, Minnesota, Vol. 19, No. 1, March.
Zweben, M. And M. Fox (Eds.) (1994), Intelligent Scheduling, AAAI/MIT Press, Cambridge,
MA.


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.