Scheduling tasks and vehicles in a flexible manufacturing system

Due to their increasing applicability in modern industry, flexible manufacturing systems (FMSs), their design, and their control have been studied extensively in the recent literature. One of the most important issues that has arisen in this context is the FMS scheduling problem. This article is concerned with a new model of an FMS system, motivated by the practical application that takes into account both machine and vehicle scheduling. For the case of a given machine schedule, a simple polynomial-time algorithm is presented that checks the feasibility of a vehicle schedule and constructs it whenever one exists. Then a dynamic programming approach to construct optimal machine and vehicle schedules is proposed. This technique results in a pseudopolynomialtime algorithm for a fixed number of machines.     

Specification methods for material-handling control algorithms in flexible manufacturing systems

Good methods are needed to specify, test, and debug material-handling control logic. This article surveys a number of representative methods for defining and describing control algorithms for programmable material-handling equipment used in flexible manufacturing systems. The methods are evaluated with regard to their suitability for communication between people and as bases for interfaces to automatic program generators. It is concluded that no single method is entirely satisfactory. Three methods (position diagrams, function block diagrams, and operation networks) have potential to be combined into an effective hybrid approach that minimizes the need for the user to switch between various conceptual models.     

Developing a computer control system for a flexible manufacturing cell

This article focuses on the development of a computer control system for a flexible manufacturing cell. The paper outlines the various modules that are required for a computer control system and elaborates on the development of some of these modules. This is part of an ongoing research project at the University of the Witwatersrand. The aim of the project is to demonstrate the viability of flexible manufacturing systems to South African industry. Thus the main constraints of the project were cost, ease of implementation, and ease of maintainability. This necessitated the use of existing machinery and of computer systems and software that were readily available and already familiar to industry.     

Allocating buffer storages in a flexible manufacturing system

This article reports an approximation scheme to determine buffer capacities required to achieve the target performance level in a general flexible manufacturing system with multiple products. This work extends our previous study of sequential production lines with a single product. The manufacturing system is operated using a pull mechanism, and the performance level is measured by the average proportion of demands backlogged. Simulation experiments were performed to study the validity of the approximation scheme under various situations.     

Dynamic load control policies for a flexible manufacturing system with stochastic processing rates

Real-time scheduling and load controls of FMSs are complex processes in which the control logic must consider a broad spectrum of instantaneous state variables while taking into account the probabilistic future impact of each decision at each time epoch. These processes are particularly important in the management of modern FMS environment, since they are known to have a significant impact on the FMS productive capacity and economic viability. In this article we outline the approach developed for dynamic load controls within an FMS producing a variety of glass lenses. Two revenue-influencing objective functions are evaluated for this capital-intensive facility. It is shown that by using Semi-Markovian modeling concepts, the FMS states need to be observed only at certain decision epochs. The mean holding time in each state is then obtained using the probability distribution function of the conditional state occupancy times. Several key performance measures are then derived by means of the value equations. In addition, the structure of the optimal policies are exemplified for a variety of operational parameters. It is shown that the optimal policies tend to generate higher buffer stocks of parts in those work centers having the highest revenue-generation rates. These buffer stocks get smaller and smaller as the relative processing capacity of the centers increases. Similar observations lead us to the introduction of several promising heuristics that capture the structural properties of the optimal policies with a significantly smaller computational effort. Results of the empirical evaluation of these heuristics are also analyzed here.     

Production planning of a flexible manufacturing system in a material requirements planning environment

Early flexible manufacturing system (FMS) production planning models exhibited a variety of planning objectives; typically, these objectives were independent of the overall production environment. More recently, some researchers have proposed hierarchical production planning and scheduling models for FMS. In this article, we examine production planning of FMS in a material requirements planning (MRP) environment. We propose a hierarchical structure that integrates FMS production planning into a closed-loop MRP system. This structure gives rise to the FMS/MRP rough-cut capacity planning (FMRCP) problem, the FMS/MRP grouping and loading (FMGL) problem, and the FMS/MRP detailed scheduling problem. We examine the FMRCP and FMGL problems in detail and present mathematical programming models for each of these problems. In particular, the FMRCP problem is modeled as a generalized assignment problem (GAP), and a GAP-based heuristic procedure is defined for the problem. We define a two-phase heuristic for the FMGL problem and present computational experience with both heuristics. The FMRCP heuristic is shown to solve problems that exhibit a dependent-demand relation within the FMS and with FMS capacity utilization as high as 99 percent. The FMGL heuristic requires very little CPU time and obtains solutions to the test problems that are on average within 1.5 percent of a theoretical lower bound. This FMS/MRP production planning framework, together with the resulting models, constitutes an important step in the integration of FMS technology with MRP production planning. The hierarchical planning mechanism directly provides for system-level MRP planning priorities to induce appropriate production planning and control objectives on the FMS while simultaneously allowing for necessary feedback from the FMS. Moreover, by demonstrating the tractability of the FMRCP and FMGL problems, this research establishes the necessary groundwork upon which to explore systemwide issues pertaining to the coordination of the hierarchical structure.     

