A GPSS/H model for a hypothetical flexible manufacturing system

A GPSS/H model is presented for a hypothetical flexible manufacturing system. The FMS consists of six machines composed of three machine types, manufactures three types of parts, and uses automatic guided vehicles (AGVs) to transport inprocess parts between appropriate machines and wait spaces in the system. Three logical modules have been designed for the model, with copies of these modules then being appropriately distributed and interfaced throughout the model and tailored to achieve overall representation of the specific FMS. The same technique can be used by others to build analogous or extended GPSS/H models for other specific FMSs in which AGVs are used as transporters. Simulations can then be performed with such models to research FMS design and control alternatives.     

Solving the AGV Problem via a Self-Organizing Neural Network

Automated Guided Vehicle (AGV)-based material handling systems (MHS) are used widely in Flexible Manufacturing Systems (FMS). The problem of AGV consists of the decisions and the operational control strategies of dispatching, routeing and scheduling of a set of AGVs under given system environments and operational objectives. One remaining challenge is to develop effective methods of AGV decisions for improved system productivity. This paper describes a prototype neural network approach for the AGV problem in an FMS environment. A group of neural network models are proposed to perform dispatching and routeing tasks for the AGV under conditions of single or multiple vehicles, and with or without time windows. The goal is to satisfy the transport requests in the shortest time and in a non-conflicting manner, subject to the global manufacturing objectives. Based on Kohonen's self-organizing feature maps, we have developed efficient algorithms for the AGVs decisions, and simulation results have been very encouraging.     

Design,planning, scheduling,and control problems of flexible manufacturing systems

The design and use of flexible manufacturing systems (FMSs) involve some intricate operations research problems.FMS design problems include, for example, determining the appropriate number of machine tools of each type, the capacity of the material handling system, and the size of buffers.FMS planning problems include the determination of which parts should be simultaneously machined, the optimal partition of machine tools into groups, allocations of pallets and fixtures to part types, and the assignment of operations and associated cutting tools among the limited-capacity tool magazines of the machine tools.FMS scheduling problems include determining the optimal input sequence of parts and an optimal sequence at each machine tool given the current part mix.FMS control problems are those concerned with, for example, monitoring the system to be sure that requirements and due dates are being met and that unreliability problems are taken care of. This paper defines and describes these FMS problems in detail for OR/MS researchers to work on.     

MULTIQ: A Queueing Model for FMSs with Several Pallet Types

Analytical modelling of the work flow through flexible manufacturing systems (FMSs), based on closed queueing network models, has been successfully applied to the early stages of design and analysis of FMSs. This paper describes the advantages of using multiple job-class closed queueing networks for modelling realistic situations occurring in FMSs. The general modelling of FMSs by closed queueing networks is first reviewed. The way Solberg's CAN-Q—a single job-class queueing-based package—deals with several part types is clarified. A new model called MULTIQ, allowing multiple pallet types, each of which is used by several part types, is proposed. Results are derived using the data from an existing FMS. The use of the MULTIQ model for optimization purposes is suggested by some examples.     

Sequential Modelling of the Planning and Scheduling Problems of Flexible Manufacturing Systems

Research on the planning and scheduling issues of flexible manufacturing systems (FMS) has not been sparse. Most, if not all, studies, however, have focused on either developing the planning model or examining the performance of different scheduling rules. To date, the FMS planning and scheduling problems have not been studied together, though they are highly interrelated.This paper takes a first step to simultaneously address the planning and scheduling problems of flexible manufacturing systems. The problems are solved as a hierarchical process. We first integrate and formulate batching, loading, and routeing, three of the most important FMS planning problems, as a 0–1 mixed integer program. According to the optimal decisions provided by the integrated planning model, we then develop an off-line scheduling scheme that is capable of generating detail parts sequencing in the sequence independent environment (i.e. the operations are not constrained by a process sequence). Finally, we suggest several extensions and future research directions.     

Hierarchical Stochastic Production Planning with Delay Interaction

This paper explores the problem of hierarchical stochastic production planning (HSPP) for flexible automated workshops (FAWs), each consisting of a number of flexible manufacturing systems (FMSs). The objective is to devise a production plan which tells each FMS how many parts to produce and when to produce them so as to simultaneously minimize the amount of work in progress, maximize the machine utilization, and satisfy demands for finished products over a finite horizon of N time periods. Here, the problem formulation includes not only uncertainty in demand, capacities, and material supply (which is standard in the literature), but also uncertainties in processing times, rework, and waste products. It considers also multiple products and multiple time periods. This is in contrast to most work which looks at either a single periods or at an infinite horizon. The delay interaction aspect arises from taking into account the transportation of parts between FMSs. Apparently, any job which requires processing on more than one FMS cannot be transported directly from one FMS to the next. Instead, a semifinished product completed in one period must be put into shop storage until some future time period at which it can be transported to the next FMS for further processing. Herein, a stochastic interaction/prediction algorithm is developed by using standard calculus of variations techniques. By means of the software package developed, many HSPP examples have been studied, showing that the algorithm is very effective.     

