Multi-level scheduling decisions in a class of FMS using simulation based metamodels

This paper pertains to a detailed simulation study conducted on a typical Flexible Manufacturing System (FMS). Initially, the configurations of the FMS under study have been established. Two types of FMSs have been evolved: one is failure free and the other is failure prone. For each of these cases, simulation models have been developed using SLAMSYSTEM. Orders arriving randomly at the FMS are subjected to three levels of scheduling decisions namely, launching of parts into the system, routing of parts through machines and sequencing of parts on AGVs at a central buffer. The simulation results have been used to develop metamodels for the two types of FMSs. These metamodels have been subjected to statistical analysis to ascertain their adequacy to represent the simulation models. These metamodels have been found to be useful for simulating the FMSs under study so as to evaluate various multi-level scheduling decisions in the FMS.     

An improved part grouping model for minimizing makespan in FMS

In some flexible manufacturing systems (FMSs), limited tool magazine capacity requires grouping of parts into subsets for production. Although several studies have addressed the part grouping issue, research comparing the performance of models is scanty. Moreover, there is no congruency in the objectives of the present part grouping models and subsequent loading models. Traditionally, part grouping is addressed before machine loading. In this study, we overcome the drawbacks by proposing two models: model LM, which does not require part grouping, and model PGLRM (part grouping, loading and routing model), which requires part grouping. The performance of model LM serves as a benchmark. These two models also address machine loading and part routing issues concurrently. Model PGLRM's performance is then compared with the performance of model LM and few other existing part grouping models in terms of makespan and routing flexibility. Our analysis shows that model PGLRM not only results in a lower value of makespan but also imparts higher routing flexibility as compared to existing part grouping models.     

Optimal dynamic routing in Flexible Manufacturing Systems with limited buffers

An optimal routing policy is obtained for Flexible Manufacturing Systems (FMSs) with limited buffers at the work stations. This policy is used to effectively drive a robotic material handling system. The routing decisions are made by a supervising computer on a real-time basis in order to avoid any work station running out of inputs and to control the blocking of the material handling system. Using our model, general material handling times can be assumed. The optimal policy and several key performance measures are computed, following the problem formulation as a continuous-time, semi-Markovian decision process. Fast convergence and computational stability are ensured by the ergodic solution algorithm augmented to solve the functional equations of the renewal process. The solution algorithm was implemented, tested on an extensive range of problems regarding the structure and the performance of the optimal policy. Complex environments involving diverse processing times, as well as very limited buffer storage, were examined. The interaction between the allocation of buffer spaces to work stations, the structural properties of the optimal monotone (threshold-type) policy and the system performance are also investigated.     

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.     

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.     

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

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.     

Routing trains through a railway station based on a node packing model

In this paper, we describe the problem of routing trains through a railway station. This routing problem is a subproblem of the automatic generation of timetables for the Dutch railway system. The problem of routing trains through a railway station is the problem of assigning each of the involved trains to a route through the railway station, given the detailed layout of the railway network within the station and given the arrival and departure times of the trains. When solving this routing problem, several aspects such as capacity, safety, and customer service have to be taken into account. In this paper, we describe this routing problem in terms of a weighted node packing problem. Furthermore, we describe an algorithm for solving this routing problem to optimality. The algorithm is based on preprocessing, valid inequalities, and a branch-and-cut approach. The preprocessing techniques aim at identifying superfluous nodes which can be removed from the problem instance. The characteristics of the preprocessing techniques with respect to propagation are investigated. We also present the results of a computational study in which the model, the preprocessing techniques and the algorithm are tested based on data related to the railway stations Arnhem, Hoorn and Utrecht CS in the Netherlands.     

An estimation of distribution algorithm for scheduling problem of flexible manufacturing systems using Petri nets

Based on the place-timed Petri net models of flexible manufacturing systems (FMSs), this paper proposes a novel effective estimation of distribution algorithm (EDA) for solving the scheduling problem of FMSs. A candidate solution is represented as an individual with two sections: the first contains the route information while the second is a permutation with repetition for parts. The feasibility of individuals is checked and guaranteed by a highly permissiveness deadlock controller. A feasible individual is interpreted into a deadlock-free schedule while the infeasible ones are amended. The probabilistic model in EDA is constructed via a voting procedure. An offspring individual is then produced based on the model from a seed individual, and the set of seed individuals is extracted by a roulette method from the current population. The longest common subsequence is also embedded into the probabilistic model for mining good genes. A modified variable neighborhood search is applied on offspring individuals to obtain better solutions in their neighbors and hence to improve EDA’s performance. Computational results show that our proposed algorithm outperforms all the existing ones on benchmark examples for the studied problem. It is of important practice significance for the manufacturing of time-critical and multi-type products.     

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.     

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.     

