Division of Research School of Business Administration A KNOWLEDGE-BASED APPROACH TO SELECTION CONSIDERING DUE DATES MANUFACTURING SYSTEMS March 1988 PART TYPE IN FLEXIBLE Working Paper #563 Kathryn E. Stecke Ilyong Kim Moonkee Min University of Michigan

A KNOWLEDGE-BASED APPROACH TO PART TYPE SELECTION CONSIDERING DUE DATES IN FLEXIBLE MANUFACTURING SYSTEMS KATHRYNE.STECKE, ILYONG KIMand MOONKEE MIN Graduate School of Business Administration The University of Michigan Ann Arbor, Michigan Abstract This paper applies artificial intelligence to the short-term production planning function of flexible manufacturing systems(FMSs). A knowledge - based approach is used to solve the part type selection and production ratiodetermination problems. The part type selection problem is to select a subset of the part types that have been ordered to be produced on an FMS, often with due dates and/or production requirements, for simultaneous machining over some upcoming period of time. A knowledge-based system is implemented in the language, Knowledge Engineering Environment (KEE). This system both selects part types and determines their mix ratios under constraints on due dates and tool magazine capacity. Further research needs are also discussed. 1. Introduction A systemic analysis of a manufacturing company shows three interrelated subsystems: management system, physical system, and information system. The management system refers to the managers and their functions at the strategic, tactical, and operational levels. The business tasks of the managers consist of physical activities and information processing activities. The managers delegate their physical activities to the physical system which consists of physical manufacturing facilities and their operators. The managers' information processing activities are supported by the information system. The information system uses models to process data into information useful to the managers so that they can direct the physical system effectively. The growing global market competition and shortened product life cycle have emphasized the need for flexibility as well as productivity in the physical system. A flexible manufacturing system (FMS) is a hightechnology solution to that need, which combines the benefits of a flexible job shop and a highly productive flowshop. The physical system of an FMS comprises computer numerically controlled machine tools served by automated materials-handling equipment and supervised by a computer to ensure practically no set up time wasted between different operations. The flexibility of an FMS allows the concurrent production of several part types through different routes and the production of modified new part types with minimal lead time and cost. To highly utilize the flexibility in the physical system, intelligence in the FMS information system could be useful. Without the help of an intelligent information system, it could be difficult for FMS managers to 1 perform well in dynamically changing FMS operation environments. Their decision making can fail quality and timing goals because of the d i fficu Ity and complexity in FMS operations. An intelligent information system is different from conventional information systems in that it has a knowledge base and an inference

engine as system components in addition to data and models. The knowledge base stores knowledge necessary to solve problems in a certain domain. The inference engine generates inferences and decisions using the stored knowledge to aid or replace human decision making processes. The purpose of this paper is to propose a knowledge-based system, a component of an intelligent information system, which supports FMS managers' decisions on the use of production planning models in dynamically changing system environments. Models are defined here to comprise qualitative human judgments as well as quantitative models such as optimization models, algorithms, and heuristics. Although several OR models and heuristics have been suggested to perform better on FMSs, the effective use of such quantitative models in real FMSs is not a simple task. The quantitative models have different assumptions and input data to generate solutions and may not be understandable to FMS managers. FMS managers usually rely on their judgments and simple analytical methods. For FMS managers to effectively and easily incorporate the solutions of the OR models and heuristics in their judgments, an intelligent information system would be useful. Several studies [BrEL86] [ShCh86] [ThLe86] present knowledge-based approaches to FMS scheduling. Bruno et al. [BrEL871 use production rules to FMS scheduling problems in order to improve the tardiness-based performance. They state that the rule-based system provides FMS schedulers with more transparency, modularity, and flexibility than the previous system written in Fortran. Shen and Chang [ShCh86] suggest frames as a knowledge representation tool for FMS schedule generation. They show a pseudo-code for a frame representation of scheduling algorithms. Thesen and Lei [ThLe86] use production rules to represent some heuristics for dispatching parts to a manufacturing cell. To FMS production planning, however, there is no extensive study using a knowledge-based approach. Before exploiting a knowledgebased approach to FMS production planning including due date information, FMS production planning problems will be reviewed in Section 2. 2. FMS Production Planning According to Stecke [Stec85], FMS production problems can be decomposed into four: 1) design, 2) production planning, 3) scheduling, and 4) control. Design problems include the choice of machine tools and layout, the selection of material handling systems, and the computer control architecture. the production planning problems include five subproblems:part type selection, machine grouping, production ratio determination, resource allocation, and machine loading. The solutions to these planning problems for system set-up provide that all cutting tools required for each operation of the selected part types are loaded into the appropriate machines' limited capacity tool magazines. Once the FMS is set up, FMS scheduling is the next function. This problem include determining of part input sequences and releasing parts into the system. Control problems include monitoring the shop floor situations.

