A hybrid simulated annealing for solving an extended model of dynamic cellular manufacturing system

This paper develops a mixed-integer programming model to design the cellular manufacturing systems (CMSs) under dynamic environment. In dynamic environment, the product mix and part demand change under a multi-period planning horizon. Thus, the best designed cells for one period may not be efficient for subsequent periods and reconfiguration of cells is required. Reconfiguration may involve adding, removing or relocating machines; it may also involve a change in processing rout of part types from a period to another. The advantages of the proposed model are as follows: considering the batch inter/intra-cell material handling by assuming the sequence of operations, considering alternative process plans for part types, and considering machine replication. The main constraints are maximal cell size and machine time-capacity. The objective is to minimize the sum of the machine constant and variable costs, inter- and intra-cell material handling, and reconfiguration costs. An efficient hybrid meta-heuristic based on mean field annealing (MFA) and simulated annealing (SA) so-called MFA–SA is used to solve the proposed model. In this case, MFA technique is applied to generate a good initial solution for SA. The obtained results show that the quality of the solutions obtained by MFA–SA is better than classical SA, especially for large-sized problems.     

Layout designs in cellular manufacturing

Cellular manufacturing (CM) is now an established international practice to integrate: equipment, people, and systems into `focused factories', `mini-businesses' or `cells' with clear customers, responsibilities and boundaries. The major elements in exploiting the benefits of CM is efficient layout designs. This paper presents the application of recently developed multi-objective inter- and intra-cell layout designs methodologies in a CM environment by the author to a dynamic food manufacturing and packaging company in Australia. Some of the problems expressed by the company were large and unnecessary volume of shop floor material handling cost, difficulties and confusion over production planning, long products lead times resulting in losing customers and high overhead costs. Furthermore the company was deeply concerned about the increasing number of accidents and injuries on the shop floor caused by poor layout of machinery and the lack of proper aisle structures for movement of the lift-trucks. This paper shows the process of developing the final inter-cell layout designs by providing the management with multiple layout configurations and showing the impact of each design on the material handling cost at each stage. These solutions not only provide a safer shop floor but also significant reductions in material handling cost, waste, need for large capital investment and the number of lift-trucks needed on the shop floor.     

Flexible machine layout design for dynamic and uncertain production environments

Flexible manufacturing systems operate in a dynamic environment and face considerable uncertainty in production demands. The development of a flexible machine layout is a critical issue in creating a system that can respond effectively to these requirements. Unlike most existing methods for creating flexible layout designs, the procedure developed in this paper is not restricted to equal size machines. It optimizes the trade-offs between increased material handling costs as requirements change and machine rearrangement costs needed to adapt the layout to these changes. The proposed flexible machine layout design procedure formulates and solves a robust machine layout design problem over a rolling horizon planning time window. The formulation, details of the solution methodology, illustrative examples, and computational results are presented.     

Layout design for flexible manufacturing systems considering single-loop directional flow patterns

To achieve high productivity in a flexible manufacturing system (FMS), an efficient layout arrangement and material flow path design are important due to the large percentage of product cost that is related to material handling. The layout design problem addressed in this paper has departments with fixed shapes and pick-up/drop-off points. It is an open-field type layout with single-loop directed flow path. A two-step heuristic is proposed to solve the problem. It first solves a traditional block layout with directed-loop flow path to minimize material handling costs by using a combined spacefilling curve and simulated annealing algorithm. The second step of the proposed methodology uses the resulting flow sequence and relative positioning information from the first step as input to solve the detailed FMS layout, which includes the spatial coordinates and orientation of each FMS cell. This detailed FMS layout problem is formulated and solved as a mixed integer program. Empirical illustrations show promising results for the proposed methodology in solving real-world type problems.     

制造单元布局问题的双目标模型与算法研究

单元制造系统的布局对于提高系统的效率起着十分重要的作用。以最小化物料周转量和设施面积为目标,建立了一个单元制造系统布局的双目标优化模型,在该模型中不同制造单元的布局、单元内部不同设施的位置与方向这几个问题可以同时进行优化。基于模拟退火邻域解的变尺度生成机制和双目标抽样准则设计了模型的求解算法。算例表明本文算法所得Pareto解集优于经典的NSGA-Ⅱ算法。     

A new approach towards integrated cell formation and inventory lot sizing in an unreliable cellular manufacturing system

