Flexible manufacturing system (FMS) scheduling using filtered beam search

This paper reports our effort to develop a knowledge based system for scheduling jobs in a flexible manufacturing system (FMS). We view FMS scheduling as a two-stage process: static scheduling, followed by real-time rescheduling if unanticipated events were to occur. This paper deals with the static scheduling stage. The system uses a frame-based knowledge representation scheme and a problem-solving strategy based on filtered beam search. Filtered beam search views a scheduling problem as a state space search and generates a 'good' schedule quickly by controlling the amount of search required. Evaluation functions are used to decide which branches are the most promising. An important feature of this system, in our view, is the explicit manner in which environmental, procedural and structural knowledge, (stored in the knowledge base using a frame-based scheme) can be used to improve the quality of the generated schedule. The system has been implemented and tested using Common Lisp on a Macintosh system with a 3MB main memory and a 40MB hard disk. Computational experience with our system is reported.