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.     

A survey of the perturbation analysis of discrete event dynamic systems

This paper introduces an analysis and optimization technique for discrete event dynamic systems, such as flexible manufacturing systems (FMSs), and other discrete part production processes. It can also be used for enhancement of the simulation results of, or the monitoring of the operations of such systems in real time. Extensive references are given where readers may pursue futher details.     

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.     

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.     

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.     

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.     

Maximal coupling and rare perturbation sensitivity analysis

In this article, we introduce a new method for obtaining the ersatz sample derivatives useful in sensitivity analysis: the maximal coupling RPA method.     

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.     

Hierarchical production control of a flexible manufacturing system

A hierarchical production control framework for a flexible manufacturing system is proposed. The machines in the system are subject to failures in a wide spectrum band. At first, failures are clustered near some discrete points on the failure spectrum in order to define the hierarchical model. Each level in the hierarchy corresponds to a discrete point on the failure spectrum. At each level, faster varying failures are modelled by their mean behaviour, and more slowly varying failures are treated as static. Then, a hierarchical controller of multiple time scale type is proposed. System control at each level is based on the work of Kimemia and Gershwin. Simulation results conclude the paper.     

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.     

Queueing network modelling of flexible manufacturing system using mean value analysis

In the present investigation, we develop queueing model for the performance prediction of flexible manufacturing systems (FMSs) with a multiple discrete material-handling devices (MHD). An iterative method has been suggested using mean value analysis (MVA) for the state-dependent routing. Two queueing network models are considered to determine the material-handling device interference. In the first one, we model the interference from the MHD by inflating the station service times but neglect queueing at the MHD. In another network, the queueing for the MHD is taken into consideration. The performance of FMS configuration is obtained by iterating between two networks. The suggested algorithms demonstrate better results than the algorithm used by earlier workers for single MHD. Some performance indices viz. throughput, mean service time, mean waiting time, etc. are obtained. Numerical results are provided to highlight the effect of the system parameters on performance indices, which are further evaluated by using neuro-fuzzy controller system to validate the tactability of soft computing approach.     

Development of a model for a two-station serial transfer line subject to machine and buffer failure

In modern automated production lines, it is common to connect pairs of machines with mechanical storage devices in order to provide buffering between processing stations. Since these devices are mechanical, they are prone to failure. Previous research concerning the analytical modeling of a class of production lines, the serial transfer line, assumes that these buffers are completely reliable. The concept of an unreliable buffer is introduced and an analytic model of a two machine line with an unreliable buffer is developed. It is proposed that this model will form the foundation for an analytic model of the more complex K > 2 machine serial transfer line with unreliable buffers.     

Optimal two-layer selection policy for a flexible manufacturing system

This paper deals with the selection problem in a manufacturing system. The manufacturing system consists of a flexible manufacturing cellC ₀ which feedsM flexible manufacturing cellsC _1i ,i=1, ...,M. In addition, each cellC _1i ,i=1, ...,M, is feeding several production lines. Sufficient conditions on optimal feedback selection policies for theM+1 flexible manufacturing cells are derived. These selection policies maximize the probability of the system output reaching some demand before any of the system buffers is being overflowed. A numerical study is conducted.     

Integrated cellular manufacturing systems design with production planning and dynamic system reconfiguration

This paper presents and analyzes a comprehensive model for the design of cellular manufacturing systems (CMS). A recurring theme in research is a piecemeal approach when formulating CMS models. In this paper, the proposed model, to the best of the authors’ knowledge, is the most comprehensive one to date with a more integrated approach to CMS design, where production planning and system reconfiguration decisions are incorporated. Such a CMS model has not been proposed before and it features the presence of alternate process routings, operation sequence, duplicate machines, machine capacity and lot splitting. The developed model is a mixed integer non-linear program. Linearization procedures are proposed to convert it into a linearized mixed integer programming formulation. Computational results are presented by solving some numerical examples, extracted from the existing literature, with the linearized formulation.     

Dynamic material handling for a class of flexible manufacturing systems

A real-time hierarchical routing control scheme for a large class of material handling systems is presented. The higher level (coordinator) performs resource allocation tasks and supplies parameter values to the lower (local control) level. The lower level operates in an autonomous (without continuous supervision) and distributed fashion. If state information is made available to the coordinator, the routing strategy can furthermore be adaptively adjusted.     

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.