KBSS: a knowledge-based job-shop scheduling system* |
| |
Authors: | O. CHARALAMBOUS K. S. HINDI |
| |
Affiliation: | Decision Technologies Group of the Computation Department , University of Manchester Institute of Science and Technology , P.O. Box 88, Manchester, M60 1QD, UK. |
| |
Abstract: | Abstract. A knowledge based job-shop scheduling system (KBSS), which employs artificial intelligence techniques to solve general job-shop problems, is presented. The system consists of two main components: a knowledge base (KBSS model) and a control mechanism. The KBSS model has a three-level architecture which captures, in frames, knowledge about the job-shop domain and the characteristics of individual job-shop problems. The control mechanism consists of two modules: the primary scheduler (PS) and the heuristic scheduler (HS). PS is a rule-based scheduler built around a time-transcending heuristic which attempts to minimize the makespan and meet the due dates. If PS fails to meet the due dates then HS applies a combination of A* and beam search techniques in the space of alternative solutions and returns the best alternative it finds. The emphasis on due dates is a distinctive feature of KBSS. Experience with evaluating the presented scheduling system is reported and discussed. |
| |
Keywords: | |
|
|