装配系统的供应链排序问题

在装配系统中,有多个供应商向同一个制造商提供零部件,仅当一个产品的所有零部件都送到后,制造商才进行最后的组装与发送.假设制造商为非瓶颈式生产.研究目标为工件带权完工时间和及最大延误的装配系统供应链排序问题,利用排序的理论和方法,分别设计多项式时间算法,并分析算法的性能比.     

Stochastic design optimization of asynchronous flexible assembly systems

This paper presents the application of the stochastic quasigradient method (SQG) of Ermoliev and Gaivaronski to the performance optimization of asynchronous flexible assembly systems (AFAS). These systems are subject to blocking and starvation effects that make complete analytic performance modeling difficult. A hybrid algorithm is presented in this paper which uses a queueing network model to set the number of pallets in the system and then an SQG algorithm is used to set the buffer spacings to obtain optimal system throughput. Different forms of the SQG algorithm are examined and the specification of optimal buffer sizes and pallet numbers for a variety of assembly systems with ten stations are discussed. The combined Network-SQG method appears to perform well in obtaining a near optimal solution in this discrete optimization example, even though the SQG method was primarily designed for application to differentiable performance functionals. While a number of both theoretical and practical problems remain to be resolved, a heuristic version of the SQG method appears to be a reasonable technique for analyzing optimization problems for certain complex manufacturing systems.     

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.     

Design rules of flexible assembly and inspection cells

Every leading institution and manufacturing company in the world is dealing with some aspects of flexible automation. This is because they have found that designing and making goods and products on order rather than for stock is the key issue in cutting manufacturing costs and lead time, and eventually staying in business in the future. This paper discusses the way in which this above outlined goal can be implemented in the assembly business, as well as giving design rules on how to design flexible assembly and inspection cells and systems. The rules are justified by solid model simulation and the author's industrial and laboratory experience.     

A large scale machine loading problem in flexible assembly

Flexible manufacturing is characterized by versatile work stations with minimum change over times and a versatile material handling system. The loading problem in flexible manufacturing is to assign tools, material, operations and jobs to work stations in order to minimize the total number of job-to-work station assignments. In this paper, we describe a special case of the general loading problem applied to flexible assembly and develop a discrete optimization model. We then discuss approaches for obtaining good heuristic solutions and present results for a large scale study.     

Multi-level production scheduling for a class of flexible machining and assembly systems

A class of machining and assembly systems characterised by a flat assembly component structure, the existence of families of similar items, non-negligible setups and fast material flow between work-centres is considered. A hierarchical production scheduling framework is proposed for this class of systems. The decision problems at each level of the hierarchy are identified and formulated. The formulations constitute a sufficiently accurate reflection of reality, while at the same time leading to tractable mathematical models that can be handled by carefully chosen and adapted optimisation techniques. The models can, when combined with suitable knowledge bases form the core of an effective multi-pass, hierarchical decision support system. Possible srategies for coordinating the various decision problems at the different levels of the hierarchy are also discussed.This work was supported by the ACME Directorate of the Science and Engineering Research Council of the United Kingdom, Grant No. GR/D 51476, and was carried out in collaboration with Lucas Aerospace (Engines Division), Shaftmoor Lane, Birmingham, U.K.On leave from Warsaw University of Technology, Institute of Automatic Control, Nowowiejska 15/19, 00-665 Warszawa, Poland.     

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.     

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.     

Efficient Scheduling of Traffic on a Railway Line

Scheduling trains on a single railway line is an important issue in it own right and a building block for scheduling trains in railway networks. A local, state-dependent, travel-advance strategy combined with a discrete-event model of a railway line represents a more efficient way of approaching the scheduling problem than the nonlinear programming approach used in the past. The new approach produces suboptimal time-efficient and energy-efficient schedules and can be used for fast rescheduling in case of significant perturbation in the schedule.     

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.     

Scheduling orders on either dedicated or flexible machines in parallel to minimize total weighted completion time

We are interested in the problem of scheduling orders for different product types in a facility with a number of machines in parallel. Each order asks for certain amounts of various different product types which can be produced concurrently. Each product type can be produced on a subset of the machines. Two extreme cases of machine environments are of interest. In the first case, each product type can be produced on one and only one machine which is dedicated to that product type. In the second case, all machines are identical and flexible; each product type can be produced by any one of the machines. Moreover, when a machine in this case switches over from one product type to another, no setup is required. Each order has a release date and a weight. Preemptions are not allowed. The objective is minimizing the total weighted completion time of the orders. Even when all orders are available at time 0, both types of machine environments have been shown to be NP-hard for any fixed number (≥2) of machines. This paper focuses on the design and analysis of approximation algorithms for these two machine environments. We also present empirical comparisons of the various algorithms. The conclusions from the empirical analyses provide insights into the trade-offs with regard to solution quality, speed, and memory space. Electronic Supplementary Material The online version of this article () contains supplementary material, which is available to authorized users. This research is supported by the National Science Foundation through grants DMI-0300156 and DMI-0245603.     

Revenue-maximizing pricing and scheduling strategies in service systems with flexible customers

We propose a model of service operations systems in which customers are heterogeneous both in terms of their private delay sensitivity and flexibility. A service provider maximizes revenue through jointly optimal pricing and steady-state scheduling strategies. We provide a complete analysis for this generally intractable problem. Interestingly, when one queue accommodates a large population of impatient customers, it may be desirable to strategically idle the server in the other queue, which is a phenomenon new to the literature.     

Rollout Algorithms for Stochastic Scheduling Problems

Stochastic scheduling problems are difficult stochastic control problems with combinatorial decision spaces. In this paper we focus on a class of stochastic scheduling problems, the quiz problem and its variations. We discuss the use of heuristics for their solution, and we propose rollout algorithms based on these heuristics which approximate the stochastic dynamic programming algorithm. We show how the rollout algorithms can be implemented efficiently, with considerable savings in computation over optimal algorithms. We delineate circumstances under which the rollout algorithms are guaranteed to perform better than the heuristics on which they are based. We also show computational results which suggest that the performance of the rollout policies is near-optimal, and is substantially better than the performance of their underlying heuristics.     

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.     

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.     

Impact of flexible machines on automated manufacturing systems

Although the problem of scheduling dynamic job shops is well studied, setup and changeover times are often assumed to be negligibly small and therefore ignored. In cases where the product mix changes occur frequently, setup and changeover times are of critical importance. This paper applies some known results from the study of multi-class single-server queues with setup and changeover times to develop an approximation for evaluating the performance of job shops. It is found that the product mix, setup and changeover times, and scheduling rules affect the performance significantly, in particular at high levels of machine utilisation. This approach could be used to determine the required level of flexibility of machines and to choose an appropriate scheduling policy such that production rates remain within acceptable limits for foreseeable changes in the product mix.     

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.     

Scheduling uniform machines on-line requires nondecreasing speed ratios

We consider the following on-line scheduling problem. We have to schedulen independent jobs, wheren is unknown, onm uniform parallel machines so as to minimize the makespan; preemption is allowed. Each job becomes available at its release date, and this release date is not known beforehand; its processing requirement becomes known at its arrival. We show that if only a finite number of preemptions is allowed, there exists an algorithm that solves the problem if and only ifs _i–1/s_i s_i/s_i+1 for alli = 2,,m – 1, wheres _i denotes theith largest machine speed. We also show that if this condition is satisfied, then O(mn) preemptions are necessary, and we provide an example to show that this bound is tight. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.     

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.