The first subproblem of the FMS production planning function - part type selection problem - is to select a subset of part types that have been ordered, often with production requirements and due dates, for concurrent and actual machining over some upcoming period of time. The objectives of the part type selection problem are to meet due dates (or minimize mean tardiness) while trying to maximize system utilization. Part type selection must satisfy the following constraints: 1) the production requirements of part types should be produced by their due dates; 2) the cutting tools required for all operations of the selected part types are loaded into the appropriate machines' limited capacity tool magazines; and 3) the number of fixtures of each type is limited. The approaches to production planning can be classified into two categories: flexible and batch approaches. A flexible approach [StKi861 to select part types is implemented as follows: when the production requirements of some part type(s) are finished, spaces in tool magazines are freed up. Some new part type(s) can be introduced into the system for immediate and simultaneous machining, if this input can help system utilization. A batch approach [WhGa84] [Hwan86] [Raja86] partitions the part types into separate batches and distinct machining horizons. All production requirements of the selected part types are produced continuously in one batch. The tools are changed for the next batch. For different types of FMSs, either a flexible or batch approach is appropriate. In general, using the flexible approach enables the system to be more highly utilized [StKi87]. Moreover, the flexible approach seems to cope better with due dates, which has not yet been incorporated in the previous studies. There are some situations where the flexible approach to solve the short-term production planning problems is useful: 1) production requirements of some part type(s) are finished; 2) some urgent order arrives; 3) some production orders change; 4) one or more new part types begin production; 5) a machine tool goes down; and 6) preventative maintenance is to be performed. The flexible approach is employed in the design of the knowledge-based system to FMS production planning. 3. A Knowledqe-based Approach to FMS Production Planninq The proposed architecture for an intelligent information system for FMS production planning is shown in Figure 1. The architecture has a knowledge-based system and a data base management system. The knowledge-based system can store and retrieve data about FMS operations in the data base of the data base management system. The knowledge-based system has three components: 1) knowledge base including model base; 2) inference engine; and 3 ) user interface. To design the knowledge-based system, we extract FMS planning knowledge from'FMS managers and FMS modelers. According to Thesen and Lei [ThLe86], the present situation in FMSs differs from other application of knowledge-based systems in two important aspects. First, there are not many expert FMS managers available. Second, the problem is well structured in the sense that it is possible to build simulation models that predict the effects of applying acquired knowledge from FMS modelers. A graphical method, diagram, is used to aid the knowledge acquisition process. The diagram in Figure 2 shows a set of FMS