This paper presents a comprehensive mathematical model for integrated cell formation and inventory lot sizing problem. The proposed model seeks to minimize cell formation costs as well as the costs associated with production, while dynamic conditions, alternative routings, machine capacity limitation, operations sequences, cell size constraints, process deterioration, and machine breakdowns are also taken into account. The total cost consists of machine procurement, cell reconfiguration, preventive and corrective repairs, material handling (intra-cell and inter-cell), machine operation, part subcontracting, finished and unfinished parts inventory cost, and defective parts replacement costs. With respect to the multiple products, multiple process plans for each product and multiple routing alternatives for each process plan which are assumed in the proposed model, the model is combinatorial. Moreover, unreliability conditions are considered, because moving from “in-control” state to “out-of-control” state (process deterioration) and machine breakdowns make the model more practical and applicable. To conquer the breakdowns, preventive and corrective actions are adopted. Finally, a Particle Swarm Optimization (PSO)-based meta-heuristic is developed to overcome NP-completeness of the proposed model.     

Integrating design and production planning considerations in multi-bay manufacturing facility layout

This paper develops a new mathematical model that integrates layout design and production planning to prescribe efficient multi-bay manufacturing facilities. The model addresses the need to distribute department replicas throughout the facility and extends the use of product and process requirements as problem parameters in order to increase process routing flexibility. In addition, the model allows for the consideration of practical material handling and production features such as alternate process routings, product flow production patterns, and department replica capacities. Computational results demonstrate that the run time required to solve our test problems is quite acceptable given the long-term nature of facility layout decisions. Moreover, comparative results indicate that department replication can reduce material movement significantly while maintaining the existing production capacity.     

Ant Colony Optimisation for Machine Layout Problems

Flexible machine layout problems describe the dynamic arrangement of machines to optimise the trade-off between material handling and rearrangement costs under changing and uncertain production environments. A previous study used integer-programming techniques to solve heuristically reduced versions of the problem. As an alternative, this paper introduces an ant colony optimisation (ACO) algorithm to generate good solutions. Experimental results are presented, with ACO obtaining better solutions than the reduction heuristic.     

A heuristic approach for the double row layout problem

Annals of Operations Research - In the double row layout problem, we wish to position n machines on two parallel rows in order to minimize the cost of material flow among machines. The problem is...     

Solving a multi-objective simulation model using a hybrid response surface method and lexicographical goal programming approach—a case study on integrated circuit ink-marking machines

In an integrated circuit (IC) packaging plant, the ink-marking machine has a significantly higher throughput than the other processing machines. When periodic demand surges result in backlog orders or in lost customers, there is a need to increase system throughput. To resolve this problem, the purchase of a new machine often results in excess capacity in addition to added operation and acquisition costs. Therefore, the productivity improvement effort has priority over the machine purchase decision. This paper seeks to optimize both throughput and cycle time performance for IC ink-marking machines. While throughput increase is the primary objective, there is an acceptable cycle time limit for a feasible solution. It is a multi-objective problem. The proposed solution methodology constructed a simulation metamodel for the ink-marking operation by using a fractional factorial experimental design and regression analysis. It is then solved by a hybrid response surface method and lexicographical goal programming approach. Solution results illustrated a successful application.     

Iterative algorithms for part grouping and loading in cellular reconfigurable manufacturing systems

A reconfigurable manufacturing system (RMS), one of state-of-the-art manufacturing system technologies, is the one designed at the outset for rapid changes in its hardware and software components in order to quickly adjust its production capacity and functionality in response to market or system changes. In this study, we consider a cellular RMS with multiple reconfigurable machining cells (RMCs), each of which has numerical control machines, a setup station, and an automatic material handling and storage system. Each machine within the RMC has an automatic tool changer and a tool magazine of a limited capacity. Two important operational problems, part grouping and loading, are considered in this study. Part grouping is the problem of allocating parts to RMCs, and loading is the problem of allocating operations and their cutting tools to machines within the RMC. An integer programming model is suggested to represent the two problems at the same time for the objective of balancing the workloads assigned to machines. Then, due to the complexity of the problem, we suggest two iterative algorithms in which the two problems are solved repeatedly until a solution is obtained. Computational experiments were done on various test instances and the results are reported.     

A lexicographic approach to bi-objective scheduling of single-period orders in make-to-order manufacturing

