![]() |
|||
![]()
|
![]() |
![]() |
![]() |
Chapter 23
|
1. | General Background on Intelligent Scheduling Issues, Trends, and Research Directions | ||
2. | GUESS (Generically Used Expert Scheduling System) | ||
3. | The Object-Oriented Structure of GUESS | ||
3.1. | Major Scheduling Approaches Used in GUESS | ||
3.1.1. | Suggestion Tabulator (Sugtab) | ||
3.1.2. | Hill Climbing | ||
3.1.3. | Genetic Algorithm Approach | ||
3.2. | Resource Modeling in GUESS | ||
4. | Testing and Performance of GUESS | ||
5. | Summary | ||
Acknowledgments | |||
References |
Scheduling is a popular topic for intelligent systems. In a survey of operational expert system applications in business from 1980 to 1993 (Eom, 1995), the largest percentage (48%) of operational expert systems was in productions and operations management and expert scheduling systems were a dominant percentage of these.
Scheduling involves accomplishing a number of things that tie up various resources for periods of time. It is constraint-driven, meaning that a scheduling problem can be defined as a set of constraints to satisfy. A solution to the scheduling problem is a set of compatible scheduling decisions that guarantee the satisfaction of the constraints (Noronha and Sarma, 1991). Guaranteeing the compatibility of the decisions made is the role of constraint propagation. The order in which decisions must be made needs to be determined.
Most schedules need to be redone. In manufacturing, for example, reports from shop personnel in industries as diverse as semiconductor fabrication and automobile manufacturing estimate that the effective useful life of a daily schedule is an hour or less (Fox and Zweben, 1994). Thus, the 8-hour or 16-hour production schedules need to be reworked. A critical element of scheduling, therefore, is the effective ability to reschedule.
In identifying expert scheduling system approaches used, Liebowitz (1993) did a literature review of 250 references, over 2 years, dealing with expert scheduling systems. Liebowitz found that 137 used a heuristic scheduling approach, 16 used an optimization/algorithmic scheduling approach, 42 used a hybrid scheduling approach (heuristic and optimization), and 55 were unknown (no scheduling approach was mentioned). In all, there were 24 major scheduling approaches used in these expert scheduling systems. Three classes of expert scheduling system approaches emerged.
The first class deals with optimization scheduling methods. These include enumerative algorithms and mathematical programming methods. Enumerative algorithms search for an optimal solution by enumerating and comparing all possible solutions. Branch and bound and dynamic programming are examples of such. Mathematical programming methods formulate the problem as a mathematical model, like integer and mixed-integer programming. The problem with optimality in scheduling is that optimality is hard, if not impossible, to define in a realistic scheduling environment. The number of possible solutions increases so fast that there are no practical results, and it may be too time consuming to determine the optimum solution. This is because scheduling deals with NP-complete problems where no method can be discovered that doesn't grow exponentially in problem size.
The second class of scheduling approaches in intelligent systems is the use of heuristic approaches. There are several heuristic algorithms that have been used in scheduling, including neural network algorithms, greedy algorithms, intelligent pertubation algorithms, simulated annealing algorithms, and genetic algorithms. Other heuristic scheduling methods have also been used extensively, for example, conflict resolution strategies, resource-based scheduling, order-based scheduling, blackboard-based scheduling, lookahead scheduling, and the like. The heuristic approach for scheduling produces and maintains "satisficing" schedules over time; that is, schedules that are good, workable solutions derived quickly, but may not necessarily be the optimum schedule.
The third class of intelligent scheduling approaches is hybrid methods. These include artificial intelligence (AI) plus simulation-based scheduling, optimization/operations research plus AI scheduling, and hybrid systems combining the strengths of the other approaches.
In looking at the NASA mission planning environment, Liebowitz (1993) identified 63 major requirements for a mission planning expert scheduling system. These requirements fit under the classes of: general requirements, resources/constraints requirements, activity requirements, scheduling capability requirements, rescheduling capability requirements, output requirements, user interface and control requirements, and system interface requirements. The recurring themes in studying the expert scheduling system literature are the need for a hierarchical architecture for scheduling, the ability to quickly and effectively perform rescheduling automatically, the need for good user and system interface design, and the need to have various techniques accessible for use in scheduling (a toolkit approach).
In the NASA environment, scheduling is a critically important area. According to the Engineering Services Group of McDonnell Douglas, projecting out to the space station of the next decade, scheduling will be required for 365 days of the year and could take 2000 to 3000 people working continuously. NASA Headquarters officials have mentioned that two of the most pressing tasks that NASA will have to deal with in the future are data analysis and scheduling. With the scheduling domain, people have learned two things: (1) scheduling is a difficult area, and (2) nothing goes according to schedule (Brown and Scherer, 1995). In the ATDRSS (Advanced Tracking Data and Relay Satellite System) at NASA, ATDRSS era service requests will increase 3- to 10-fold in number from today's TDRS requests for using the satellites. Human aids, like expert scheduling systems, are needed to assist the human schedulers. Within NASA, intelligent scheduling systems are already being used for such tasks as scheduling Shuttle and payload launches, scheduling satellite experimenter use of the satellite, and a number of other scheduling applications (Liebowitz, Lightfoot, and Dent, 1991; Liebowitz and Lightfoot, 1993).
Outside of NASA, many of the major airlines like Singapore Air, Japan Air, United, TWA, Iberia, and others are using expert scheduling systems for aircraft gate assignment. A number of international applications of intelligent scheduling systems are being used for daily, medium-term production scheduling, aircraft maintenance, scheduling power generating units, job shop scheduling, semiconductor wafer production, newspaper printing runs, paper production, real-time factory scheduling in a VLSI development line, flight crew scheduling, and airport staff rostering. A sample of intelligent scheduling systems being used worldwide is shown in Table 1.
Previous | Table of Contents | Next |
![]() |
|
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. |