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.     

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

The part families problem in flexible manufacturing systems

Parts grouping into families can be performed in flexible manufacturing systems (FMSs) to simplify two classes of problems: long horizon planning and short horizon planning. In this paper the emphasis is on the part families problem applicable to the short horizon planning. Traditionally, parts grouping was based on classification and coding systems, some of which are reviewed in this paper. To overcome the drawbacks of the classical approach to parts grouping, two new methodologies are developed. The methodologies presented are very easy to implement because they take advantage of the information already stored in the CAD system. One of the basic elements of this system is the algorithm for solving the part families problem. Some of the existing clustering algorithms for solving this problem are discussed. A new clustering algorithm has been developed. The computational complexity and some of the computational results of solving the part families problem are also discussed.     

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 fuzzy logic-based hybrid estimation of distribution algorithm for distributed permutation flowshop scheduling problems under machine breakdown

As the research interest in distributed scheduling is growing, distributed permutation flowshop scheduling problems (DPFSPs) have recently attracted an increasing attention. This paper presents a fuzzy logic-based hybrid estimation of distribution algorithm (FL-HEDA) to address DPFSPs under machine breakdown with makespan criterion. In order to explore more promising search space, FL-HEDA hybridises the probabilistic model of estimation of distribution algorithm with crossover and mutation operators of genetic algorithm to produce new offspring. In the FL-HEDA, a novel fuzzy logic-based adaptive evolution strategy (FL-AES) is adopted to preserve the population diversity by dynamically adjusting the ratio of offspring generated by the probabilistic model. Moreover, a discrete-event simulator that models the production process under machine breakdown is applied to evaluate expected makespan of offspring individuals. The simulation results show the effectiveness of FL-HEDA in solving DPFSPs under machine breakdown.     

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.     

Optimal and Heuristic Procedures for Row Layout Problems in Automated Manufacturing Systems

In many automated manufacturing environments, particularly flowlines and flexible manufacturing systems (FMSs), machines are arranged along a straight material handling track with a material handling device moving jobs from one machine to aother. These layouts are referred to as row machine layouts. In this paper we study the Row Layout Problem (RLP) under the design objective of minimizing the total backtracking distance of the material handling device, which is a NP-complete problem. We propose the use of a dynamic programming algorithm for its solution. Special cases of the problem, usually encountered in flexible manufacturing cells and which can be solved with polynomial procedures, are also discussed. For the equidistant case (i.e., successive candidate locations are in equal distances), we formulate the problem as an integer linear program. The use of standard mathematical programming codes can efficiently solve this formulation. Two effective heuristic procedures, which explore simple ideas based on local optimality conditions, are also presented. Extensive computational results demonstrate the effectiveness of such heuristics.     

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.     

求解随机凸规划概率约束问题的对偶算法

1引言随机规划中的概率约束问题在工程和管理中有广泛的应用.因为问题中包含非线性的概率约束,它们的求解非常困难.如果目标函数是线性的,问题的求解就比较容易.给出了一个求解随机线性规划概率约束问题的综述.原-对偶算法和切平面算法是比较有效的.在本文中,我们讨论随机凸规划概率约束问题:     

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 population dynamics model with strong maternal care

A two-sex age-structured nondispersing population dynamics deterministic model is presented taking into account strong maternal and weak paternal care of offspring. The model includes a weighted harmonic-mean type pair formation function and neglects the spatial dispersal and separation of pairs. It is assumed that each sex has pre-reproductive and reproductive age intervals. All adult individuals are divided into single males, single females, permanent pairs, and female-widows taking care of their offsprings after the death of their partners. All pairs are of two types: pairs without offspring under parental care at the given time and pairs taking child care. All individuals of pre-reproductive age are divided into young and juvenile groups. The young offspring are assumed to be under parental or maternal (after the death of their father) care. Juveniles can live without parental or maternal care but they cannot reproduce offsprings. It is assumed that births can only occur from couples. The model consists of nine integro-PDEs subject to the conditions of integral type. A class of separable solutions is studied, and a system for macro-moments evolving in time is derived in the case of age-independent vital ones. __________ Translated from Lietuvos Matematikos Rinkinys, Vol. 46, No. 2, pp. 215–255, April–June, 2006.     

Job Shop Scheduling with Tooling Constraints: a Tabu Search Approach

Flexible manufacturing systems (FMSs) are automated factories in which many different part types are produced simultaneously. The tool-loading problem now adds further to the delicate task of finding an optimal schedule for such systems. In this paper, a tabu search approach is developed to solve the job shop scheduling problem with tooling constraints.     

