Experimental investigation of real-time scheduling in flexible manufacturing systems

This paper presents a new two-phase (TP) approximate method for real-time scheduling in a flexible manufacturing system (FMS). This method combines a reduced enumeration schedule generation algorithm with a 0–1 optimization algorithm. In order to make the combined algorithm practicable, heuristic rules are introduced for the selection of jobs to be scheduled. The relative performance of the TP method vis-a-vis conventional heuristic dispatching rules such as SPT, LPT, FCFS, MWKR, and LWKR is investigated using combined process-interaction/discrete-event simulation models. An efficient experimental procedure is designed and implemented using these models, and the statistical analysis of the results is presented. For the particular case investigated, the conclusions are very encouraging. In terms of mean flow time, the TP method performs significantly better than any other tested heuristic dispatching rules. Also, the experimental results show that using global information significantly improves the FMS performance.     

Evaluation of entropy-based dispatching in flexible manufacturing systems

Traditionally, part dispatching has been done using static rules, rules that fail to take advantage of the dynamic nature of today’s manufacturing systems. In modern manufacturing systems, machines carry multiple tools so parts have the option of being machined at more than one machine. This flexibility, termed routing flexibility in the literature, opens up new possibilities for shop floor planners for the scheduling and dispatching of parts.     

Numerical performance of approximate queuing formulae with application to flexible manufacturing systems

This paper calls attention to two of the more successful queuing approximation formulae — one by Kramer and one by Marchal. The analytic solution of a range of single server Erlang cases is compared to the two approximation formulae. Then a family of H₂/M/1 cases is similarly considered. Maximum errors are seen to be about three percent. The Kramer formula seems to be better when the interarrival coefficient of variation is less than 0.66 and the Marchal formula is better for larger interarrival coefficients of variation. Finally, a multiserver refinement function (the ratio of G/G/1 results to M/M/1 results) is proposed to scale M/M/s as an approximation for G/G/s. In most of these multiple channel cases, the maximum error is less than six percent. The last section of this paper presents a simple, representative FMS. It is modelled as an open queuing network. Then the approximation procedure is applied node by node to illustrate the estimation of system performance measures such as machine utilizations and throughput.     

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).     

Measurement of loading and operations flexibility in flexible manufacturing systems: An information-theoretic approach

An information-theoretic approach is applied for measuring the flexibility in flexible manufacturing systems (FMSs). The general relation between flexibility and entropy is discussed. The entropy for a Markovian process is obtained and then applied to closed queueing network models of FMSs to discuss loading flexibility which arises from the power to regulate the frequency of the visit of a part to different work stations. The concept of operations entropy as a measure of operations flexibility, which arises from the power to choose the work station and the corresponding operations, is introduced. The operations entropy has been decomposed into entropies within and between operations and entropies within and between groups of operations. This measure has been used to determine the next operation to be performed on a part by using the principle of least reduction of flexibility.The present paper is an improved version of the paper On measurement of flexibility in flexible manufacturing systems: An information-theoretic approach, presented at the II ORSA/TIMS Special Conference on Flexible Manufacturing Systems, held at Ann Arbor in August 1986.     

An efficient method to determine the optimal configuration of a flexible manufacturing system

A frequently encountered design issue for a flexible manufacturing system (FMS) is to find the lowest cost configuration, i.e. the number of resources of each type (machines, pallets, ...), which achieves a given production rate. In this paper, an efficient method to determine this optimal configuration is presented. The FMS is modelled as a closed queueing network. The proposed procedure first derives a heuristic solution and then the optimal solution. The computational complexity for finding the optimal solution is very reasonable even for large systems, except in some extreme cases. Moreover, the heuristic solution can always be determined and is very close (and often equal) to the optimal solution. A comparison with the previous method of Vinod and Solberg shows that our method performs very well.     

Modeling a class of state-dependent routing in flexible manufacturing systems