This paper presents a lexicographic approach and integer programming formulations for a dual-objective, long-term production scheduling in make-to-order manufacturing environment. The problem objective is to assign single-period customer orders for various product types to planning periods to complete all the orders with minimum number of tardy orders as a primary criterion and to level the aggregate production or the total capacity utilization over a planning horizon as a secondary criterion. Each order must be completed during one planning period. The basic integer programming formulation has been strengthened by the addition of some cutting constraints derived by relating the demand on required capacity to available capacity for each subset of orders with the same due date. The approach has been applied to optimize production schedules in a flexible flowshop made up of several processing stages in series, with identical, parallel machines, and an output buffer of limited capacity for holding completed products before delivery to the customers. Numerical examples modeled after a real-world make-to-order flexible assembly line in the electronics industry are provided and some computational results are reported.     

主通道位置不固定的设施布局问题多目标优化模型及算法

以物流中心设施布局问题为对象,提出了考虑出入口及主通道位置不固定情况下的设施布局问题的多目标优化模型并设计了其改进的遗传算法。首先,以物料搬运成本最小、活动关系密切度最大和面积利用率最大为目标,构建了考虑出入口位置不固定条件下的具有I型主通道的设施布局多目标优化数学模型。然后,设计了一种改进的遗传算法,包括:改进的编码、解码方法,追加了解码修正操作,基于惩罚函数策略的适应度函数等。实例测试表明,本算法的执行效率高而且结果稳定,优化效果好,布局结果紧凑适用。     

Applications of mathematical programming models

A sizeable proportion of manufacturing expenses can be attributed to facility layout and material handling. Facility layout decisions involve designing the arrangement of elements in manufacturing systems. Among the most critical material handling decisions in this area are the arrangement and design of material flow patterns. This survey article reviews loop based facility planning and material handling decisions for trip based material handling equipment with an emphasis on unit load automated guided vehicles. The article examines issues related with facility design, material handling design, and fleet sizing and operating.     

A cross entropy approach to design of reliable networks

One of the most important parameters determining the performance of communication networks is network reliability. The network reliability strongly depends on not only topological layout of the communication networks but also reliability and availability of the communication facilities. The selection of optimal network topology is an NP-hard problem so that computation time of enumeration-based methods grows exponentially with network size. This paper presents a new solution approach based on cross-entropy method, called NCE, to design of communication networks. The design problem is to find a network topology with minimum cost such that all-terminal reliability is not less than a given level of reliability. To investigate the effectiveness of the proposed NCE, comparisons with other heuristic approaches given in the literature for the design problem are carried out in a three-stage experimental study. Computational results show that NCE is an effective heuristic approach to design of reliable networks.     

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 meta-heuristic approach for solving the Urban Network Design Problem

This paper proposes an optimisation model and a meta-heuristic algorithm for solving the urban network design problem. The problem consists in optimising the layout of an urban road network by designing directions of existing roads and signal settings at intersections. A non-linear constrained optimisation model for solving this problem is formulated, adopting a bi-level approach in order to reduce the complexity of solution methods and the computation times. A Scatter Search algorithm based on a random descent method is proposed and tested on a real dimension network. Initial results show that the proposed approach allows local optimal solutions to be obtained in reasonable computation times.     

Multi-plant production planning in capacitated self-configuring two-stage serial systems

This research deals with a capacitated master production planning and capacity allocation problem for a multi-plant manufacturing system with two serial stages in each plant. We consider both cases in which a decoupling buffer is allowed or not between the two stages. Peculiar to the system considered is the capability of dynamically self-configuring its layout when buffering is disallowed, in the sense that, for each production run, different parallel machines in the second stage are grouped together and serially connected to a machine in the first stage. Although setup times and costs are considered negligible in our model, yet binary setup variables are introduced in order to account for minimum lot-sizes. The resulting mixed {0,1} linear programming model is solved by means of LP-based heuristic algorithms. The proposed modeling and solution procedure has been applied to problem instances originating from a real-world application, showing good results in practice.     

Covering and connectivity constraints in loop-based formulation of material flow network design in facility layout

The shortest loop covering at least one edge of each workcenter in a manufacturing facility layout is an instance of the generalized traveling salesman problem. The optimal solution to this problem is a promising design for non-vehicle-based material handling, typical of most types of conveyors and power-and-free systems, where the length of the path is the main driver of the total investment costs. The loop formulation is usually embedded within a larger problem of the concurrent design of the loop and the input/output stations for vehicle-based material handling typical of automatically guided vehicles and autonomous delivery robots. In these systems, it is not the length, but the total flow of the loaded and empty vehicles that drives the objective function. It has been shown that the shortest loop provides an effective heuristic scheme to achieve prosperous and robust solutions for the concurrent design of the loop and input/output stations. We review and compare covering constraints formulations, provide new insight into connectivity constraints, improve the model formulation and its solution procedure, and report computational results.