Selecting technology for investment in flexible manufacturing

Flexible manufacturing (FM) has progressed to the stage where the concepts and the available technology are well established and proven. Investment in FM can be very profitable, but must be aimed at achieving clearly defined objectives. This article describes the scope of FM and shows that the required technical specification is determined by the nature of the potential benefits. The ability to quantify all the potential benefits of FM in financial terms means that investment should not be made without a financial evaluation, but should be treated as any other investment decision. Advice is given to show companies how to identify the companywide benefits of FM and to relate these to the required technology before selecting potential suppliers.     

Tool addition strategies for flexible manufacturing systems

The allocation of tools to machines determines potential part routes in flexible manufacturing systems. Given production requirements and a minimum feasible set of tools, the decision of how to fill vacant slots in tool magazines to maximize routing flexibility is shown to be a minimum cost network flow problem for the cases when routing flexibility is a function of the average workload per tool aggregated over tool types, or of the number of possible routes through the system. A linear programming model is then used to plan a set of routes for each part type so as to minimize either the material handling requirement or the maximum workload on any machine. The impact of these tool addition strategies on the material handling and workload equalization is investigated and computational results presented. The advantage of the overall approach is computational simplicity at each step and the ability to react to dynamic changes.     

Decision learning about production control as machines break down in a flexible manufacturing system

During manufacturing, there are many situations that can affect production performance. Such situations include machine breakdowns, rush orders, order changes, and order delays. When such issues occur, one has to make decisions to try to maintain production efficiency. Human decisions tend to be too late and incomplete in such contingencies. Thus a system that can make better decisions in time to maintain production performance is needed. To achieve this objective, the intelligent decision system described in this paper integrates artificial intelligence, an optimization technique, and simulation to solve such problems. The decision-making logic of the intelligent decision system is described by event graphs. It imitates the manner of human thinking. Self-learning of the decision-making process is used to strengthen the decision quality. In this study, a method of rule induction is applied to build up the self-learning system. There are two subsystems included in this system. One is rule generation and the other is knowledge management. A case for machine breakdowns is presented and discussed. A series of tests designed to validate the self-learning system are presented. These demonstrate that a rule induction method is suitable for constructing the self-learning.     

A knowledge-based system for the strategic control level of robots in flexible manufacturing cells

The strategic control level synthesis for robots is related to a hierarchical robot control problem. The main control problem at the strategic control level is to select the model and algorithm to be used by the lower control level to execute the given robot task. Usually there are several lower control level models and algorithms that can be used by the robot control system for every robot task. Strategic control level synthesis depends on the particular robot system application. In a typical application, when the robot system is used in a flexible manufacturing system for manipulating various part types, the robot tasks executed by the robot system depend on the manufacturing processes in the system. If the robot system is applied in another flexible manufacturing system, dedicated to other manufacturing processes, another set of robot tasks might be needed to perform the necessary operations. Therefore, the quantity and the kind of knowledge required in the system for the strategic control level differ from one application to another. Such a fact creates the appropriate conditions for employing some artificial intelligence techniques. This article describes a knowledge-based system approach to the strategic control level synthesis problem.     

An iterative approach to system setup problems in flexible manufacturing systems

System setup problems in flexible manufacturing systems deal with short-term planning problems such as part type selection, machine grouping, operation assignment, tooling, fixture and pallet allocation, and routing. In this article, we consider three of the subproblems: part type selection, machine grouping, and loading. We suggest a heuristic approach to solve the subproblems consistently with the objective of maximizing the expected production rate. The proposed procedure includes routines to generate all possible machine grouping alternatives for a given set of machines, to obtain optimal target workloads for each grouping alternative, and to allocate operations and tools to machine groups. These routines are executed iteratively until a good solution to the system setup problem is obtained. Computational experience is reported.     

Dispatching,routing, and scheduling of two automated guided vehicles in a flexible manufacturing system

This article presents a new approach for planning the dispatching, conflict-free routing, and scheduling of automated guided vehicles in a flexible manufacturing system. The problem is solved optimally in an integrated manner, contrary to the traditional approach in which the problem is decomposed in three steps that are solved sequentially. The algorithm is based on dynamic programming and is solved on a rolling time horizon. Three dominance criteria are used to limit the size of the state space. The method finds the transportation plan minimizing the makespan (the completion time for all the tasks). Various results are discussed. A heuristic version of the algorithm is also proposed for an extension of the method to many vehicles.     

A loop layout design problem for flexible manufacturing systems

The interconnection pattern of the processing modules of a computerized manufacturing system affects its performance. In this article, we discuss a set of requirements that the interconnection network should satisfy. Subsequently, we concentrate on a simple and popular architecture, the loop network. The problem we address is to design the layout of the system so that the number of machines that the part types cross in their manufacturing process is minimized. We formulate the problem mathematically and solve it by a heuristic that obtains consistently better results than an earlier popular method.     

A modular control design method for a flexible manufacturing cell including error handling