USERS| ~Knowledge Engineer USERS = ' FMS manager do --- — FMS Modeler KNOWLEDGE-BASED SYSTEM * DATA BASE r__ *M MANAGEMENT a SYSTEM USER INTERFACE ^ ^^,^ USER INTERFACE Graphics, Menu, Goal browser 0 A * INFERENCE ENGINE Inference Control | KNOWLEDGE BASE DATA BASE Frame representation Frame represenation | of Model Base of FMS managers Opt. models Planning < - Heuristics j? --- T Scheduling - Judgments \ Contr0 Selection Production Rules for Modification Model Manipulations ntegraton integ ration Figure 1. Architecture for an Intelligent Information System for FMSs. production planning models connected by input edges and output edges. Input edges are used to represent sets of data necessary to produce information to be stored in output edges. The graphical representation is useful to represent knowledge using knowledge representation methods developed in artificial intelligence such as frames and production rules. Applegate et al. [AKKN85] compare the advantages of each knowledge representation method with regard to the representation of models and model manipulations. A frame is a data structure describing an object or class of objects in a knowledge-based system. Frames are composed of slots which contain declarative and procedural information. Frames are useful for the representation of problems and model characteristics. Production rules are condition-action pairs of the form IF

A Set of Predefined Events Figure 2. Diagram for Production Planning Models. (condition] THEN [action]. The use of production rules in the model manipulations provides a powerful inferencing structure for model selection and query processing. KEE (Knowledge Engineering Environment) is used to prototype the knowledge-based system. The knowledge base in Figure 3 shows framerepresentation of models and FMS problems that FMS managers should deal with. The knowledge base also shows rule-representation of model manipulations. A model is viewed as a frame which has slots for model input data, output data, and model processing procedures. An input data slot is a procedural slot which retrieves the input data from a centralized data base. If the data are not found in the data base, it calls for the execution of other model to get the required data. An output slot contains results of model execution.

