Managing variances in manufacturing system design

The goal of this paper is to investigate how uncertainties in demand and production should be incorporated into manufacturing system design problems. We examine two problems in manufacturing system design: the resource allocation problem and the product grouping problem. In the resource allocation problem, we consider the issue of how to cope with uncertainties when we utilize two types of resources: actual processing capacity and stored capacity (inventory). A closed form solution of the optimal allocation scheme for each type of capacity is developed, and its performance is compared to that of the conventional scheme where capacity allocation and inventory control decisions are made sequentially. In the product grouping problem, we consider the issue of how we design production lines when each line is dedicated to a certain set of products. We formulate a mathematical program in which we simultaneously determine the number of production lines and the composition of each line. Two heuristics are developed for the problem.     

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.     

可重构制造系统重组过程中设备选择模型的研究

根据生产任务选择加工设备进行制造资源重组是实现可重构制造系统的关键问题之一，由于设备的选择涉及到多种因素，既有定量指标，又有定性指标，传统的依靠人工经验的方法显得力不从心。本文首先结合实际情况，提出了一套设备选择评价体系，通过对模糊判断矩阵采用最小对数二乘法确定各评价因素的权重系数，针对定性指标和定量指标采用不同的方法确定其性能指标值，通过模糊积分对评判指标进行综合评判，最后进行了实例研究。所提出的方法有效地简化了决策过程，为可重构制造系统设备选择提供了一套行之有效的方法。     

Auxiliary tool allocation in flexible manufacturing systems

This paper analyses a new approach to the machine loading problem arising in flexible manufacturing systems (FMSs). This approach allows the operations to be assigned to machines assuming that machines have access to all the tools required for their operations. This exploits the flexibility of the FMS completely. Next an allocation of tools to machines is determined which satisfies the tool requirements for each machine and minimizes the total number of tools. Thus this approach minimizes the unnecessary tool duplications in the system and maximizes the tool utilization. The problem is modeled as an integer linear program (ILP). We notice that the main problem has a block diagonal structure which is decomposable by relaxing a set of linking constraints. Each separated sub-problem represents a problem of allocation of a single type of tools. We develop a branch-and-bound based exact solution procedure and three heuristic procedures to solve the sub-problems. Our lower bounding approach uses Lanrangean relaxation. The solutions to the Lagrangean relaxation are further used to determine the branching sequences and to develop heuristic approaches. Since finding even a feasible solution to the main problem is NP-hard, we develop only enumerative procedures to solve the main problem. Finally, these solution procedures are tested on randomly generated test problems.     

A multi-class multi-level capacitated lot sizing model

When demand loading is higher than available capacity, it takes a great deal of effort for a traditional MRP system to obtain a capacity-feasible production plan. Also, the separation of lot sizing decisions and capacity requirement planning makes the setup decisions more difficult. In a practical application, a production planning system should prioritize demands when allocating manufacturing resources. This study proposes a planning model that integrates all MRP computation modules. The model not only includes multi-level capacitated lot sizing problems but also considers multiple demand classes. Each demand class corresponds to a mixed integer programming (MIP) problem. By sequentially solving the MIP problems according to their demand class priorities, this proposed approach allocates finite manufacturing resources and generates feasible production plans. In this paper we experiment with three heuristic search algorithms: (1) tabu search; (2) simulated annealing, and (3) genetic algorithm, to solve the MIP problems. Experimental designs and statistical methods are used to evaluate and analyse the performance of these three algorithms. The results show that tabu search and simulated annealing perform best in the confirmed order demand class and forecast demand class, respectively.     

Optimal bivariate clustering and a genetic algorithm with an application in cellular manufacturing

The problem of bivariate clustering for the simultaneous grouping of rows and columns of matrices was addressed with a mixed-integer linear programming model. The model was solved using conventional methodology for very small problems but solving even small to moderate-sized problems was a formidable challenge. Because of the NP-complete nature of this class of problems, a genetic algorithm was developed to solve realistically sized problems of larger dimensions. A commonly encountered example is the simultaneous clustering of parts into part families and machines into machine cells in a cellular manufacturing context for group technology. The attractiveness of employing the optimization model (with objective function being a sum of dissimilarity measures) to provide simultaneous grouping of part types and machine types was compared to solutions found by employing the commonly used grouping efficacy measure. For cellular manufacturing problem instances from the literature, the intrinsic differences between the objective of the proposed model and grouping efficacy is highlighted. The solution to the general model found by employing a genetic algorithm solution technique and applying a simple heuristic was shown to perform as well as other algorithms to find the commonly accepted best known solutions for grouping efficacy. Further examples in industrial purchasing behavior and market segmentation help reveal the general applicability of the model for obtaining natural clusters.     

Heuristics for determining economic processing rates in a flexible manufacturing system