This paper introduces a new modular control design method for a cell controller with integrated error handling. To make the complexity of the cell controller manageable, its control logic is separated into two parts: resource allocation control and operation control. To create the operation control not only quickly but correctly, modular operation blocks integrated with error handling are developed. An algorithm automatically generates the operation control. The operation control created by the proposed method is proved to have desired control behaviors. The method is applied to an example system.     

Reliability analysis of flexible manufacturing systems

High productivity is the primary goal of flexible manufacturing systems (FMSs) in which semi-independent workstations are integrated using automated material-transport systems and hierarchical local networks. Availability of various subsystems and of the system as a whole is a prerequisite for achieving functional integration as well as high throughput. An FMS also has inherent routing and operation flexibilities that provide it with a certain degree of fault tolerance. A certain volume of production can thus be maintained in the face of subsystem (i.e., machines, robots, material handling system, etc.) failures. In this article, we propose two reliability measures, namely, part reliability (PR) and FMS reliability (FMSR) for manufacturing systems and present algorithms to evaluate them. We also consider the dynamic or time-dependent reliability analysis as a natural generalization of the static analysis. The methods outlined use an algorithm that generates process-spanning graphs (PSGs), which are used to evaluate the reliability measures.     

Performance management in flexible manufacturing systems

This article treats several performance management decision problems in flexible manufacturing systems (FMSs). This work differs from a number of other studies in that we allow the processing rates at the machines to be varied, and the system has to meet a given throughput goal per unit time. The managerial decision options modeled here include part routing and allocation of tasks to machines, work-in-progress (WIP) levels, capacity expansions, tool-type selection, the setting of throughput goals, and multiperiod production planning. We discuss and explain the insights and implications, partly nonintuitive, gained from our investigations. Finally, extensive numerical evaluations are included to illustrate the economic and performance impact of the various performance management alternatives. These results demonstrate that substantial economic benefits can be achieved by careful tuning of the FMS operational parameters.     

Modular synthesis of Petri nets for modeling flexible manufacturing systems

This paper proposes a modular Petri net synthesis method for modeling flexible manufacturing systems based on synchronization among control processes of the manufacturing resources (such as robots and machines). In the method, the target system is modeled in a bottom-up and uniform manner by first describing the system's control processes using strongly connected state machines (SCSMs) as the basic modules. Each SCSM may contain multiple tokens to represent resources from the same type such as spaces in a buffer. Next, the common transitions and common transition subnets of the modules are merged to represent their synchronization. The system model constructed is proven to be conservative and thus bounded. Moreover, a restricted class of merged nets is proven to be live and reversible. For general classes of merged nets, this paper shows theorems that easily calculateP-invariants of the final net without solving the linear system equations. TheseP-invariants can be used to help in verifying the model's qualitative properties such as liveness.     

Rule-based production planning in flexible manufacturing systems

Production planning in flexible manufacturing may require the solution of a large-scale discrete-event dynamic stochastic optimization problem, due to the complexity of the system to be optimized, and to the occurrence of discrete events (new orders and hard failures). The production planning problem is here approached for a multistage multipart-type manufacturing shop, where each work cell can share its processing time among the different types of parts. The solution of this problem is obtained by an open-loop-feedback control strategy, updated each time a new event occurs. At each event time, two coupled problems are solved: 1) a product-order scheduling problem, conditioned on estimated values of the production capacities of all component work cells; and 2) a production-capacity planning problem, conditioned on predefined sequences of the product orders to be processed. In particular, the article aims at defining a production planning procedure that integrates both analytical tools, derived from mathematical programming, and knowledge-based rules, coming from experience. The objective is to formulate a hybrid (knowledge-based/analytical) planning architecture, and to analyze its use for multicell multipart-type manufacturing systems.     

Evaluating the design of flexible manufacturing systems

Evaluating the design of flexible manufacturing systems is complex. Developing a measure of performance useful for evaluating alternate designs continues to be interesting. Here, total productivity of the system is proposed as an appropriate measure. Specification of parameters based upon strategic considerations for this measure are discussed. Finally, the usefulness of the measure is demonstrated through an example.     

Quality control of an unreliable flexible manufacturing system with scrapping and infinite buffer capacity

Manufacturing multiple part types on a flexible manufacturing system (FMS) is increasingly becoming a rule rather than an exception. In such systems, attention has been drawn to the application of zero-defect technologies. However, in practice, this goal has remained elusive and costly. As a result, even though FMSs may be more reliable, producing fewer defective parts, system complexity and more stringent quality standards are rendering quality control in FMSs potentially useful. The goals of this article are threefold. First, we introduce a procedure for measuring and managing the in-process quality control of an FMS, which is described by an Open Queueing Network (OQN), bridging thereby a gap between queueing theory and quality control. Second, by focusing attention on the potential unreliabilities of FMSs, we provide some managerial insights regarding the role, position, and distribution of the quality control effort in an FMS. Finally, we stress the intricate relations between an FMS's operating characteristics and the manufactured quality and its control. Using numerical analyses, we draw some inferences regarding the design of such FMSs when both quality and quantity issues in the FMSs are considered. These simultaneous considerations of quantity and quality flows in an FMS have not been previously considered in the study of FMSs.