A knowledge-based system for scheduling in a flexible manufacturing system

A knowledge-based system is developed to generate detailed production schedules for a flexible manufacturing system (FMS) featuring flexible routings for jobs that are partially ordered. Most of the earlier research has focused on FMSs that perform non-assembly operations, especially machining, while assembly-type operations have either not been considered, or treated independently. The knowledge-based system considers these two types of operations in an FMS simulaneously and investigates the scheduling issues involved. In addition, earlier research on FMS scheduling does not take into account the alternative routing of jobs during the scheduling process presumably to avoid the computational overhead that results from this added dimension of complexity. Routing flexibility is considered here but the resulting computational burden is reduced by using a search strategy which uses knowledge from the knowledge base to determine the most promising branches. Only a static scheduling problem is solved in this thesis.; There are two aspects to the scheduling system: a knowledge representation scheme based on frames and a solution mechanism which takes advantage of this frame-based knowledge. The system is used to address two scheduling problems. The first problem can be characterized as a single-stage scheduling problem with linear precedence constraints and general resource structure (SSP). Knowledge stored in the knowledge base is used by a heuristic search strategy called filtered beam search to limit the search space to a manageable size so that a good schedule can be produced in a reasonable time. The next problem is a generalization of the first one in that the job independence assumption is relaxed. It can be characterized as a multi-stage scheduling problem with general precedence constraints and general resource structure. A three-phase solution strategy is used to decompose the problem into a number of SSPs for detailed scheduling, which is followed by a past-analysis. The system has been implemented and tested using Common Lisp on a Macintosh Plus with 3MB main memory and 40MB hard disk. The advantages and versatility of using a knowledge-based approach to solve these FMS scheduling problems are explored.