In this paper, models are presented for determining economic processing speeds and tool loading to minimize the makespan required to produce a given set of parts in a flexible manufacturing system. Using Taylor's tool life equation, models for determining the optimal processing speeds and the tools to be loaded into finite capacity machine magazines are formulated to minimize the maximum processing time in the system. These problems are evaluated for computational complexity, and several heuristics for obtaining good feasible solutions to the problem are discussed. The quality of the solutions obtained using these heuristics is evaluated by computational experiments against lower bounds established by either relaxations or optimal solutions when possible.     

Hierarchical controls in stochastic manufacturing systems with machines in tandem

This paper presents an asymptotic analysis of hierarchical production planning in a manufacturing system with serial machines that are subject to breakdown and repair, and with convex costs. The machines capacities are modeled as Markov chains. Since the number of parts in the internal buffers between any two machines needs to be non-negative, the problem is inherently a state constrained problem. As the rate of change in machines states approaches infinity, the analysis results in a limiting problem in which the stochastic machines capacity is replaced by the equilibrium mean capacity. A method of “lifting” and “modification” is introduced in order to construct near optimal controls for the original problem by using near optimal controls of the limiting problem. The value function of the original problem is shown to converge to the value function of the limiting problem, and the convergence rate is obtained based on some a priori estimates of the asymptotic behavior of the Markov chains. As a result, an error estimate can be obtained on the near optimality of the controls constructed for the original problem.     

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.     

Approaches to Machine Load Balancing in Flexible Manufacturing Systems

The load balancing problem for a flexible manufacturing system concerns the allocation of operations to machines and of tools to magazines with limited capacity, while seeking to balance the workload on all machines. Previous attempts to tackle this problem have used integer programming and a specialized branch and bound procedure has been developed. A modified integer programming approach is proposed here. The problem has certain features which can be used advantageously for an approximate solution technique. The approximation technique is described and computational results presented. Extensions to the problem of pooling machines are also considered.     

Analysis of a finite capacity assembly system

Consider a finite capacity automatic assembly system consisting of a set of tandem work stations linked by a material handling system. Each work station consists of a set of machines and a local preprocessed inventory. The material handling system consists of a set of continuous line conveyors. Each conveyor has a beginning and an end with a specified length, velocity and capacity. The performance of the above manufacturing system is analyzed based on a mixed queuing network model, in the steady state. A methodology is presented for controlling blocking of the manufacturing system such that the probability of finding either a work station or a conveyor blocked will be sufficiently close to zero. Finally, numerical results are provided and the concluding remarks are discussed.     

Complexity of Buffer Capacity Allocation Problems for Production Lines with Unreliable Machines

Buffer capacity allocation problems for flow-line manufacturing systems with unreliable machines are studied. These problems arise in a wide range of manufacturing systems and concern determining buffer capacities with respect to a given optimality criterion which can depend on the average production rate of the line, buffer cost, inventory cost, etc. Here, this problem is proven to be NP-hard for a tandem production line and oracle representation of the revenue and cost functions, and NP-hard for a series-parallel line and stepwise revenue function.     

柔性制造系统的载荷模型和对偶分解算法

本文研究柔性制造系统最优排序问题的载荷模型，通过优化系统的最优利用率并考虑系统各机器的工作平衡，本文给出了载荷问题三个新的优化模型，这些模型形成具有０－１变量和一般整型变量的大规模整数规划问题，根据分解理论，考虑到问题的变量特性，这些大规模问题可被分解成若干维数较低的子问题求解，文章还给出了一个对偶分解算法。     

Machine-part cell formation using biclustering

Cellular manufacturing is the cornerstone of many modern flexible manufacturing techniques, taking advantage of the similarities between parts in order to decrease the complexity of the design and manufacturing life cycle. Part-Machine Grouping (PMG) problem is the key step in cellular manufacturing aiming at grouping parts with similar processing requirements or similar design features into part families and by grouping machines into cells associated to these families. The PMG problem is NP-complete and the different proposed techniques for solving it are based on heuristics. In this paper, a new approach for solving the PMG problem is proposed which is based on biclustering. Biclustering is a methodology where rows and columns of an input data matrix are clustered simultaneously. A bicluster is defined as a submatrix spanned by both a subset of rows and a subset of columns. Although biclustering has been almost exclusively applied to DNA microarray analysis, we present that biclustering can be successfully applied to the PMG problem. We also present empirical results to demonstrate the efficiency and accuracy of the proposed technique with respect to related ones for various formations of the problem.     

Design of cellular manufacturing systems using Latent Semantic Indexing and Self Organizing Maps

