A Logic Representation of Manufacturing Control

1. Introduction

Manufacturing planning and control involves managerial decision-making in three main levels of activities: the strategic level of product­ ion and inventory planning; the tactical level of manufacturing operations; and the operation­ al control of processes and material flows. Computerized manufacturing systems (CMS), char­ acterized by multi-purpose, computer-controlled machines connected by automated material handling networks, require a large number of timely decisions to be made at the various levels of operations. See [9] for the inform­ ation and control aspects of such systems. The purpose of this paper is first to explore some typical manufacturing planning and control pro­ blems, particularly those pertinent to the automatic environment, and second, to describe how predicate logic problem-solving methods can be applied to them.

2. Predicate Logic Representation of Knowledge

First-order predicate logic has been used ex­ tensively as a knowledge representation langua­ ge to describe states and problems. Moreover, as shown in [4], predicate logic comprises a programming language for expressing algorithms. Axioms in Horn clause format are interpreted as procedures to be invoked by theorem-proving mechanisms based on Robinson's resolution principle [8]. Deductive query systems such as Chang's [2]. and Minker's [5]combine predicate logic with a data base system for knowledge storage and retrieval. These systems use resolution to partially prove theorems, then in­ voke the data base system to complete the proof. In this paper we demonstrate how a predicate logic representation of knowledge integrated with a data base can be used to model control in a manufacturing environment for the purpose of solving operations management problems.

3. Manufacturing Planning and Control Needs

In the three levels of manufacturing activities previously defined, planning and control are re­ quired in order to achieve efficient, productive utilization of resources to meet a schedule of production demands. Strategic and tactical planning and control have been performed quite successfully with the aid of information system& It is in the operational level of control in which a real-time decision support interface be­ tween managers and machines is lacking, particu­ larly in the CMS environment.

Three operational control issues described in[7] include Part Mix, Part Entry and Assignment, and Process Selection. The Part Mix problem is to select particular sets of parts for sub-periods from the larger set of parts scheduled for pro­ duction in the whole period. The Part Entry and Assignment problem is to sequence individual part entry into the system and assign parts to machines when conflicts occur. The Process Selection problem is to decide which of several alternative processes, all producing the same part but requiring different machines and pro­ cessing times, should be selected for a given part.

While off-line analyses using simulation indic­ ate the importance of such control issues, a different approach is necessary when decisions have to be made and implemented in a real-time environment. In the following sections a new approach is developed, and examples given to illustrate how some of the issues described here are handled.

4. Predicate Logic Representation of Manufac­ turing Control

CMS entities and simple relationships among them are modeled by predicates, which are re­ presented in a network data base system as described in [1]. Complex relationships among the entities are defined by axioms. The axioms extend the data base by supplying procedural knowledge about how the assertional component is used for control tasks.

Many manufacturing control issues require the system status at a given time. Typical inquir­ ies concern what processes are available for each part, what conflicts exist among parts competing for machine servicing, etc. Queries of this type can be handled by problem-solving techniques utilizing a static representation. Generation of the current state of a CMS is done concurrently with actual operation of the manufacturing system by an "operational" mode of the decision support system. Problem-solving on the "operational data base" is performed using a problem-reduction approach [6], in which a problem is given by:

1. a predicate logic goal statement describing the problem to be solved;
2. descriptions of problems whose solution is known, primitive problems;
3. a set of Horn clause axioms, problem­ reduction operators, which transform problems into sub-problems.

A top-down proof procedure is applied to carry out resolution, deriving new goal statements from old ones by applying the problem-reduction operators. The primitive problems obtained are then solved by retrieval procedures that eval­ uate predicates representing assertions in the manufacturing data base.

Control issues in a dynamic domain require a "simulation" mode of the decision support system to forecast future states of the CMS. The predicate TIME(t) is used to denote time, and a state-space approach [6]is used to update the system. The representation of a problem con­ sists of:

1. the operational data base of assertions denoting the initial state;
2. a predicate logic statement of a goal ~;
3. a set of Horn clause axioms, state­ space operators, to transform states into other states.

A bottom-up proof procedure is applied to derive new assertions from old ones. The operators utilize an ADD and DELETE list similar to that used in STRIPS [3] to handle secondary implica­ tions of an operation in addition to tPe conse­ quent in the Horn Clause axiom. The assertions generated for the "simulation data base" are then used as newly solved primitive problems in a top-down theorm-proof. Comparison of criteria across different simulated states determines op­ erational parameters that should be used in the CMS operation over the forecast horizon.

5. Illustrative Manufacturing Control Problems

Table 1 shows a partial list of predicates need­ ed to represent the machines, parts, orerations, etc., and their relationships in a CMS.

