The evolution to CIM has been slower than expected.
This can be directly attributed to high software development
and maintenance costs and the difficulty in achieving the required
levels of integration between systems. These problems are especially
evident in the development of the shop floor control system (SFCS).
Many researchers have developed "standard" CIM architectures.
However, these structures are often verbose, textual descriptions
which are ambiguous and lack formality. This makes descriptions
based on these architectures unsuitable as a basis for control
software development. Furthermore, without a formal language
for describing manufacturing systems, it is difficult for researchers
to discuss and compare different system configurations. In light
of these problems, this paper identifies a formal structure for
shop floor control. The formal structure is based on a three-level
hierarchical control architecture. The purpose of this structure
is to allow manufacturing systems to be described completely and
unambiguously. This description can then be used as a basis for
control software development, which will simplify the implementation
of automated CIM sytstems.
Keywords: Shop floor control, Flexible Manufacturing Systems, Computer Integrated Manufacturing, Control architecture, Formal Model
Computer Integrated Manufacturing (CIM) has recently received a great deal of attention as an effective strategy to improve manufacturing responsiveness and quality. CIM seeks to integrate the entire manufacturing enterprise using a network of computer systems. However, the evolution to CIM has been slower than expected. This can be directly attributed to the high software development and maintenance costs and the difficulty in achieving the required levels of integration between systems (Ayres, 1989; Merchant, 1988). These problems are especially evident in the development of the shop floor control system (SFCS). The SFCS is responsible for planning, scheduling, and controlling the equipment on the shop floor.
In order to define the requirements for system control many researchers have developed "standard" CIM and FMS control architectures (Beechman, 1989; Jones and McLean, 1986; Jones and Saleh, 1990, Joshi et al. 1990; Senehi et al., 1991). These architectures attempt to identify a standard structure for computer controlled manufacturing systems. However, these architectures have not been defined in sufficient detail to address the software development and maintenance problems associated with the implementation of a SFCS (Ayres, 1989; Mettala, 1989). In fact, control systems still appear to be extremely implementation specific even if the designers adhere to one of the "standard" architectures. One explanation for this is that most of these architectures are simply verbose, textual descriptions of the manufacturing system's general structure and there is no concentration on the development of the required control systems. Consequently, these descriptions are often ambiguous and incomplete, and, hence, are inappropriate as a basis for software development. In addition, it is difficult for researchers to discuss and compare different system configurations without a standard "language" for describing the manufacturing systems.
We propose to integrate the system design and software development phases of SFCS implementation. Our research has been focused on creating a shop floor control software development methodology using Computer Assisted Software Engineering (CASE) tools. This methodology will reduce controller software costs while also providing improved levels of manufacturing system integration. The improvements in system integration stem from the formal descriptions of the components. Once the individual components' behavior is completely defined, the interactions between individual components can be formalized. This concept is illustrated in Figure 1. Within this paradigm, the control architecture provides the formal structure under which the specific implementation can be described. This formal description can then be used as a basis for control software development. In order to develop these tools, we have found it necessary to extend the traditional shop floor control architecture to include formal definitions of the individual components of the architecture. In this context, the term formal implies precise and unambiguous.
Figure 1. Generation of shop floor control software.
The formal definitions of the shop floor configuration are used as input to a software generation system and provide a means to describe different shop floor systems for comparisons. The software generation system is based on a formal model of the control requirements (Smith, 1994b), and a C++ class library implementing the details of the individual controllers (Smith, 1994). These two components supply the control model and software generator illustrated in Figure 1. This paper presents the extended control architecture required to generate the implementation specific description of a system that serves as the input. The control architecture presented here is not a unique solution to the problems described. Instead, it illustrates that there is a formal language in which control architectures can be expressed which allows for construction of generic controllers. The development of these controllers has been demonstrated in two laboratories and is described in detail by Smith (1992) and Smith and Joshi (1994, 1994b).
The target manufacturing environment is characterized by having a large number of distinct part types and low production volumes, approaching single part production. Furthermore, processing is performed on general purpose machine tools without requiring extensive setups or changeovers. Shop floor control in this environment is an extremely broad topic. A complete description of all facets of this problem would fill an entire book. This paper seeks to identify a detailed architecture for shop floor control which facilitates the automatic or semi-automatic generation of a significant portion of the control software. The rest of this paper is organized as follows. Section 2 provides a brief background on control architectures. Section 3 describes the proposed architecture and controller structure. Section 4 describes a methodology for SFCS development which is based on the proposed structure.
In the context of shop floor control, a control architecture should provide a blueprint for the design and construction of a SFCS. It should completely and unambiguously describe the structure of the control system as well as the relationships between the system inputs and the system outputs. Albus et al. (1981) describe a hierarchical robot control system and identify three basic guidelines for developing manufacturing control hierarchies: (1) Levels are introduced to reduce complexity and limit responsibility and authority, (2) each level has a distinct planning horizon which decreases as you go down the hierarchy, and (3) control resides at the lowest possible level. The robot control system introduces the concept of integrating hierarchically decomposed commands from higher levels with status feedback from lower levels to generate real-time control actions.
The National Institute of Standards and Technology (NIST) has been developing an Automated Manufacturing Research Facility (AMRF) since 1981. The purpose of the AMRF is to provide a testbed for research directed towards the development of standards for use in flexible manufacturing (Jones and McLean, 1986; Simpson et al., 1982). As a part of their research, a hierarchical control architecture has been developed. A new project at NIST called the Manufacturing Systems Integration (MSI) project has been established to refine and extend the original NIST architecture work (Senehi et al., 1991). One of the main contentions of the MSI group is that the five level hierarchy imposed by the original NIST architecture is too rigid in structure. In response, the new MSI architecture only defines three types of controllers: equipment, workcell, and shop. A hierarchical structure of arbitrary depth can be constructed using these three types of controllers. However, the primary concern in the MSI project has been to develop standards for system (i.e. controller) interconnection. There has been little work reported on methods for system development and implementation.
One of the primary limitations of the original NIST implementation is the lack of sophisticated planning and scheduling at the lower levels in the hierarchy (Jones and Saleh, 1990). As a result, there are essentially only two distinguishable layers. One to do the decision making and one to do the control. As a result of these inherent problems, Jones and Saleh (1990) propose a so-called "multi-level/multi-layer" control architecture. The structure of this architecture is based on both spatial and temporal decompositions of the system. An important aspect of this architecture is the decomposition of the control tasks at each level into adaptation, optimization, and regulation functions. Joshi et al. (1990) present a three level hierarchical control model based loosely on the lower three levels of the original NIST hierarchy. According to this "scaleable architecture," the tasks for each controller are separated into planning, scheduling, and control tasks. These tasks are similar to the adaptation, optimization, and regulation functions described by Jones and Saleh.
Judd et al. (1990) describe a methodology and a related set of tools for developing manufacturing system control software. These tools have been developed based on early work by Naylor and Volz (1987) dealing with the development of integrated manufacturing control software. In this work, they introduce the notion of a software/hardware component as an integrated assemblage of a machine and the control software for that machine. Judd et al. (1990) have extended this concept and created the formal specifications for these components. This formal machine control specification is critical in the development of integrated systems, however, this work concentrates only on the low-level physical control and does not yet consider the higher-level planning and scheduling aspects of an integrated manufacturing system. Related work dealing with these planning and scheduling aspects within the software/hardware component concept is described by Chaar (1990).
Recently, several researchers have expressed concern over the rigidity of the hierarchical structure. Hatvany (1985) points out the need for a new type of manufacturing control model which will: 1) permit total system synthesis from imperfect and incomplete descriptions, 2) be based on the automatic recognition and diagnosis of fault situations, and 3) incorporate automatic remedial action against all disturbances and adaptively maintain optimal operating conditions. Duffie and Piper (1987) present a part-oriented heterarchical control system in which each individual part and machine is represented by a system entity. Part entities have knowledge about the processing that they require and machine entities have knowledge about the processing that they can perform. Part entities "broadcast" processing requirements over the system network and machine entities similarly broadcast processing availability. When a match is found, the part and machine entities negotiate and, once an agreement is made, the part is transported to the machine and processing begins.
Upton et al. (1991) present some preliminary results in the use of heterarchical systems for manufacturing system control. The results are based on a simulated manufacturing system with a standard part flow and multiple possible machines (each with a different processing time for similar parts). Upton et al. point out that, based on the simulations, the distributed architecture dispatches jobs as a centralized controller might: using the best machines when idle, and progressively less effective machines when busier. Upton et al. state that further research in process planning, communications, and on-board information processing is required in order to make the heterarchical architecture feasible for shop-floor control. Lin and Solberg (1992) also describe a "market-based" heterarchical control system based on autontomous agents. This model uses a pofit-directed mechanism for component negotiation.
Ostroff (1990) describes a temporal logic based controller for real time discrete event processes. Based on the characteristics for these processes, small to medium discrete parts manufacturing environments are certainly within this domain. Furthermore, Ostroff goes on to describe some of the benefits of a formal framework for these systems:
It is precisely these benefits that we seek. However, a necessary precursor to development of formal functional characterization of shop floor control is the definition of terms, and the description of the structure of the control system to which these techniques will be applied. Laying this foundation is the topic of this paper.
The architecture described in this paper follows the hierarchical model. Although the heterarchical model has some intuitively appealing characteristics, the predictability system behavior is questionable and more research and experimentation is required in order to prove its stability and benefit. The architecture for a hierarchical system must describe the decomposition of the system into individual subsystems and provide functional decompositions of these subsystems. The architecture should also provide the guidelines necessary to develop these subsystems so that they can be transparently integrated into the larger system. The primary goal of a hierarchal structure is to develop systems whose subsystems are completely independent so that individual components can be developed at different locations (e.g. by different vendors) and can be replaced or updated as necessary without adversely affecting the rest of the system.
Among existing hierarchical architectures there is
much debate over the required number of distinct levels. We identify
three "natural" levels (which are generalized from Joshi
et al. (1990) and Jones and Saleh (1990)): From the bottom
of the hierarchy to the top (as shown in Figure 2) are the equipment,
workstation, and shop levels. The equipment level is defined
by the physical shop floor equipment and there is a one-to-one
correspondence between equipment level controllers and shop floor
machines. The workstation level is defined by the layout
of the equipment. Processing and storage machines that share
the services of material handling machine together form workstations.
Finally, the shop level acts as a centralized control
and interface point for the system. The primary responsibility
of the shop controller is to provide the centralized access to
the shared resources in system.
These descriptions of each level are virtually identical to those descriptions provided by Jones and McLean, 1986; Jones and Saleh, 1990; Joshi et al., 1990; Simpson et al. 1982; and others. However, while these qualitative descriptions of each level provide a conceptual view of the hierarchical decomposition, they do not provide the specific details required to formalize the control software requirements for control systems based on these architectures. In order to facilitate software generation (automatic generation, in particular), more detailed descriptions of the decomposition and of the individual levels are required. Providing these detailed descriptions is the primary objective of this paper. After a describing a set of preliminary definitions, each level in the control hierarchy will be formally defined.
A part is an individual item that is to be produced by the manufacturing system. While a part is logically an individual item, it may actually be an assembly or fabrication composed of other parts. In the production system, each part will have several administrative attributes. Some of these include the part type, part number, due date, customer number, etc. A part will also have a set of technical attributes which describe the part and define the required manufacturing operations. These technical attributes are used to create a process plan for the part. A process plan provides the processing instructions necessary to produce the part. The representation of a process plan used in this research is a directed graph that shows the precedence constraints and alternative routings for the part as paths through the graph (see Figure 3). Each node in the graph represents a specific operation or set of operations performed by a machine or group of machines. Each arc represents the movement of the part from the machine represented by the tail node to the machine represented by the head node. Any path through the graph represents a feasible processing route for the part. Therefore, by assigning processing costs to each node and transport costs to each arc, the total cost for each routing alternative can be determined. The graph can be also hierarchically constructed to show various levels of detail. These levels map directly to the control levels in the proposed architecture. This representation is a simplified view of those described by Mettala (1989) and Catron and Ray (1991).
Figure 3. Process plan representation.
We also introduce the concept of a part group. A part group is a group of parts which is handled as a single entity. For example, several parts can be attached to a multi-part fixture for transport and/or processing. In this context, the parts and the fixture together constitute a part group. Part groups correspond to the smallest units which are assigned to a controller's subordinates. For example, consider the case where a pallet of parts is removed from a storage device, placed on an AGV, and delivered to a workstation for processing. Once at the workstation, the individual parts are removed from the pallet, processed by the machines in the workstation, and placed back on the pallet. From the storage system and AGV points of view, the parts and the pallet together constitute a part group since the parts are not separated from the pallet. However, from the workstation point of view, they do not constitute a part group since the parts are removed from the pallet and processed individually. Assemblies are special cases of part groups which are not separated (unless rework is required). An important property illustrated by the assembly and disassembly cases, is that part groups can be dynamically created and destroyed by different controllers. In its simplest form, a part group is one or more items being processed, handled, or transported as a unit.
A production system is made up of several machines. We identify several classes of machine based on the machines' behaviors. This classification of equipment has led to the development of a C++ controller class that is used to simplify controller implementation (Smith and Joshi, 1994). The equipment classes are material processing, material handling, material transport, and automated storage. All machines in the factory are classified as belonging to one (and only one) of these classes. These machine classes are described in Section 3.2.
Controllers at all levels in the hierarchy will also require access to various types of information while the system is running. This information includes part process plans, NC files, and machine status reports. Jones and Saleh (1990) describe three possible methods for providing access to this data: (1) each controller receives the data from its supervisor as part of the command structure; (2) each controller has its own database management system; and (3) each controller must have an interface to a global CIM database management system. They go on to outline the rationale for selecting the third option, and propose the use of a commercially available client/server database system. We agree with this assessment and are working towards this goal. Our current implementation, however, uses a combination of the first two options.
Within the control hierarchy shown in Figure 2, the
equipment level in the hierarchy represents a logical view of
a machine and an equipment level controller (see Figure 4).
Informally we will refer to an equipment level controller and its subordinate machine as simply a piece of equipment. As shown in Figure 4, individual pieces of equipment also have machine controllers which provide physical control for the devices. These include CNC controllers, programmable controllers, and other motion controllers and are usually provided by the machine tool vendors. Equipment controllers provide a standard interface (based on the equipment type) to the rest of the control system. This interface hides the implementation-specific code required for machines from different vendors. An equipment level controller makes decisions regarding local part sequencing, keeps track of part locations, and monitors the operation of the machine under its control. Formally, the equipment level is defined as follows.
E = {e1, e2, ..., em}, is an indexed set of controllable equipment, where:
ej Î E
ej = áECj , Djñ where:
ECj is an equipment controller, and
Dj is a physical device (with device controller).
E is partitioned into {MP, MH, MT, AS} where:
MP = {ej ½ Dj is a material processors},
MH = {ej ½ Dj is a material handler},
MT = {ej ½ Dj is a material transporter}, and
AS = {ej ½ Dj is an automated storage device}.
The class of material processors includes machining centers, inspection devices, assembly machines, and so on. The key factor in placing a machine in this class is that the machine has the ability to autonomously "process" a part in some way as indicated in the process plan. By "processing," we mean any activity that results in a change in the information content associated with the physical state of the part. For example, a turning center, a coordinate measuring machine, and a painting booth are fundamentally different in terms of their processes, but from a control point of view, each of these simply process parts according to some set of instructions described by the process plan. Based on the capability for local storage, each piece of equipment has a maximum capacity, indicating the maximum number of parts that can be assigned to that device at one time. Each unit of the capacity is designated as a location. A location can be addressable or nonaddressable. An addressable location is reachable by an external device (e.g., a robot or an operator), whereas a non-addressable location can only be used by the machine itself.
The class of automated storage machines is made up of various AS/RS type devices. A piece of automated storage and retrieval machinery may store raw materials, work in process, finished parts, tools, or fixtures. Objects are stored in locations known to the AS/RS controller. Storage machines can deliver any stored object to a load/unload point and can retrieve any object from a (possibly different) load/unload point and place it in storage. Similar to previous machines, automated storage machines have a capacity, which consists of addressable and non-addressable locations. In general, the capacity of an automated storage device is much greater than the number of addressable locations.
Machines used for moving objects within the manufacturing shop are separated into two classes. The class of material handling machines is made up of robots, indexing devices, and other devices capable of moving parts from one location to another in a specified orientation. These locations are typically close together relative to the size of the factory. The primary function here is to load (unload) parts into (from) various material processors and automated storage machines. An individual piece of material handling machinery may have a capacity greater than one part by having multiple part holding attachments (i.e. grippers).
The class of material transport machines is made up of AGV's, conveyors, fork trucks, and other manual or automated transport machines. The primary function of these machines is to transport parts to various locations throughout the factory. The distinction between material handling machines and material transport machines is that material handling machines can load and unload other equipment, and material transport machines can not. Typically, material handling machines perform intra-workstation part movement functions and material transport machines perform inter-workstation part movement functions (workstations, as used here, are defined in Section 3.3). A specific type of material movement machine (e.g. a conveyor or a robot) could belong to either class, but within a particular system, each specific device (e.g. conveyor #8 or the Puma robot) will be considered either a material handler or a material transporter, but not both. Associated with each material transport device is set of ports. A port is a location at which the individual transport device may stop to be loaded/unloaded. An example of a port is an AGV station where individual AGVs stop to be loaded and unloaded at a workstation. An individual port may be shared by several material transport devices. The set of all ports in the shop will be designated as PO.
Additionally, we defined the following sets of noncontrollable equipment, which require no machine controller:
BS = {passive buffer storage units},
PD = {passive devices}.
The class of buffer storage units is made up of groups of passive storage locations to which a piece of material handling equipment has access. Buffer storage has a maximum capacity. We define a passive device as a special case of a material processor which requires no machine level controller and a has a deterministic processing time. An example of a passive device is a gravity-based device used to invert a part between successive turning processes to allow turning on both ends of the part. A buffer storage device is distinguished from a passive device by the fact that a passive device explicitly appears in the sequence of required operations for the part, and buffer storage is an optional operation performed between any two required operations.
To process a part, the equipment follows an equipment level process plan. The equipment level process plan is the lowest level in the hierarchical decomposition of a process plan (shown in Figure 3). Each node in the process plan graph represents an operation performed by a specific equipment level device and contains the information required by the machine to process the part. In the case of an NC machine tool, this might include the machining parameters such as speeds, feeds, tool selections, tool paths, and so on. In some cases, an additional decomposition might be required within the equipment controller to convert the processing instruction data into a form directly usable by the specific machine controller. For example, if a machine tool controller requires instructions in CLDATA format and the processing instructions data are stored in the form of a CAD file, a CAD-to-CLDATA conversion would be required. These conversions are performed by an external function (illustrated as the Convert File block in Figure 4) called by the equipment controller.
A workstation is made up of one or more pieces of equipment under the control of a workstation level controller. Workstations are defined using the physical layout of the equipment and are generally configured so that multiple MP devices can share the services of one or more MH devices and/or ports. We wish to create an indexed set of workstations, W = {W1, W2, ..., Wn}. To accomplish this, the sets MP, MH, MT, AS, BS, and PD are each partitioned into subsets indexed by i = 1,2,...,n, corresponding to the indexing of W. For example, MP is partitioned into {MP1, MP2, ..., MPn}. PO is separated into (not necessarily disjoint) indexed sets PO1, PO2, ..., POn, that together cover PO. A workstation, Wi, is then defined formally as:
Wi Î W
Wi = áWCi, Ei, BSi, PDi, POiñ where:
WCi is a workstation controller, and
Ei = {MPi È MHi È MTi È ASi}.
The workstation controller carries out commands received from the shop controller and is responsible for moving parts between the various pieces of equipment in the workstation and for specifying part processing performed at this equipment. To this end, it will synchronize the actions required for coordinating the transfer of parts between processing equipment and material handling equipment. Since the individual equipment controllers are responsible for sequencing their tasks once the tasks have been assigned by the workstation controller, the workstation is not responsible for loading, starting, and monitoring the operation of the machine directly. Instead, parts are "assigned" to the equipment controller which specifies a "delivery location" for the parts. Once the parts have been delivered, they are out of the direct control of the workstation. At some later time, the equipment controller informs the workstation controller that the processing of the parts has been completed and provides a "pickup location" for the parts. A mechanism for formally specifying the controller dialogue is presented by Smith and Joshi (1994b).
A synchronization may also be required between the material handling equipment and a material transport device present at a port to deliver or remove parts. This would occur when parts are transported on fixtured pallets, for example. In this case, the communication required for the synchronization will be with the shop controller rather than with the material transport device directly.
We identify three classes of workstation: processing workstations, transport workstations, and storage workstations such that W = {WP È WT È WS}. A processing workstation is a workstation that is made up of one or more material processors (MP), and optionally, one or more pieces of material handling equipment (MH), one or more buffer storage devices (BS) or AS/RS (AS). An implicit assumption is that all addressable locations of the AS and BS devices and the ports within the workstation are accessible to at least one of the MP devices. This access is typically provided by a MH device which is used to load and unload the material processors. However, in some instances, processing can be performed while the parts are at the port (e.g. a welding operation performed by a robot on parts moving on a conveyor line). Processing workstations perform all of the value-added processing required to transform raw materials into finished products.
When a part enters a processing workstation, it follows a workstation level process plan. This lists the various pieces of equipment in the workstation that the part must be sequenced across and the order that operations must occur. In the general case, a workstation level process plan may include alternative routings for a part. Each of these alternate routings can be viewed as a path through the workstation process plan graph. A workstation level process plan is a particular view of the equipment process plan which includes only the equipment within the specific workstation (as shown in Figure 3).
A transport workstation is a workstation which is made up of one or more material transport devices (MT) and provides material transport services to the other workstations in the shop. A transport workstation might also include one or more MH devices for transferring parts from one MT device to another within the transport workstation. The purpose of the transport workstation is to integrate (possibly) many different material transport devices into a single system so that the Shop controller (described in Section 3.4) does not need to be concerned with which particular device will transport particular parts. Instead, the Shop controller will simply request that objects be moved from a specified location to another specified location. Based on this request, the transport workstation will determine a set of feasible routes (each of which might contain multiple transport segments) to perform the move. The Shop controller will then evaluate the alternatives and instruct the transport workstation on which move to perform. The use of a transport workstation will also localize the effects of the introduction of new or modified transport devices/systems on the control system.
Similarly, we define a storage workstation to integrate several material storage devices which are not assigned to particular processing workstations. The storage workstation might also include MH devices for loading [unloading] parts, tools, fixtures, etc. to [from] the storage device. The storage workstation provides a centralized interface to a distributed storage system, and, similar to the transport workstation, will localize the effects of the introduction of new or modified storage devices on the control system.
The shop includes all workstations and is responsible for selecting the part routes (at the workstation level) and for communicating with the workstations for transport and storage services used to move parts, tools, fixtures, etc. between workstations. The shop level is also the primary input point for orders and status requests and, therefore, has significant interaction with humans and external computer systems. The shop level must also split part orders into individual batches to meet material transport and workstation capacity constraints.
Since all of the components of the shop have been defined, we can formally define a shop, S as follows:
S = áSC, Wñ where:
SC is a shop controller, and
Furthermore, we impose the following constraints on S :
½W½ > 0, and
È {POi ½ Wi Ï WT} = È {POi ½ Wi Î WT}.
The first constraint assures that there will be at least one workstation in the shop. The second constraint assures that the ports in the processing and storage workstations are the same ports that are in the transport workstation (this assures that the processing and storage workstations are reachable by the equipment in the transport workstation). The shop controller uses the shop level process plan graph for planning and scheduling (see Figure 3). The shop level graph is generated by aggregating the individual workstation graphs into single nodes on the equipment level graph.
One of the primary functions of the Shop controller is to provide centralized access to shared resources. A shared resource is some resource that is used by several independent entities within the SFCS. Since the production requirements and part routes change frequently in the target environment, it is necessary to have transport capabilities between every pair of workstations within the shop. Similarly, it is important to have storage facilities to decouple the processing workstations. These functions are performed by the transport and storage workstations described in Section 3.3. However, since these resource are shared, seizure of these resources by one workstation may affect other workstations in the shop. This also applies to the use of centralized tool and fixture management systems. Therefore, global knowledge is necessary in order to effectively distribute or schedule access to these shared resources.
For example, consider the case where a new part is to be processed. The first step is to remove the raw materials from the storage workstation and transport them to the first processing workstation in the processing route. In the general case, the required raw materials could be stored in several storage facilities distributed throughout the facility. The transport times from each of these locations to the specified processing workstation will be different and will depend on the state of the transport system. Therefore, neither the storage workstation or the transport workstation alone has sufficient information to make decision as to which storage facility the part should be removed from. Instead, the Shop controller receives the raw material locations from the storage workstation and the transport details from the transport workstation and makes a decision specifying a particular storage location and transport route. Identical situations exist in the transport of tools and fixtures.
Because of the complexity the material transport task, it is expected that the material transport activities will be managed rather than scheduled. In this mode of operation, requests to the transport system are handled on a first come first serve basis (although preemption is allowed), and the transport times are stochastic and are based on the current state of the transport system as a whole. That is, in terms of the traditional view of production scheduling, processing equipment is scheduled based on sequences of processes and their associated processing times. This is contrasted with the techniques used to dispatch material transport devices to service the shop once the schedule has been determined. The assumption is that there is an adequate capacity of transport equipment, and that this capacity has been managed at a level that can support any reasonable production schedule.
Figure 5 shows a layout and the corresponding formal description of the Penn State CIM Lab. This facility includes nine pieces of equipment partitioned into fove workstations. Workstation controllers are responsible for directing the operation of their subordinate equipment controllers. Interactions between workstations are controlled by the shop. Two workstations can interact only if they share common ports.
| Shop Level:
S = <SC, WP, RM>
WP = {W1, W2, W3} RM = <M, WT, WS> WT = {W4}
WS = {W5} Workstation Level:
W = {W1, W2, W3, W4, W5} W1 = <WC1, E1, BS1, PD1, PO1> E1 = {Puma, Horizon, Fanuc M1-L} BS1 = {Buffer} PD1 = {Part Inverter}
PO1 = {Cartrac_1} W2 = <WC2, E2, PO2> E2 = {Bridgeport, Fanuc A0}
PO2 = {Cartrac_3} W3 = <WC3, E3, PO3> E3 = {IBM7545} PO3 = {Cartrac_4} | W4 = {WC4, E4, PO4}
E4 = {SI Cartrac}
PO4 = {Cartrac_1, Cartrac_2, Cartrac_3, Cartrac_4} W5 = {WC5, E5, PO5} E5 = {Kardex, IBM7535}
PO5 = {Cartrac_2} Equipment Level: E = {MP, MH, MT, AS} MP = {Puma, Horizon, Bridgeport, IBM7545} MH = {Fanuc M1-L, IBM7535, Fanuc A0} MT = {SI Cartrac}
AS = {Kardex} BS = {Buffer} PD = {Part Inverter} PO = {Cartrac_1, Cartrac_2, Cartrac_3, Cartrac_4} |
Figure 5. Penn State CIM Lab.
As described by Joshi et al. (1990) and Jones and Saleh (1990), controller activities at each level in the hierarchy can be partitioned into planning activities, scheduling activities, and execution activities. In this system, planning commits by selecting the controller tasks that are to be performed (e.g., planning involves selecting from between alternative routes and splitting part batches to meet capacity constraints). Scheduling involves setting start/finish times for the individual processing tasks at the controller's subordinate entities. Execution verifies the physical preconditions for scheduled tasks and subsequently carries out the dialogue with the subordinate controllers required to physically perform the tasks. Table 1 provides the typical planning, scheduling, and execution activities associated with the equipment, workstation, and shop levels in the control hierarchy.
Table 1. Planning, scheduling,
and execution activities for each level in the SFCS control architecture.
| Planning | Scheduling | Execution | |
| Equip. | Operations-level planning (e.g. tool path planning). | Determining the start/finish times for the individual tasks. Determining the sequence of part processing when multiple parts are allowed. | Interacting with the machine controller to initiate and monitor part processing. |
| Wkstn. | Determining the part routes through the workstation (e.g. selection of processing equipment). Includes replanning in response to machine breakdowns. Allocation of shared tools. | Determining the start/finish times for each part on each processing machine in the workstation. | Interacting with the equipment level controllers to assign and remove parts and to synchronize the activities of the devices (e.g. as required when using a robot to load a part on a machine tool). |
| Shop | Determining part routes through the shop. Splitting part orders into batches to match material transport and workstation capacity constraints. Managing shared tools between workstations. | Determining the start/finish times for part batches at each workstation. Scheduling the delivery of shared tools. | Interacting with the workstation controllers and the Resource Manager to deliver/pick-up parts. |
Figure 6 illustrates the flow of information/control within a controller during system operation.
Figure 6. Control/information flow during system operation.
The shop processes orders which are part of the master production schedule for the facility. Shop level planning uses the shop level process plan and the current shop loading to determine the workstation route that the individual parts will take. Further, the order may be broken up into batches and part groups to facilitate production, transport, and/or handling. Shop level scheduling converts the batches and workstation assignments from planning into a list of tasks to be issued by execution. This list provides a priority ranking for the order within the shop. Additionally, start/end times will be set for tasks at each workstation. Shop level execution coordinates the production of the current open orders in the shop by issuing the tasks to the individual workstations as specified by the scheduler. The shop also facilitates interactions between the individual workstations where necessary.
Processing workstations produce parts in the form of batches or part groups. Workstation level planning uses the workstation level process plan and the current workstation loading to determine the actual pieces of equipment that the parts will be processed on. This also includes the determination of the specific work content that is to be achieved by the equipment. For example, a milling machine might perform a drilling operation and a reaming operation on a part during one production run, and only perform the drilling operation during the next production run. The planning module will evaluate the workstation load and attempt to balance the processing requirements across all equipment in the workstation. Scheduling converts the sequence of equipment operations for all parts into a list of tasks that is issued by execution. This task list represents current scheduling policy being utilized by the workstation. Execution coordinates the movement of the batch or part group though the workstation by issuing the tasks to the individual equipment controllers and coordinating the interaction between equipment.
Processing equipment performs operations on part groups. Equipment level planning uses the work content assigned by the workstation to determine a sequence of operations to be performed on that piece of equipment. In the case of machining, planning might optimize machining parameters based on the machine and tool status. Scheduling converts this sequence of operations into a list of specific tasks to be issued by execution. The list represents a priority ranking of the part groups currently assigned to the equipment. Execution coordinates the production of part groups by performing the tasks provided by scheduling. Equipment level execution provides the direct interface between the control system and the physical machines.
Intuitively, it can be seen that if workstations and equipment are allowed to make unilateral decisions regarding priorities, the overall performance of the shop may suffer. Local optimums at the equipment and workstation levels do not guarantee global optimums at the shop level. Therefore, to help coordinate the lower levels of the hierarchy, generalized due dates are utilized. The shop sets a due date for the batch or part group at each individual workstation that the parts visit. These due dates are generated using the order due date, the shop load, and the expected processing times at the workstations. Within the due date constraints imposed by its supervisor, each level is free to schedule its production as it sees fit. The estimated processing times are determined through negotiation between the supervisory controller and its subordinates. Note that, unlike the heterarchical approach described in Section 2, the negotiation occurs between supervisory controllers and their subordinates rather than between part entities and processing entities. Negotiation based scheduling in a hierarchical environment is a topic of ongoing research (Lin and Solberg, 1992; Senehi et al. 1991). The architecture presented in this paper is meant to provide a formal structure which will allow this type of negotiation.
The primary reason for identifying the partitioning of controller activities is so that the differences in the dependencies of each partition can be exploited during system development and modification. These dependencies determine the frequency with which the module performing the activities must be created/modified. Execution activities depend on the configuration of the shop, and not on the parts being produced. For example, the execution tasks for an NC mill will be identical regardless of the part being cut. Only the NC file specifying the tools and cutter paths will be different. Similarly, the workstation level execution activities required to synchronize a robot loading a part in an NC turning center are also independent of the specific part type being turned. Since the execution tasks depend only on the configuration of the shop, the execution software can be generated based solely on that configuration. Furthermore, current and past research has shown promise that a significant portion of this execution software can be automatically generated based on a high-level description of the shop (Mettala, 1989; Smith, 1992; Smith and Joshi, 1994, 1994b). The architecture described in this paper defines the structure of this high-level description.
However, scheduling and planning activities depend not only on the configuration of the shop, but also on the characteristics of the parts and part orders and on the load in the shop at the time of manufacture. For example, maximizing part throughput might be a good objective for processing an order of single parts, whereas minimizing the number of tardy jobs might be a better objective for processing parts which must later be aggregated (e.g., for assembly). The main concern is that, since the part mix and production requirements change frequently in the target environment, the planning and scheduling requirements will also change frequently within the same shop configuration. Currently, discrete event simulation is used as the planning and scheduing tool within our implementation (Smith et al., 1994). The simulation is explicitly separated from the execution module and communicated through shared memory, and, hence, can be freely modified without affecting the execution function.
Using this separation of execution from scheduling and planning, generic execution modules can be developed for a facility. These modules are developed using generic tasks derived from the physical characteristics of the individual controllers, and are represented using formal models of the controller (Mettala, 1985; Smith and Joshi, 1994). Examples of the generic tasks include pick, put, process, which specify picking up, putting down, and processing parts, respectively. These generic tasks are the elemental actions of the controllers which need to be scheduled by the scheduler. The execution module merely provides the means to verify physical preconditions and communicate with the subordinate systems to facilitate the tasks. This partitioning of the controllers functionality is vital to the creation of the generic controllers and is facilitated by the architecture presented in this paper.
A shop floor controller class (Booch, 1991) has also
been constructed to aid in controller development (Smith and Joshi,
1994). This class (shown in Figure 8) is based on the hierarchical
decomposition and classification of shop floor controllers presented
in this paper. Individual classes inherit the data structures
and methods generic across all controllers and add additional
data structures and methods specific to the controller type.
These additional methods specialize the controller based on the
specific behaviors performed by the class of equipment/workstation.
Controller objects are instantiated from the controller class
and are linked with the automatically generated execution code
and the hand crafted planning and scheduling code to form operational
controllers. The controller class and generation systems have
been implemented in C++ and are described in detail by Smith and
Joshi (1994 and 1994b).
Our ongoing goal has been to develop CASE tools and techniques that reduce development costs associated with the software implementation of the SFCS. Our current research has focused on the control architecture, the execution functions, and the scheduling functions. The models described in this paper have been tested and are being used to facilitate shop floor control software development at the Penn State University's Computer Integrated Manufacturing Lab and at the Texas A&M Computer Aided Manufacturing Lab. The formal descriptions of these facilities instantiated from the architecture presented in this paper are critical components to the control system generation methodology.
A three-level hierarchical control architecture has been presented. The architecture extends the existing hierarchical architectures by providing formal definitions for the individual architectural components. In the development of a specific shop floor control system, the architecture provides the generic structure under which the specific implementation can be formally described. This formal description of the specific shop serves as the basis for controller development, including the planning, scheduling, and execution functions. Additionally, the structure provides an implementation-independent language which can be used by other researchers for describing their manufacturing systems and/or laboratories. With a common language, meaningful comparisons can be made between different shop floor configurations and control system implementations. Implementation experience has shown that the software development and maintenance tasks have been simplified by the use of the formal descriptions and the development methodology described in this paper.
This work was partially supported through National Science Foundation (NSF) awards DDM-9009270 and DDM-9158042, both awarded to Dr. Sanjay Joshi, and by DARPA grant ARPA #8881, "Rapid Prototyping of Shop-floor Control Systems for CIM." The views expressed in the paper are the views of the authors.
Albus, J., Barbera, A., and Nagel, N., Theory and Practice of Hierarchical Control, Proceedings of the 23rd IEEE Computer Society International Conference, Washington D.C., 1981, pp. 18-39.
Ayres, R. U., Technology Forecast for CIM, Manufacturing Review, Vol. 2, No. 1, 1989, pp. 43-52.
Beeckman, D., CIM-OSA: Computer Integrated Manufacturing - Open Systems Architecture, International Journal of Computer Integrated Manufacturing, Vol. 2, Nol. 2, 1989, pp. 94-105.
Booch, G., Object-Oriented Design with Applications, Benjamin/Cummings Publishing, 1991.
Catron, B.A., and Ray, S.R., ALPS: A Language for Process Specification, International Journal of Computer Integrated Manufacturing, Vol. 4, No. 2, pp. 105-113, 1991.
Chaar, J. K., A Methodology for Developing Real-Time Control Software for Efficient and Dependable Manufacturing Systems, Ph.D. Thesis, University of Michigan, 1990.
Duffie, N. A. and Piper, R. S., Non-Hierarchical Control of a Flexible Manufacturing Cell, Robotics & Computer Integrated Manufacturing, Vol. 3, No. 2, 1987, pp. 175-179.
Duffie, N. A., Chitturi, R., and Mou, J., Fault-tolerant Heterarchical Control of Heterogeneous Manufacturing System Entities, Journal of Manufacturing Systems, Vol. 7, No. 4, 1988, pp. 315-327.
Hatvany, J., Intelligence and Cooperation in Heterarchic Manufacturing Systems, Robotics & Computer Integrated Manufacturing, Vol. 2, No. 2, 1985, pp. 101-104
Hoberecht, W. C., Automatic Generation of Equipment and Workstation Scheduling Software Modules for Use in a Shop Floor Control System, Ph.D. thesis, The Pennsylvania State University, 1994.
Jones, A. T. and McLean, C. R., A Proposed Hierarchical Control Architecture for Automated Manufacturing Systems, Journal of Manufacturing Systems, Vol. 5, No. 1, 1986, pp. 15-25.
Jones, A. T. and Saleh, A., A Multi-level/Multi-layer Architecture for Intelligent Shopfloor Control, International Journal of Computer Integrated Manufacturing, Vol. 3, No. 1, 1990, pp. 60-70.
Joshi, S. B., Wysk, R. A., and Jones, A., A Scaleable Architecture for CIM Shop Floor Control, Proceedings of Cimcon '90, A. Jones Ed., National Institute of Standards and Technology, May 1990, pp. 21-33.
Judd, R., P., Vanderbok, R. S., Brown, M. E., and Sauter, J. A., Manufacturing System Design Methodology: Execute the Specification, Proceedings of Cimcon '90, A. Jones Ed., National Institute of Standards and Technology, May 1990, pp.133-152
Lin, G. Y. and Solberg, J. J., Integrated Shop Floor Control Using Autonomous Agents, IIE Transactions, Vol. 24, No. 3, July 1992, pp. 57-71.
Merchant, M. E., The Percepts and Sciences of Manufacturing, Robotics & Computer Integrated Manufacturing, Vol. 4, No. 1/2, 1988, pp. 1-6.
Mettala, E. G., Automatic Generation of Control Software in Computer Integrated Manufacturing, Ph.D. Thesis, The Pennsylvania State University, 1989.
Naylor, A. W. and Volz, R. A., Design of Integrated Manufacturing Control Software, IEEE Transactions on Systems, Man, and Cybernetics, Vol. SMC-17, No. 6, November/December 1987, pp. 881-897.
Ostroff, J. S., A Logic for Real-Time Discrete Event Processes, IEEE Control Systems Magazine, June 1990, pp. 95-102.
Senehi, M. K., Barkmeyer, E., Luce, M., Ray, S., Wallace, E., and Wallace, S., Manufacturing Systems Integration Initial Architecture Document, National Institute of Standards and Technology, NIST Iteragency Report NISTIR 4682, Gaithersburg, MD, 1991.
Simpson, J. A., Hocken, R. J., and Albus, J. S., The Automated Manufacturing Research Facility of the National Bureau of Standards, Journal of Manufacturing Systems, Vol. 1, No. 1, 1982, pp. 17-31.
Smith, J. S., A Formal Design and Development Methodology for Shop Floor Control in Computer Integrated Manufacturing, Ph.D. thesis, The Pennsylvania State University, 1992.
Smith, J. S. and Joshi, S. B., Reusable Software Concepts Applied to the Development of FMS Control Software, International Journal of Computer Integrated Manufacturing, Vol. 5, No. 3, 1992, pp. 182-196.
Smith, J.S. and Joshi, S.B., "A Shop Floor Controller Class for Computer Integrated Manufacturing," International Journal of Computer Integrated Manufacturing, (accepted), 1994.
Smith, J. S. and Joshi, S. B., Message-based Part State Graphs (MPSG): A Formal Model for Shop Floor Control, Working Paper # INEN MS WP 14 11-92, Texas A&M University, College Station, TX 7783, 1994b.
Smith, J. S., Wysk, R. A., Sturrock, D., Ramaswamy, S., Smith, G., and Joshi S. B., "Discrete Event Simulation for Shop Floor Control," Proceedings of the 1994 Winter Simulation Conference, December, 1994, Lake Buena Vista, FL, pp. 962-969.