A new, efficient clustering method for solving the cellular manufacturing problem is presented in this paper. The method uses the part-machine incidence matrix of the manufacturing system to form machine cells, each of which processes a family of parts. By doing so, the system is decomposed into smaller semi-independent subsystems that are managed more effectively improving overall performance. The proposed method uses Self Organizing Maps (SOMs), a class of unsupervised learning neural networks, to perform direct clustering of machines into cells, without first resorting to grouping parts into families as done by previous approaches. In addition, Latent Semantic Indexing (LSI) is employed to significantly reduce the complexity of the problem resulting in more effective training of the network, significantly improved computational efficiency, and, in many cases, improved solution quality. The robustness of the method and its computational efficiency has been investigated with respect to the dimension of the problem and the degree of dimensionality reduction. The effectiveness of grouping has been evaluated by comparing the results obtained with those of the k-means classical clustering algorithm.AMS classification: 62H30     

Manufacturing cell formation by state-space search

This paper addresses the problem of grouping machines in order to design cellular manufacturing cells, with an objective to minimize inter-cell flow. This problem is related to one of the major aims of group technology (GT): to decompose the manufacturing system into manufacturing cells that are as independent as possible. This problem is NP-hard. Thus, nonheuristic methods cannot address problems of typical industrial dimensions because they would require exorbitant amounts of computing time, while fast heuristic methods may suffer from poor solution quality. We present a branch-and-bound state-space search algorithm that attempts to overcome both these deficiencies. One of the major strengths of this algorithm is its efficient branching and search strategy. In addition, the algorithm employs the fast Inter-Cell Traffic Minimization Method to provide good upper bounds, and computes lower bounds based on a relaxation of merging.This work was supported in part by NSF Grants DDM-9201779, IRI-9306580, and NSFD EEC 94-02384 in the US, and the CMDS project (work order 019/7-148/CMDS-1039/90-91) in India. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.     

A Lagrangean relaxation based approach for the capacity allocation problem in flexible manufacturing systems

This study considers the operation assignment and capacity allocation problem in flexible manufacturing systems. A set of operations is selected to be processed and assigned to the machines together with their required tools. The purchase or usage of the required tools incurs a cost. The machines have scarce time and tool magazine capacities. The objective is to maximize the total weight of the assigned operations minus the total tooling costs. We use Lagrangean relaxation approach to obtain upper and lower bounds on the optimal objective function values. The computational experiments show that our approach provides near optimal bounds in reasonable solution times.     

Cell formation using fuzzy relational clustering algorithm

Cellular manufacturing is a useful way to improve overall manufacturing performance. Group technology is used to increase the productivity for manufacturing high quality products and improving the flexibility of manufacturing systems. Cell formation is an important step in group technology. It is used in designing good cellular manufacturing systems. The key step in designing any cellular manufacturing system is the identification of part families and machine groups for the creation of cells that uses the similarities between parts in relation to the machines in their manufacture. There are two basic procedures for cell formation in group technology. One is part-family formation and the other is machine–cell formation. In this paper, we apply a fuzzy relational data clustering algorithm to form part families and machine groups. A real data study shows that the proposed approach performs well based on the grouping efficiency proposed by Chandrasekharan and Rajagopalan.     

Bond Energy,Rectilinear Distance and a Worst-case Bound for the Group Technology Problem

The machine-part relation in the group technology problem can be represented by a 0-1 matrix A where the rows represent the machines and the columns stand for the parts. The grouping of machines and parts into families is then equivalent to clustering the rows and the columns of A so that the resulting matrix may review some useful patterns of the original data. One frequently used objective function is the total ‘bond energy’ between the rows and the columns, which is a quadratic assignment problem formulation. We will show that this formulation is equivalent to solving two rectilinear travelling-salesman problems. On the basis of this observation, we propose a new approach to solve the group technology problem and establish a new worst-case bound for this problem.     

Exploiting process plan flexibility in production scheduling: A multi-objective approach

When solving a product/process design problem, we must exploit the available degrees of freedom to cope with a variety of issues. Alternative process plans can be generated for a given product, and choosing one of them has implications on manufacturing functions downstream, including planning/scheduling. Flexible process plans can be exploited in real time to react to machine failures, but they are also relevant for off-line scheduling. On the one hand, we should select a process plan in order to avoid creating bottleneck machines, which would deteriorate the schedule quality; on the other one we should aim at minimizing costs. Assessing the tradeoff between these possibly conflicting objectives is difficult; actually, it is a multi-objective problem, for which available scheduling packages offer little support. Since coping with a multi-objective scheduling problem with flexible process plans by an exact optimization algorithm is out of the question, we propose a hierarchical approach, based on a decomposition into a machine loading and a scheduling sub-problem. The aim of machine loading is to generate a set of efficient (non-dominated) solutions with respect to the load balancing and cost objectives, leaving to the user the task of selecting a compromise solution. Solving the machine loading sub-problem essentially amounts to selecting a process plan for each job and to routing jobs to the machines; then a schedule must be determined. In this paper we deal only with the machine loading sub-problem, as many scheduling methods are already available for the problem with fixed process plans. The machine loading problem is formulated as a bicriterion integer programming model, and two different heuristics are proposed, one based on surrogate duality theory and one based on a genetic descent algorithm. The heuristics are tested on a set of benchmark problems.