LaffRAMMZI BU FOR CAM IS I IXII*S S I UA(LINi.UNLUA1ONj.S AroN r.PIMpN(wNis ^ DILL 1 GUlNSIRAINlU1 OM1R '- QLL Is lo I AIN!DRAL L L 2 UltJ * l:IIt S ' IMUL1 MACHUI Stv- -— M L -. -- MLL2 PALL IS Hf ~*. VT11I VIL -: -- VTL2 P^A1t 1 OU)lPll1 -— PAI1.TYPES: P PART 2 Dt Sl(*N CONTROL PRO.T SSING - OPLAIION1 - -PROWCTONPLANN*G ' SCMEDUUNA MACHIE.QAOLPG / MACHINA.LGOA~M,"#, * B/iALANCEDOYAR'JAX.RA1I10, PAR111A INIO.OE ETElATON // ' - ^UNALANCEM.PART A4X.RATIO 'ALDORWIJMS * * - - PARI.SELECTIN / /' KLHEURISTrC. - f MS PRiltIl IIJN.PL ANNNINl.MlIllf L / RAJAGOPLAN 'WH I NEY XAUL. PART.I YP~.S LEC rPobR H^TA \ 7~ ---JUOOiN1 -~- P^ARl JXJAlO 'vOPTIIlATKONJAOOEl:MWN, - SrEKM QL*U1NGAIETW-RK * As;\ 'SIAUL A TIN RtLSeUthL.ALLOCAMTON INTEGRATION MOWl CAT W R2 RUXE I O MA Nt.MXI't A I)ONIN.tUl f h RULEE2 RULE 3 RULE 4 StLECXtO~IS- - - HUE5 * ' RULES RULE7 JULE 7 Figure 3. Knowledge Base. As an illustration, the unbalanced part mix ratio model has an input slot which retrieves data about selected part types, number of fixtures available, processing time requirements, and relative workloads. The unbalanced part mix ratio model executes a closed queueing network model, CAN-Q [Solb77], to calculate the relative target workloads which provide the maximum expected production. The part mix ratios from the execution of the unbalanced part mix ratio model are stored in the output slot. The model processing slot contains procedures to call external solution packages such as LINDO [Shra81]. Model manipulations are represented in production rules. The production rules include selection rules, integration rules, and modification rules. The selection rules represent model selection procedures to provide the user with an appropriate model to solve problems. If there is not an appropriate basic model in the model base, the knowledge-based system is able to integrate a new model using existing basic models. Modification rules describe how models can be

dynamically changed. Especially, models for adjusting part mix ratios can be modified by learning, based on data about their historical and statistical performances in the specific FMS environment. Synthesis of knowledge representation methods - frames and production rules - is achieved by an object-oriented view, where both frames and rules are considered as objects. KEE allows production rules to be stored within and activated from frames to make inferences. The strength of an object-oriented view lies in its ability to represent models and their interactions in cogent form, i.e., objects. It provides "inheritance" of attributes of models. It also can represent interactions among models by "messages" sent between them, which provides a natural way of representing the interactions. The following sample session shows a sequence of fired production rules of which the IF CONDITIONS are met when an urgent order arrives. It also demonstrates the "message sendings" between the objects (boldface) in the knowledge-based system. IF < Some urgent orders arrive > THEN < The stage of OPERATION is part priority determination > < Send a message to FMS.CONSTRAINTS to update due dates, processing times, and production requirements > IF < The stage of OPERATION is part priority determination > THEN < Send a message to MODIFIED.DUE.DATE.HEURISTICto determine priorities of parts > < The stage of OPERATION is part selection > IF < The stage of OPERATION is part selection > THEN < Send a message to FMS.CONSTRAINTS to update available machines and tool magazine capacity > < Send a message to PART.SELECTION.ALGORITHM to select a subset of part types for simultaneous processing > < The stage of OPERATION is part mix ratio determination > IF < The stage of OPERATION is part mix ratio determination > AND < The size of groups of pooled running machines is unequal > THEN < Send a message to FMS.CONSTRAINTS to update the number of fixtures available > < Send a message to UNBALANCED.PART.MIX.RATIO.MODEL to determine mix ratios > < Send a message to CAN-Q to determine relative workloads > < The stage of OPERATION is part mix ratio evaluation > IF < The stage of OPERATION is part mix ratio evaluation > THEN < Send a message to SIMULATION.MODEL to estimate mean tardiness and system utilization > < The stage of OPERATION Is part mix ratio judgment> IF < The stage of OPERATION is part mix ratio judgment > THEN < Send a message to JUDGMENT to examine whether mean tardiness and system utilization are improved > IF < Mean tardiness and system utilization are Improved based on JUDGMENT> THEN < Send a message to UNBALANCED.PART.MIX.RATIO.MODEL to determine new part mix ratios > IF < Mean tardiness and system utilization are not Improved based on JUDGMENT> THEN < Return the selected part types and mix ratios to the system user >

4. Conclusions and Future Research This paper proposes a knowledge-based system, a component of an intelligent information system, to the part type selection/production ratio problems at the FMS production planning stage. KEE is used to prototype the knowledge-based system. The knowledge-based system incorporates due date information in the production planning stage. The information has usually been considered in the scheduling stage. A machine learning mechanism is considered to make the proposed knowledge-based system truly intelligent. Especially, the learning mechanism helps compare the alternative part mix ratios by observing historical data concerning previous judgments and by analyzing and learning from such experiences. The proposed knowledge-based approach for FMS operation also has the following advantages: 1) integration, 2) transparency, and 3) modularity. The knowledge-based approach provides FMS users with an integrative view of solution over different problem domains such as production planning, scheduling, and control. The knowledge-based approach provides a transparency and coherence in the representation of different types of models. The knowledge-based approach provides modularity in the use of the knowledge for FMS operations. Modularized production rules and frames can be easily added, modified, and deleted from the knowledge-based system. To evaluate the performance of the suggested knowledge-based system, a simulation model will be written in a knowledge-based simulation language such as SIMKIT. Simulation results will show how much the performance of the FMS is enhanced by applying artificial intelligence to the information system for FMS production planning. There are further research needs along these lines. This study should be extended to the subsequent production planning problems such as grouping and loading problems. Also, the proposed knowledge-based system for production planning problems should be integrated with those for FMS scheduling and control to help operate an FMS on-line. References [AKKN85] Applegate, L.M., Klein, G., Konsynski, B.R. and Nunamaker, Jay F., "Model Management Systems: Proposed Model Representations and Future Designs, " Proceedings of the Sixth International Conference on Information Systems, Lynn Gallegos, Richard Welke, and JamesWetherbe, Indianapolis, pp. 1-16, December 1985. [BrEL86] Bruno, Giorgio, Elia, Antonio, and Laface, Pietro, "A Rule-based System to Schedule FMS Production," Computer, Volume 19, Number 7, PP. 32-40, July 1986. [Hwan86] Hwang, Syming. "A Constraint-Directed Method to Solve the Part Type Selection Problem in Flexible Manufacturing Systems Planning Stage," Proceedings of the Second ORSA/TIMS Conference on Flexible Manufacturing Systems: Operations Research Models and Applications, Kathryn E. Stecke and Rajan Suri (Editors), Ann Arbor