Tool planning models for flexible manufacturing systems

Although the tool loading problem for Flexible Manufacturing Systems (FMSs) has been analyzed in the past, the tool planning problem, the basis of tool management, has largely been ignored. In this paper, the interface between tool planning and the FMS loading and routing decisions is analyzed. It is shown that tool policy has a pronounced effect on the flexibility and the planned makespan of an FMS. A tool planning model is developed and integrated into an overall FMS detailed tool loading and part routing procedure. This model while considerably reducing the number of tools required (by 55%) matches the performance of a policy that equips each machine with all tools in terms makespan, routing flexibility, and tool productivity.     

A Hierarchical Model for Control of Flexible Manufacturing Systems

Flexible Manufacturing Systems (FMSs) are usually composed of general purpose machines with automatic tool changing capability and integrated material handling. The complexity of FMSs requires sophisticated control. In this paper we present a four-level control hierarchy and outline computationally feasible control algorithms for each level. The top level is concerned with the choice of part types and volumes to be assigned to the FMS over the next several months. The second level plans daily or shift production. Production levels are set and tools are allocated to machines so as to minimize holding and shortage costs. Various FMS environments are presented. The third level determines process routes for each part type in order to minimize material handling. Additional tools are loaded on machines when possible to maximize alternate routeing. Routes are then assigned to parts to minimize workload assignment, and these are used by level four for actual routeing, sequencing and material handling path control. The level three model is formulated as a linear program, and heuristics are used for level four. An example is provided to illustrate the completeness of the decision hierarchy and the relationships between levels.     

Analysis of flexible manufacturing systems with priority scheduling: PMVA

A new methodology for performance analysis of flexible manufacturing systems (FMSs) with priority scheduling is presented. The analytic model developed extends the mean value analysis of closed networks of queues with multiple product types, various non-preemptive priority service disciplines, and with parallel machine stations. Performance measures derived include the expected throughput per product and per station, utilization of machines and transporters, queuing times and queue length measures for various configurations. Extensive numerical calculations have shown that the algorithm used for solving the problem converges rapidly and retains numerical stability for large models. The paper also illustrates the application of the model to a system with a mixture of FCFS and HOL disciplines which gives insights into various priority assignment policies in FMSs. Special attention was given to the problem of scheduling the robot carriers (transporters).     

Discovering metamodels’ quality-of-fit for simulation via graphical techniques

Metamodels are used in many disciplines to replace simulation models of complex multivariate systems. To discover metamodels ‘quality-of-fit’ for simulation, simple information returned by average-based statistics, such as root-mean-square error RMSE, are often used. The sample of points used in determining these averages is restricted in size, especially for simulation models of complex multivariate systems. Obviously, decisions made based on average values can be misleading when the sample size is not adequate, and contributions made by each individual data point in such samples need to be examined. This paper presents methods that can be used to discover metamodels quality-of-fit graphically by means of two-dimensional plots. Three plot types are presented; these are the so-called circle plots, marksman plots, and ordinal plots. Such plots can be used to facilitate visual inspection of the effect on metamodel accuracy of each individual point in the data sample used for metamodel validation. The proposed methods can be used to complement quantitative validation statistics; in particular, for situations where there is not enough validation data or the validation data is too expensive to generate.     

A Petri net approach to the modelling and analysis of flexible manufacturing systems

In this paper we present an approach for modelling and analyzing flexible manufacturing systems (FMSs) using Petri nets. In this approach, we first build a Petri net model (PNM) of the given FMS in a bottom-up fashion and then analyze important qualitative aspects of FMS behaviour such as existence/absence of deadlocks and buffer overflows. The basis for our approach is a theorem we state and prove for computing the invariants of the union of a finite number of Petri nets when the invariants of the individual nets are known. We illustrate our approach using two typical manufacturing systems: an automated transfer line and a simple FMS.A shorter version of this paper was presented at the 1st ORSA/TIMS Special Interest Conference on FMSs, University of Michigan, Ann Arbor, August 1984.     

Metamodeling: Radial basis functions,versus polynomials

For many years, metamodels have been used in simulation to provide approximations to the input–output functions provided by a simulation model. In this paper, metamodels based on radial basis functions are applied to approximate test functions known from the literature. These tests were conducted to gain insights into the behavior of these metamodels, their ease of computation and their ability to capture the shape and minima of the test functions. These metamodels are compared against polynomial metamodels by using surface and contour graphs of the error function (difference between metamodel and the given function) and by evaluating the numerical stability of the required computations. Full factorial and Latin hypercube designs were used to fit the metamodels. Graphical and statistical methods were used to analyze the test results. Factorial designs were generally more successful for fitting the test functions as compared to Latin hypercube designs. Radial basis function metamodels using factorial and Latin hypercube designs provided better fit than polynomial metamodels using full factorial designs.     

Sequential decision procedures for batching and balancing in FMSs