We develop a closed queueing network model for flexible manufacturing systems (FMSs), where parts routing follows a probabilistic shortest-queue (PSQ) scheme, i.e. parts are routed to the shortest queue (or the most empty station) with the highest probability. We allow limited local buffer at each work station. We prove that with the PSQ routing, the Markovian queue-length process satisfies time reversibility and has a product-form equilibrium distribution. An algorithm is developed to compute the solutions to the model. The model can be used as a performance evaluation tool to study FMSs.     

Batching in single operation manufacturing systems

We introduce a new decision problem important to the efficient operation of resources in manufacturing systems. This problem of ‘batching’ is considered for single machine activities. It is shown that even for these simple models, lot splitting may occur and that these batching decisions may have a dramatic impact on the manufacturing lead time of items to be processed.     

A review of open queueing network models of manufacturing systems

In this paper we review open queueing network models of manufacturing systems. The paper consists of two parts. In the first part we discuss design and planning problems arising in manufacturing. In doing so we focus on those problems that are best addressed by queueing network models. In the second part of the paper we describe developments in queueing network methodology. We are primarily concerned with features such as general service times, deterministic product routings, and machine failures — features that are prevalent in manufacturing settings. Since these features have eluded exact analysis, approximation procedures have been proposed. In the second part of this paper we review the developments in approximation procedures and highlight the assumptions that underlie these approaches.     

A technique for on-line sensitivity analysis of flexible manufacturing systems

The recent perturbation analysis approach to discrete event systems is applied to flexible manufacturing systems (FMS). While analytic (queueing) models are useful in preliminary design of such systems, they are not accurate enough at the detailed design/operation stage. Thus, experimentation on detailed simulations or on the actual system has been the way to optimize system performance. Perturbation analysis allows us to derive the sensitivity of system performance, with respect to several design/operating parameters, by observing a single experiment (and without having to actually alter the parameters — often a costly operation). Thus, observation of one experiment can give accurate directions for the improvement of several parameter values. Here we give a simulation example illustrating how perturbation analysis could be used on-line on an FMS to improve its performance, including reducing its operating cost. Experimental results are also presented validating the estimates obtained from this technique.Work supported by U.S. Office of Naval Research Contracts N00014-75-C-0648 and N00014-79-C-0776, and NSF Grant ENG78-15231, at Harvard University.A preliminary version of this paper appeared in the Proc. 1st ORSA/TIMS Conf. on Flexible Manufacturing Systems, August 1984. This version includes two appendices, which relate to implementation of the technique described in the main body of the paper.     

Algorithms for part and machine selection in flexible manufacturing systems

Deciding whether FMS technology is viable for a given application, and if so, what machines should comprise the FMS and what parts should be produced on it, can be a difficult task. Manual methods suffice only for situations where a small number of FMS-type machines are to be considered and less than a few dozen candidate parts are to be chosen from. When both machines and parts are to be selected from a larger number of candidates, manual methods become cumbersome and time consuming, and computer-based decision aids become a necessity. This paper gives an overview of the required decision process, and then focuses on those stages for which computer-based decision aids can be used effectively. Particular decision aids are described, and case studies are cited to illustrate their motivation and use.     

A supervisory control paradigm for real-time control of flexible manufacturing systems

Most of the current academic flexible manufacturing system (FMS) scheduling research has focused on the derivation of algorithms or knowledge-based techniques for efficient FMS real-time control. Here, the limitations of this view are outlined with respect to effective control of actual real-time FMS operation. A more realistic paradigm for real-time FMS control is presented, based on explicit engineering of human and automated control functions and system interfaces. To illustrate design principles within the conceptual model, an example of algorithmic and operator function models for a specific real-time FMS control problem are developed.Portions of this paper have appeared in: Proc. 2nd ORSA/TIMS Conf. on Flexible Manufacturing Systems: Operations Research Models and Applications, Ann Arbor, Michigan, August 12–15, 1986, and Proc. 1986 Int. Conf. on Systems, Man, and Cybernetics, Atlanta, Georgia, October 14–17, 1986.This research was supported in part by the New Faculty Research Program of the Georgia Institute of Technology.     