Ml, Elsevier Science Publishers B. V., Amsterdam, PP. 297-309, August 1986. [Raja86] Rajagoplan, S. "Formulation and Heuristic Solutions for Parts Grouping and Tool Loading in Flexible Manufacturing Systems,' Proceedings of the Second ORSA/TIMS Conference on Flexible Manufacturing Systems: Operations Research Models and Applications, Kathryn E. Stecke and Rajan Suri (Editors), Ann Arbor Ml, Elsevier Science Publishers B. V., Amsterdam, PP. 311-320, August 1986. [Schr81] Schrage, Linus E. Linear Programming Models with LINDO, The Science Press, Palo Alto CA, 1981. [ShCh86] Shen, Sheldon and Chang, Yih-Long, "An Al Approach to Schedule Generation in a Flexible Manufacturing System,' Proceedings of the Second ORSAITIMS Conference on Flexible Manufacturing Systems: Operations Research Models and Applications, Kathryn E. Stecke and Rajan Suri (Editors), Ann Arbor Ml, Elsevier Science Publishers B. V., Amsterdam, PP. 581-592, August 1986. [Sol b77] Solberg, James. J. "A Mathematical Model of Computerized Manufacturing Systems," 4th International Conference on Production Research, Tokyo, Japan, pp. 22-30, August 1977. [Stec86] Stecke, Kathryn. E. "Design, Planning, Scheduling, and Control Problems of Flexible Manufacturing Systems, " Annals of Operations Research, Vol. 3, pp. 3-12, 1985. [StKi86] Stecke, Kathryn. E. and Kim, llyong. "A Flexible Approach to Implementing the Short-Term FMS Planning Function," Proceedings of the Second ORSAITIMS Conference on Flexible Manufacturing Systems: Operations Research Models and Applications, Kathryn E. Stecke and Rajan Suri (Editors), Ann Arbor Ml, Elsevier Science Publishers B. V., Amsterdam, PP.311-320, August 1986. [Stki87] Stecke, Kathryn. E. and Kim, llyong. "A Study of FMS Part Type Selection Approaches for Short-term Production Planning," International Journal of Flexible Manufacturing Systems, forthcoming 1987. [ThLe86] Thesen, Arne and Lei, Lei, "An Expert System for Scheduling Robots in a Flexible Electroplating System with Dynamically Changing Workloads, Proceedings of the Second ORSA/TIMS Conference on Flexible Manufacturing Systems: Operations Research Models and Applications, Kathryn E. Stecke and Rajan Suri (Editors), Ann Arbor Ml, Elsevier Science Publishers 8. V., Amsterdam, PP. 555-566, August 1986. [WhGa84] Whitney, C.K. and Gaul, T.S. "Sequential Decision Procedures for Batching and Balancing in FMSs: Proceedings of the First ORSA/TIMS Conference on Flexible Manufacturing Systems: Operations Research Models and Applications, Kathryn E. Stecke and Rajan Suri (Editors), Ann Arbor Ml, PP. 243-248, August 1984.