Batching and balancing constitute two of the several scheduling and resource allocation problems important over different time scales in FMS operations. The time scale for batching and balancing is of the order of days to weeks — which puts it between long-term planning and part selection, of the order of months to years, and real-time part entry and dispatching, of the order of minutes. All these scheduling and resource allocation problems have been addressed at the Charles Stark Draper Laboratoty by a common methodology. We have used a sequential decision algorithm, each decision based on optimization of a probabilistic performance criterion designed to trade off whatever and however many competing attributes may be important in the particular problem. This paper discusses the common methodology, and its application to FMS batching and balancing in particular. Our computer program BATCH/BAL which implements the algorithms given here has been the starting point for all the other sequential decision programs subsequently developed at our laboratory.This paper is based in part on work supported by the United States Army Tank Automotive Command under Contract DAAE07-83-C-R084 with the Charles Stark Draper Laboratory, Inc., and in part on work supported under Internal Research and Development at Draper.     

Inspection sequencing and part scheduling for flexible manufacturing systems

An approach to the study of integrated effects of inspection sequencing rules and part scheduling policies in flexible manufacturing settings is presented. Simulation experiments were carried out to examine 5 inspection sequencing heuristics while considering 8 different part scheduling policies in a typical FMS construct. Analyses of data have shown that the inspection sequencing has a significant impact on FMS performance, and the selection of a part scheduling policy relies heavily on the inspection plan implemented in the system. The results of this study sustain the need to explore total issues of an FMS, if possible, rather than a piecemeal approach which usually falls short when pursuing a global system optimization.     

Dynamic scheduling for switched processing systems with substantial service-mode switching times

Switched Processing Systems (SPS) represent canonical models for many communication and computer systems. Over the years, much research has been devoted to developing the best scheduling policies to optimize the various performance metrics of interest. These policies have mostly originated from the well-known MaxWeight discipline, which at any point in time switches the system into the service mode possessing “maximal matching” with the system state (e.g., queue-length, workload, etc.). However, for simplicity it is often assumed that the switching times between service modes are “negligible”—but this proves to be impractical in some applications. In this study, we propose a new scheduling strategy (called the Dynamic Cone Policy) for SPS, which includes substantial service-mode switching times. The goal is to maximize throughput and maintain system stability under fairly mild stochastic assumptions. For practical purposes, an extended scheduling strategy (called the Practical Dynamic Cone Policy) is developed to reduce the computational complexity of the Dynamic Cone Policy and at the same time mitigate job delay. A simulation study shows that the proposed practical policy clearly outperforms another throughput-maximizing policy called BatchAdapt, both in terms of the average and the 95th percentile of job delay for various types of input traffic.     

A knowledge-based approach to scheduling in an F.M.S.

This paper reports the development of a computer-based system for production scheduling in a dedicated FMS. The system is based on the state-operator framework commonly used in artificial intelligence. Such a system consists of three components: (i) a knowledge base of states, which describes both the current task domain situation and the goal to be achieved; (ii) a set of operators that are used to manipulate the knowledge base; and (iii) a control strategy to decide which operators to apply next and to resolve conflicts. Some of the interesting features of the scheduling system include: (i) the ability to detect resource conflicts; (ii) the ability to determine alternate routes for a given part in the event of a resource conflict; and (iii) the ability to amend plans if an alternate route is found. These features allow the system to take advantage of the flexible routing for parts that an FMS allows. The system has been implemented using the XLISP programming language. Implementation considerations are discussed. A small but comprehensive example is presented. Further research directions are suggested.     

Discrete and continuous time representations and mathematical models for large production scheduling problems: A case study from the pharmaceutical industry

The underlying time framework used is one of the major differences in the basic structure of mathematical programming formulations used for production scheduling problems. The models are either based on continuous or discrete time representations. In the literature there is no general agreement on which is better or more suitable for different types of production or business environments. In this paper we study a large real-world scheduling problem from a pharmaceutical company. The problem is at least NP-hard and cannot be solved with standard solution methods. We therefore decompose the problem into two parts and compare discrete and continuous time representations for solving the individual parts. Our results show pros and cons of each model. The continuous formulation can be used to solve larger test cases and it is also more accurate for the problem under consideration.     

Using subsystem linear regression metamodels in stochastic simulation

This article explores the use of metamodels as simulation building blocks. The metamodel replaces a part of the simulation model with a mathematical function that mimics the input–output behavior of that part, with respect to some measure of interest to the designer. The integration of metamodels as components of the simulation model simplifies the model and reduces the simulation time. Such use of the metamodels also gives the designer a better understanding of the behavior of those parts of the model, making the simulation model as a whole more intelligible. The metamodel-based simulation model building process is examined, step by step, and the designer options are explored. This process includes the identification of the metamodel candidates and the construction of the metamodels themselves. The assessment of the proposed approach includes the evaluation of the integration effort of the metamodel into the metamodel-based simulation model, and the accuracy of the output data when compared to the original system.