KBSS: a knowledge-based job-shop scheduling system*

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.