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



TABLE 1
Sample List of International Intelligent Scheduling Systems (Liebowitz, 1994)
 
Singapore Changi Airport Resource Allocation System: schedules ramp handling services to the airlines
Korea DAS (Daewoo Shipbuilding Scheduling) project for scheduling ship repair and shipbuilding tasks
  UNIK-PCS (Yukong Ltd.) -- schedules daily purchase and deliveries of oil
  Pohang Iron and Steel Co. -- expert scheduling systems for steel manufacturing
Norway SINTEF SI (Oslo) -- developing expert scheduling systems for improving logistics performance in industry and civil services (oil well activity scheduling)
  TRUTH (Esprit 6463) -- developed generic software for reactive scheduling
Australia SACSS (Steel making and casting scheduling system) at BHP
France ILOG SOLVER/SCHEDULE (Ilog, Inc.) -- an object-oriented, constraint-based satisfaction tool
Mexico An intelligent scheduling system at HYLSA to assign steel rolls to electric furnaces for reheating
Japan Expert scheduling systems in steel and metal industry (NKK)

As the maturity of the intelligent scheduling system field has grown, a number of tools (like in the constraint-solving area) have been developed to help in the development process of intelligent scheduling systems. Examples of worldwide constraint solving tools include:

  • CHARME (Bull)
  • CHIP (Cosytec)
  • CHLEO and CHLARE (Axia Recherche)
  • DECISION POWER (ICL)
  • ORION (Interactive Engineering/Machine Reasoning)
  • ILOG SOLVER/SCHEDULE (Ilog, Inc.)
  • PROLOG III (Prologia)
  • SNI PROLOG (Siemens)
  • APSHELL/SCHEDES (Fujitsu)
  • ES/PROMOTE/PLAN (Hitachi)

Another emerging development in the intelligent scheduling system field has been on generic scheduling and building tools to facilitate generic scheduling. Examples of such generic expert scheduling or planning system tools are: O-Plan2 and TOSCA at the University of Edinburgh, PARR (Bendix/Allied Signal), ROSE (Loral), AMP (Stottler-Henke Associates), and UNIK (KAIST, Korea).

Most of the intelligent scheduling systems use either a constructive scheduling method or a repair-based method. The constructive method grew out of the ISIS work at CMU, and incrementally extends a partial schedule until it is complete. The repair method, developed from NASA Ames' work, iteratively modifies a complete schedule to remove conflicts or to further optimize the schedule.

Looking to the near term, what are some research areas that need to be addressed in the intelligent scheduling area? Some of the research needed includes:

  • Benchmarking intelligent scheduling systems and doing performance analysis (see the Special Issue on "Expert Scheduling Systems and Their Performances," Expert Systems With Applications Journal, Vol. 6, No. 3, Elsevier, Oxford, 1993).
  • Establishing a methodology for building intelligent scheduling systems that clarifies the scope of their applicability.
  • Developing general or generic intelligent scheduling systems/tools.
  • Developing problem description vocabulary, classification scheme, and map of the problem space (Karl Kempf at Intel has echoed this point).
  • Constructing a mapping between problem leaf nodes and solutions leaf nodes (mapping problem requirements to scheduling approaches for use in expert systems).
  • Realizing that the AI part of the scheduling system may be very little in terms of the overall scheduling system development -- integration issues, user interface design issues, and other non-AI issues may consume much of the development time.
  • Researching the relationship between, and integration of, planning and scheduling techniques (unified framework).
  • Applying machine learning techniques in scheduling (see Aytug et al., "Review of Machine Learning in Scheduling," IEEE Transactions on Engineering Management, IEEE, May 1994).
  • Improving management awareness/technology transfer/implementation methods.

Another important research area is "cooperative scheduling." This involves keeping the human in the loop. Under cooperative scheduling, procedures, rules, and the user cooperate to make a schedule. This doesn't replace the user and automatically produce an optimal solution to a problem that the user has formulated, but rather collaborates with the user in designing a feasible solution. This is regarded as a decision-making rather than a constraint-satisfaction problem. Scheplan, of IBM Tokyo and NKK, Japan, uses this approach for steel-making production scheduling.

Most intelligent scheduling systems today have the inability to adapt and learn. Future research issues for learning methods in AI scheduling systems are:

  • Continue to explore ways and paradigms for learning (rote learning, inductive learning, neural network learning, case-based learning, classifier systems, etc.).
  • Provide means to learn how to trade off management goals, which are often inconsistent and time-varying.
  • Learn about the uncertainties that exist in a given production environment.
  • Validate the results that machine learning has produced.
  • Examine a richer representation for handling the complexities and nuances of scheduling environments.
  • Need better methods for inherently dynamic learning techniques and for real-time learning.

Aside from these technical issues, management issues are just as, and perhaps even more, important than the technical ones. The technology may not be the limiting factor, but the "management" of the technology may curtail a project or technology. One may have a technical success but a technology transfer failure. According to Gill (1995) and Yoon et al. (1995), the downfall of expert systems has been primarily due to organizational/management-related issues. Thus, future research should concentrate on improving technology transfer, institutionalization, and organizational factors.

Overall, the major trends in intelligent scheduling systems are:

  • The majority of the AI approaches to scheduling have been constraint-based; the last 7 to 8 years have seen the emergence of constraint-based programming languages [e.g., CC(FD)].
  • Movement toward expert scheduling system shells/generic constraint-based satisfaction problem-solvers.
  • Interest in object-oriented programming paradigms and hierarchical architectures used in intelligent scheduling systems.
  • Continued use of hybrid intelligent systems for scheduling (knowledge-based, neural networks, fuzzy logic, genetic algorithms, optimization/operations research, etc.).

2. GUESS (GENERICALLY USED EXPERT SCHEDULING SYSTEM)

As stated previously in the research directions for intelligent scheduling, there is great need to develop a generic scheduling toolkit in order to minimize the "reinventing the wheel" phenomenon. Toward this goal, GUESS (Generically Used Expert Scheduling System) has been developed as a generic expert scheduling system architecture and toolkit.

GUESS is designed to aid the human scheduler and to keep him/her in the loop. GUESS is a decision support aid as opposed to an automated replacement for the human scheduler. GUESS is programmed in C++ and runs on an IBM-PC Windows environment. GUESS has been designed to take advantage of an object-oriented, hierarchical architecture. GUESS contains two major levels of schedulers. The low-level schedulers are composed of different scheduling methods, mainly heuristic-based and optimization/algorithmic-based. The high-level scheduler, called the metascheduler, coordinates the activation of the low-level schedulers and injects any new information that is pertinent to the scheduling problem.

An object-oriented approach has been used for GUESS in order to maximize the reusability and corresponding generality of GUESS. As an example, GUESS can schedule 2551 events and over 14,000 constraints in under 45 seconds on a Dell 486 computer.

The next sections will discuss the design and development of GUESS.


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.