Cooperative dispatching – exploiting the flexibility of an FMS by means of incremental optimization

We present a new control scheme for releasing parts into a flexible manufacturing system (FMS) that is based on incremental optimization. Our objective is to exploit the available routing flexibility of parts in an enhanced manner by viewing part release as an assignment problem using system status information. In particular, we propose an “intelligent” part release mechanism with some look-ahead and optimization features in order to allow for optimization-based “cooperation” of workcenters. The cooperative dispatching concept is implemented in an object-oriented computer simulation model, and experiments with a varying degree of average routing flexibility are performed. The experimental results are used for a statistical analysis of the benefits of cooperative dispatching versus the common approach of standard dispatching. Finally, we investigate the robustness of the presented FMS control scheme in the case of random machine breakdowns.     

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.     

Mathematical programming approaches for dual multicast routing problem with multilayer risk cost

This paper addresses a dual multicast routing problem with shared risk link group (SRLG) diverse costs (DMR-SRLGD) that arises from large-scale distribution of realtime multicast data (e.g., internet protocol TV, videocasting, online games, stock price update). The goal of this problem is to find two redundant multicast trees, each from one of the two sources to every destination at a minimum cost. The cost of the problem contains two parts: the multicast routing cost and the shard common risk cost. Such common risk could cause the failures of multiple links simultaneously. Therefore, the DMR-SRLGD ensures the availability and reliability of multicast service. We formulate an edge-based model for the DMR-SRLGD. In addition, we also propose a path-based model that rises from the Dantzig-Wolfe decomposition of the edge-based model, and develop a column-generation framework to solve the linear relaxation of the path-based formulation. We then employ a branch-and-price solution method to find integer solutions to DMR-SRLGD. We also extend both edge-based and path-based models to handle the complex quality of service requirements. The computational results show the edge-based model is superior than the path-based model for the easy and small test instances, whereas the path-based model provides better solutions in a timely fashion for hard or large test instances.     

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.     

Fluid models of integrated traffic and multipath routing

In this paper we consider a stochastic model describing the varying number of flows in a network. This model features flows of two types, namely file transfers (with fixed volume) and streaming traffic (with fixed duration), and extends the model of Key, Massoulié, Bain and Kelly [27] by allowing more general bandwidth allocation criteria. We analyse the dynamics of the system under a fluid scaling, and show Lyapunov stability of the fluid limits under a natural stability condition. We provide natural interpretations of the fixed points of these fluid limits. We then compare the fluid dynamics of file transfers under (i) balanced multipath routing and (ii) parallel, uncoordinated routing. We show that for identical traffic demands, parallel uncoordinated routing can be unstable while balanced multipath routing is stable. Finally, we identify multi-dimensional Ornstein-Uhlenbeck processes as second-order approximations to the first-order fluid limit dynamics.     

The price of anarchy in an exponential multi-server

We consider two criteria for routing selection in a multi-server service station: the equilibrium and social optimization. The ratio between the average mean waiting times in these two routings is called the price of anarchy (PoA). We show that the worst-case PoA is precisely the number of servers.     

A heavy traffic limit theorem for a class of open queueing networks with finite buffers

We consider a queueing network of d single server stations. Each station has a finite capacity waiting buffer, and all customers served at a station are homogeneous in terms of service requirements and routing. The routing is assumed to be deterministic and hence feedforward. A server stops working when the downstream buffer is full. We show that a properly normalized d-dimensional queue length process converges in distribution to a fd-dimensional semimartingale reflecting Brownian motion (RBM) in a d-dimensional box under a heavy traffic condition. The conventional continuous mapping approach does not apply here because the solution to our Skorohod problem may not be unique. Our proof relies heavily on a uniform oscillation result for solutions to a family of Skorohod problems. The oscillation result is proved in a general form that may be of independent interest. It has the potential to be used as an important ingredient in establishing heavy traffic limit theorems for general finite buffer networks. This revised version was published online in June 2006 with corrections to the Cover Date.     

Improving the robustness in railway station areas

In order to improve the robustness of a railway system in station areas, this paper introduces an iterative approach to successively optimize the train routing through station areas and to enhance this solution by applying some changes to the timetable in a tabu search environment. We present our vision on robustness and describe how this vision can be used in practice. By introducing the spread of the trains in the objective function for the route choice and timetabling module, we improve the robustness of a railway system. Using a discrete event simulation model, the performance of our algorithms is evaluated based on a case study for the Brussels’ area. The computational results indicate an average improvement in robustness of 6.2% together with a decrease in delay propagation of about 25%. Furthermore, the effect of some measures like changing the train offer to further increase the robustness is evaluated and compared.