Flowshop Scheduling of Robotic Cells with Job-dependent Transportation and Set-up Effects

A flexible manufacturing cell consisting of two machining centres, several automated storage/retrieval stations, and a mobile transporting robot is considered. The problem is to schedule jobs on machines so as to minimize the makespan, with the effects of transportation and set-ups to be taken into account. The problem is studied with the aid of a graph model, and an exact algorithm of cubic complexity is derived based on the Gilmore–Gomory algorithm for the travelling salesman problem.     

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.     

Probabilistic proximity searching algorithms based on compact partitions

The main bottleneck of the research in metric space searching is the so-called curse of dimensionality, which makes the task of searching some metric spaces intrinsically difficult, whatever algorithm is used. A recent trend to break this bottleneck resorts to probabilistic algorithms, where it has been shown that one can find 99% of the relevant objects at a fraction of the cost of the exact algorithm. These algorithms are welcome in most applications because resorting to metric space searching already involves a fuzziness in the retrieval requirements. In this paper, we push further in this direction by developing probabilistic algorithms on data structures whose exact versions are the best for high dimensions. As a result, we obtain probabilistic algorithms that are better than the previous ones. We give new insights on the problem and propose a novel view based on time-bounded searching. We also propose an experimental framework for probabilistic algorithms that permits comparing them in offline mode.     

Earliness–tardiness production planning for just-in-time manufacturing: A unifying approach by goal programming

With popularity of the just-in-time (JIT) philosophy, researchers have started to seek the integration of Manufacturing Resource Planning (MRP-II) and JIT methodologies. This paper deals with the master production planning problem for a mass manufacturing system in the JIT environment, an earliness–tardiness production planning (ETPP) problem. The objective is to determine the optimum production rate for each product so that the total penalties imposed on the early and tardy production for all production periods be minimized. A goal programming (GP) approach is proposed to formulate the ETPP problem in a more generalized form, which includes several existing models in one unifying model. Moreover, the proposed GP algorithm ensures a global optimum solution, while the existing ones did not. In addition, it also possesses the advantages over others, such as easier to comprehend, easier to solve, and easier to extend it to the problem of multiple goals.     

Similarity-based inference as evidential reasoning

The guiding principle underlying most approaches to similarity-based reasoning (SBR) is the common idea that “similar causes bring about similar effects”. We propose a probabilistic framework of SBR which is based on a formal model of this assumption. This model, called a similarity profile, provides a probabilistic characterization of the similarity relation between observed cases (instances). A probabilistic approach seems reasonable since it adequately captures the heuristic (and hence uncertain) nature of the above hypothesis. Taking the concept of a similarity profile as a point of departure, we develop an inference scheme in which instance-based evidence is represented in the form of belief functions. The combination of evidence derived from individual cases can then be considered as a problem of information fusion. In this connection, we also address the problem of rating individual cases, and of modulating their influence on the prediction which is finally derived.     

Variance-constrained dissipative observer-based control for a class of nonlinear stochastic systems with degraded measurements

This paper is concerned with the variance-constrained dissipative control problem for a class of stochastic nonlinear systems with multiple degraded measurements, where the degraded probability for each sensor is governed by an individual random variable satisfying a certain probabilistic distribution over a given interval. The purpose of the problem is to design an observer-based controller such that, for all possible degraded measurements, the closed-loop system is exponentially mean-square stable and strictly dissipative, while the individual steady-state variance is not more than the pre-specified upper bound constraints. A general framework is established so that the required exponential mean-square stability, dissipativity as well as the variance constraints can be easily enforced. A sufficient condition is given for the solvability of the addressed multiobjective control problem, and the desired observer and controller gains are characterized in terms of the solution to a convex optimization problem that can be easily solved by using the semi-definite programming method. Finally, a numerical example is presented to show the effectiveness and applicability of the proposed algorithm.     

改进二元分布估计算法求解置换流水车间调度问题

针对置换流水车间调度这类组合最优化问题的求解,提出了一种改进二元分布估计算法(Improved binary estimation distribution algorithm, I-EDA)。算法以二元分布估计算法为架构,使用NEH(Nawaz-Enscore-Ham)启发式算法生成初始解,提高了初始解的质量;通过对优势解的统计采样构建位置矩阵模型和链接矩阵模型,依照两个矩阵模型的合并概率组合链接区块产生子代。提出了NEH插入式重组策略和基于位置概率的交换策略和两种全新局部搜索机制替代原二元分布估计算法的相邻交换法,以进一步筛选优势解。最后通过对Reeves标准测试集的仿真实验和算法比较验证了所提出算法的有效性。