Piecewise deterministic Markov process model for flexible manufacturing systems with preventive maintenance

In this paper, we consider a maintenance and production model of a flexible manufacturing system. The maintenance activity involves lubrication, routine adjustments, etc., which reduce the machine failure rates and therefore reduce the aging of the machines. The objective of the problem is to choose the rate of maintenance and the rate of production that minimize the overall costs of inventory/shortage, production, and maintenance. It is shown that the value function is locally Lipschitz. Then, the existence of the optimal control policy is shown, and necessary and sufficient conditions for optimality are obtained.This research has been supported by NSERC-Canada, Grant OGP-003644 and FCAR-NC0271F.     

The optimality of balancing workloads in certain types of flexible manufacturing systems

Symmetric mathematical programming is used to analyze the optimality of balancing workloads to maximize the expected production in a single-server closed queuing network model of a flexible manufacturing system (FMS). In particular, using generalized concavity we prove that, even though the production function is not concave, balancing workloads maximizes the expected production in certain types of m-machine FMS's with n parts in the system. Our results are compared and contrasted with previous models of production systems.     

A Petri Net based algorithm for minimizing total tardiness in flexible manufacturing systems

Petri Nets have been extensively used for modeling and simulating of the dynamics of flexible manufacturing systems. Petri Nets can capture features such as parallel machines, alternative routings, batch sizes, multiplicity of resources, to name but a few. However, Petri Nets have not been very popular for scheduling in manufacturing due to the Petri Net “state explosion” combined with the NP-hard nature of many of such problems. A promising approach for scheduling consists of generating only portions of the Petri Net state space with heuristic search methods. Thus far, most of this scheduling work with Petri Nets has been oriented to minimize makespan. The problem of minimizing total tardiness and other due date-related criteria has received little attention. In this paper, we extend the Beam A^* Search algorithm presented in a previous work with capability to handle the total tardiness criterion. Computational tests were conducted on Petri Net models of both flexible job shop and flexible manufacturing systems. The results suggest that the Petri Net approach is also valid to minimize due date related criteria in flexible systems.     

Queueing models for a flexible machining station Part II: The method of Coxian phases

A work station of a flexible manufacturing system (fms) is modeled as a multi-server queue with finite waiting room. The interarrival/service time distributions have squared coefficients of variations not less than 0.5 and are modeled as Coxian laws of two phases. A recursive scheme is developed to calculate the equilibrium queue length distribution. The model, together with the diffusion approximation model of Part I, can be used to aid the design of fms work stations.     

On modeling failure and repair times in stochastic models of manufacturing systems using generalized exponential distributions

Failures of machines have a significant effect on the behavior of manufacturing systems. As a result it is important to model this phenomenon. Many queueing models of manufacturing systems do incorporate the unreliability of the machines. Most models assume that the times to failure and the times to repair of each machine are exponentially distributed (or geometrically distributed in the case of discrete-time models). However, exponential distributions do not always accurately represent actual distributions encountered in real manufacturing systems. In this paper, we propose to model failure and repair time distributions bygeneralized exponential (GE) distributions (orgeneralized geometric distributions in the case of a discretetime model). The GE distribution can be used to approximate distributions with any coefficient of variation greater than one. The main contribution of the paper is to show that queueing models in which failure and repair times are represented by GE distributions can be analyzed with the same complexity as if these distributions were exponential. Indeed, we show that failures and repair times represented by GE distributions can (under certain assumptions) be equivalently represented by exponential distributions.This work was performed while the author was visiting the Laboratory for Manufacturing and Productivity, Massachusetts Institute of Technology, Cambridge, MA 02139, USA.     

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.