Table 1

Computerized Manufacturing System Predicates

Predicates MCH(mch) OPERATION( op) PART(part,part-type) COMPLETE-PART-OP (part,op,t) MCH-OP(mch,op,op-time) PART-ROUTING (part-type,op,next-op)

Interpretation machine 11 mch 11 operation "op" part part I op canplete at t

mch/op process time part routing

The complex relationships are specified by axioms. Problem-reduction operators for the Part Assignment problem determine (1) if the first operation for a part is next to be performed, (2l if a subsequent operation is next, and (3) a possible schedule of a part to a machine for an operation. These three axioms are defined as:

(Al) Yx Vy Vz Vw

• NEXT-PART-OP( part·x ,op·y) + PART(part=x,part-type=z), OPERATION(op·y), PART-ROUTING(part-type·z,op·y), ~PART-ROUTIN�(part-type·z,op=w,next-op·y) ~coMPLETE-PART-OP(part·x,op=y)

(A2) Vx Vy Vz 3w

NEXT-PART-OP( part·x ,op=y) + PART(part·x,part-type·z), OPERATION(op-w), OPERATION(op·y), PART-ROUTING(part-type·z,op·w,next-op=y) PART-ROUTING(part-type·x,op=Y), COMPLETE-PART~OP(part·x,op·w), ~COMPLETE-PART-OP(part·x,op·y)

(A3) Vx Vy Yz

POSSIBLE-SCHEDULE(part·x ,mchay ,op·z) + NEXT-PART-OP(part=x,op·z), MCH-OP(mch·y,op·z)

Wi th these axioms, we can solve a Part Assign­ ment problem such as: "On what machine can part #p2 be scheduled for its next operation?" This problem, expressed as the goal statement:

:ly 3z POSSIBLE-SCHEDULE( part= Np2 ,mch=y, op=z)

is reduced to a set of primitive problems by in­ voking axiom A3, then Al or /!2. A unique "y, z" pair satisfying the primitive problems solves the Part Assignment problem. For multiple "y ,z" occurrences, additional axioms specify the particular machine-operation pair to be chosen.

For simulation, a set of state-space operators describe the operation of the manufacturing system. For example, the end of a machine's operation~erformance is defined by:

END-MCH-OP(mch=x,part=y,op=z,t=t 3 )+

INIT-MCH-OP(mch·x,part=y,op·z,t=t 1 ),

MCH-OP(mch=x,op=z,op-time=t 2 ),

ADD(addendl=t 1 ,addend2=t 2 ,sum·t 3 ),

delete list: INIT-MCH-OP(mch=x,part=y,op=z)

CURRENT-PART-OP(part=y,op=z)

add list:MCH-IDLE(mchax),

COMPLETE-PART-OP(part=y,op=z,t=t 3 )

Using such axioms, we solve a problem useful in Process Selection: "Given a shortest processi~ time scheduling rule, when will part Np2 com­ plete its next operation?" The goal statement:

3z 3w- NEXT-PART-OP(part=#p2 ,op=z),

COMPLETE-PART-OP(part·Np2,op=z,t=w) is solved by first invoking the simulation mode of the decision support system. A bottom-up theorem-proof derives an assertion of the form: COMPLETE-PART-OP(part=#p2,op·Nop ,t=Nt ) z w

in the simulation data base. Axiom Al or P2. is then invoked in a top-down manner to reduce the NEXT-PART-OP sub-problem. Finally, the prim­ itive problems are solved by data base retriev­ al. Simulating the completion time for a number of alternative scheduling rules enables us to select the rule that provides the best value of a criterion measure of performance for com­ pletion of a number of part operations over the simulated time horizon.

6. Conclusions

In this paper we have explored the application of predicate logic and mechanical theorem­ proving to the management of a computerized manufacturing system. Predicate logic permits a descriptive non-procedural representation of knowledge related to the operation of the fac­ ility. The predicate calculus ·language allows both static and dynamically changing knowledge to be modeled, while theorem-proving permits

"new" knowledge to be deduced from the current knowledge base. From a decision support view­ point, the resolution procedure allows the know­ ledge base to be applied to a user's specific manufacturing control problems.

Further work is needed to implement such a system. Questions on how axioms should be stor­ ed and how resolution can be effectively carried out must be investigated. From a user's point of view, a more natural, English-like problem statement language is needed. In addition, relationships between the problem-solving tech­ niques described and classical integer program­ ming models of scheduling would be of interest.

ACXNOWLEDGMENTS

This work supported in part by the National Science Foundation (grant MCS 76-24675 for Com­ puterized Decision Support Systems). Mr. W. Bullers gratefully acknowledges the fellowship s>~pport made possible by a grant from IBM.