Sharing clearances to improve machine layout

This paper considers a double-row layout problem with shared clearances in the context of semiconductor manufacturing. By sharing some clearances, reductions in both layout area and material handling cost of approximately 7–10% are achieved. Along with minimal clearances for separating adjacent machines, clearances that can be shared by adjacent machines are considered. The shared clearances may be located on either or both sides of machines. A mixed integer linear programming formulation of this problem is established, with the objective to minimise both material flow cost and layout area. A hybrid approach combining multi-objective tabu search and heuristic rules is proposed to solve it. Computational results show that the hybrid approach is very effective for this problem and finds machine layouts with reduced areas and handling costs by exploiting shared clearances.     

A cross-entropy approach to the single row facility layout problem

The single row facility layout problem is to arrange a given number of facilities along a straight line so as to minimise the total cost associated with the interactions between the facilities. In this paper, a metaheuristic algorithm based on the cross-entropy method, incorporating a local search procedure and symmetry-breaking techniques, is developed to solve this problem. The proposed algorithm has been tested on some widely used benchmark instances. The computational results show that the proposed algorithm has found the optimal or the best solutions known so far for the instances of size with up to 100 facilities and is competitive with some existing algorithms.     

The double row layout problem

This research explores the double row layout problem (DRLP) that deals with how to place departments or machines on both sides of a central corridor. This type of layout problem is commonly observed in production and service facilities. Over the last 40 years, researchers have extensively studied a similar problem called the single row layout problem (SRLP) or one dimensional space allocation problem (ODSAP); as a result, several practical approaches are currently available for the problem. However, the DRLP has not received much attention in the literature although it often provides a better structure for layout designers. In this research, we first develop an MIP model for the DRLP that involves more variables and constraints than existing formulations of the SRLP. In turn, conditions yielding a good solution are analysed based on the proposed model. Five heuristic algorithms are developed to provide a reasonably good initial solution and corresponding upper bound of the DRLP. The performance of these heuristic algorithms, as well as MIP solutions by CPLEX 10.2, is compared in a series of experiments.     

A new approach for loop machine layout problem integrating proximity constraints

This paper focuses on the machine arrangement problem on common loop network in a flexible manufacturing system. Existing studies aim to place machines at pre-fixed positions around a loop network. This problem is considered as a permutation problem that aims to find the best combination to reduce generated costs. In this work, we try to add more complexity to this problem by respecting the proximity constraints, defined by the experts, between the machines. To do this, we propose an algorithm based on direct distance measure. Logically, proximity constraints are checked using direct distances but costs are calculated using travelled distances. Throughout this study, we seek the best machine layout in four transport system configuration types to minimise the sum of flow time distances. Comparing our algorithm results with two hybrid genetic algorithms, the empirical results show that the proposed algorithm provides the most suitable solutions.     

Unequal-area stochastic facility layout problems: solutions using improved covariance matrix adaptation evolution strategy,particle swarm optimisation,and genetic algorithm

Determining the locations of departments or machines in a shop floor is classified as a facility layout problem. This article studies unequal-area stochastic facility layout problems where the shapes of departments are fixed during the iteration of an algorithm and the product demands are stochastic with a known variance and expected value. These problems are non-deterministic polynomial-time hard and very complex, thus meta-heuristic algorithms and evolution strategies are needed to solve them. In this paper, an improved covariance matrix adaptation evolution strategy (CMA ES) was developed and its results were compared with those of two improved meta-heuristic algorithms (i.e. improved particle swarm optimisation [PSO] and genetic algorithm [GA]). In the three proposed algorithms, the swapping method and two local search techniques which altered the positions of departments were used to avoid local optima and to improve the quality of solutions for the problems. A real case and two problem instances were introduced to test the proposed algorithms. The results showed that the proposed CMA ES has found better layouts in contrast to the proposed PSO and GA.     

Linear Programming Based Genetic Algorithm for the Unequal Area Facility Layout Problem

The facility layout problem (FLP) is generally defined as locating a set of departments in a facility with a given dimension. In this paper, a hybrid genetic algorithm (GA)/linear programming (LP) approach is proposed to solve the FLP on the continuous plane with unequal area departments. This version of the FLP is very difficult to solve optimally due to the large number of binary decision variables in mixed integer programming (MIP) models as well as the lack of tight lower bounds. In this paper, a new encoding scheme, called the location/shape representation, is developed to represent layouts in a GA. This encoding scheme represents relative department positions in the facility based on the centroids and orientations of departments. Once relative department positions are set by the GA, actual department locations and shapes are determined by solving an LP problem. Finally, the output of the LP solution is incorporated into the encoding scheme of the GA. Numerical results are provided for test problems with varying sizes and department shape constraints. The proposed approach is able to either improve on or find the previously best known solutions of several test problems.     

An efficient local search heuristic for the double row layout problem with asymmetric material flow

The double row layout problem (DRLP) consists of arranging a number of rectangular machines of varying widths on either side of a corridor to minimize the total cost of material handling for products that move between these machines. This problem arises in the context of many production environments, most notably semiconductor manufacturing. Because the DRLP contains both combinatorial and continuous aspects, traditional solution approaches are not well suited to obtain solutions within a reasonable time. Moreover, previous approaches to this problem did not consider asymmetric flows. In this paper, an effective local search procedure featuring linear programming is proposed for solving the DRLP with asymmetric flows (symmetric flows being a special case). This approach is compared against several constructive heuristics and solutions obtained by a commercial mixed integer linear programming solver to evaluate its performance. Computational results show that the proposed heuristic is an effective approach, both in terms of solution quality and computational effort.     

A simulated annealing procedure for single row layout problems in flexible manufacturing systems

In this paper we address a layout problem in flexible manufacturing systems (FMSs). A layout type that has been extensively implemented in FMSs is the single row machine layout. In such a configuration machines are arranged along a straight track with a material handling device moving jobs from one machine to another. The single row layout problem (SRLP) deals with the optimal arrangement of the machines for the above configuration. We propose a simulated annealing (SA) heuristic for the solution of SRLP. Extensive computational results, and ways to improve the performance of the SA algorithm through parameter fine-tuning procedures, are reported.     

A methodology for solving the unequal area facility layout problem using distance and shape-based measures

This paper presents a methodology for solving the unequal area facility layout problem commonly encountered in industry practice. A mixed-binary nonlinear-programming model is formulated to capture the operational issues encountered on the shop floor. In particular, in addition to the distance measure that is typically used to quantify the material handling costs, the impact of geometry or the shape of the departments is quantified in the formulation of the model. A higher-level heuristic solution algorithm, based on a concept known as ‘tabu search’, is proposed to efficiently solve industry-relevant problems. The methodology not only considers the impact of both distance and shape-based measures simultaneously in the proposed initial solution finding mechanism, but also in the evaluation of the objective function during the entire search procedure, in the hope that it will lead to identifying a better final solution. Taking into consideration fixed and variable tabu list sizes, along with long-term memory with maximum and minimum frequencies, has led to developing six different heuristics for the solution algorithm. A single factor experiment based on randomized block design has been used to compare the performances of the six different heuristics on three different problem structures—small, medium, and large—using the total cost as the criterion. Based on this experiment, the characterizations of search procedures have been recommended to facilitate identifying the best solution for each problem structure. The proposed method is also compared with those in the published literature by solving fairly well known unequal area facility layout problems. When an improvement is observed, the comparison has led to identifying a percentage improvement in total cost of approximately 2.8% to 11.8%, thus demonstrating the effectiveness of the model and the algorithm.     

二维不规则件优化排样的小生境遗传算法

首先采用组合矩形包络算法将二维不规则零件的排样问题转化为矩形件的排样问题;然后将遗传算法与小生境技术相结合,寻找排样件在排样时的最优次序及各自的旋转角度;最后用“最低水平线与填充算法相结合”策略的启发式排样算法实现自动排样。实例表明,该算法是有效的。     

Environment conscious manufacturing edited by S.M. Gupta and A.J.D. Lambert

The dynamic facility layout problem (DFLP) aims to minimise the sum of handling and re-layout costs by devising an individual layout for each distinctive production period. In this paper, a hybrid particle swarm optimisation (HPSO) algorithm is proposed to find near-optimal solutions of DFLP. We use a coding and decoding technique that permits a one to one mapping of a solution in discrete space of DFLP to a PSO particle position in continuous space. The proposed PSO will further use this coding technique to explore the continuous solution space. For further enhancement, the proposed PSO is hybridised with a simple and fast simulated annealing. The developed algorithm is capable of being extended to more general cases although equal area machines and standardised handling equipments with identical unit costs are assumed for the time being. Computational results show the efficiency of the proposed algorithm compared to other heuristics.     

A new relaxed flexible bay structure representation and particle swarm optimization for the unequal area facility layout problem

The facility layout problem (FLP) with unequal area departments is a very hard problem to be optimally solved. In this article, a hybrid particle swarm optimization (PSO) and local search approach is proposed to solve the FLP with unequal area departments. The flexible bay structure (FBS), which is a very common layout in manufacturing and retail facilities, is used. Furthermore, the FBS is relaxed by allowing empty spaces in bays, which results in more flexibility while assigning departments in bays. The proposed PSO approach is used to solve the FLP instances from the literature with varying sizes. The comparative results show that the PSO approach is very promising and able to find the previously known-optimal solutions in very short CPU times. In addition, new best solutions have been found for some test problems. Improvements have been achieved by allowing partially filled bays.     

产品操作界面元素布局多目标优化设计

目的针对产品设计中操作界面布局设计时存在的随意性、不确定性大等问题,使用多目标优化设计的方法,寻找界面元素的最优布置,以提升界面的使用舒适性和人机交互效率。方法在分析了工效学准则和界面布局美度评价准则的基础上,确立了层次性、相关性、简洁性和舒适性四个界面布局基本原则,并依据原则构建了界面元素布局多目标优化数学模型,在此模型的基础上采用改进的遗传算法,建立基于遗传算法的界面元素布局多目标优化方法。结果给出产品操作界面布局设计的基本原则,提出一种基于遗传算法的产品操作界面元素布局的多目标优化方法及流程。结论提出的布局原则和优化方法能较好地协助设计师获得满足设计需求的布局方案,实例结果表明了理论模型的合理性与遗传算法对于界面元素布局多目标优化问题求解的有效性。     

A genetic algorithm for solving the economic lot scheduling problem in flow shops

In this study, we propose a hybrid genetic algorithm (HGA) to solve the economic lot scheduling problem in flow shops. The proposed HGA utilizes a so-called Proc PLM heuristic that tests feasibility for the candidate solutions obtained in the evolutionary process of genetic algorithm. When a candidate solution is infeasible, we propose to use a binary search heuristic to ‘fix’ the candidate solution so as to obtain a feasible solution with the minimal objective value. To evaluate the performance of the proposed HGA, we randomly generate a total of 2100 instances from seven levels of utilization rate ranged from 0.45 to 0.80. We solve each of those 2100 instances by the proposed HGA and the other solution approaches in the literature. Our experiments show that the proposed HGA outperforms traditional methods for solving the economic lot scheduling problem in flow shops.     

基于遗传算法的连续型设备布置优化

针对企业在生产过程中遇到的连续型设备布置问题,分析设备面积不等、形状固定及总空间限制等因素,提出分行布置的方案和数学模型来最小化物料搬运成本,用遗传算法对方案进行设计,并进行实证研究.     

A Monte Carlo simulation based heuristic procedure for solving dynamic line layout problems for facilities using conventional material handling devices

A simple procedure is proposed to identify line layout solutions when a production facility with work centres of unequal size uses conventional material handling devices and operates under stochastic demand scenarios. The procedure uses Monte Carlo simulation (MCS) to empirically search for robust solutions defined as those that simultaneously meet minimum material handling cost performance levels across all demand scenarios. The results reported in this study suggest that ‘robust’ line layout solutions can be identified using a modest volume of random sampling. The procedure and results are demonstrated through a series of sample problems.     

基于AutoCAD和MATLAB的排样优化与程序实现

在顶点算法基础上,提出了改进型中心旋转顶点算法.建立了普通单排、对头单排和对头双排的数学模型,提供了实现流程,即通过AutoCAD的DXF接口文件,利用MATLAB语言实现排样优化计算和相关图形处理,最后给出了冲裁件排样的优化实例.     

A genetic algorithm and queuing theory based methodology for facilities layout problem

Facilities layout, being a significant contributor to manufacturing performance, has been studied many times over the past few decades. Existing studies are mainly based on material handling cost and have neglected several critical variations inherent in a manufacturing system. The static nature of available models has reduced the quality of the estimates of performance and led to not achieving an optimal layout. Using a queuing network model, an established tool to quantify the variations of a system and operational performance factors including work-in-process (WIP) and utilisation, can significantly help decision makers in solving a facilities layout problem. The queuing model utilised in this paper is our extension to the existing models through incorporating concurrently several operational features: availability of raw material, alternate routing of parts, effectiveness of a maintenance facility, quality of products, availability of processing tools and material handling equipment. On the other hand, a queuing model is not an optimisation tool in itself. A genetic algorithm, an effective search process for exploring a large search space, has been selected and implemented to solve the layout problem modelled with queuing theory. This combination provides a unique opportunity to consider the stochastic variations while achieving a good layout. A layout problem with unequal area facilities is considered in this paper. A good layout solution is the one which minimises the following four parameters: WIP cost, material handling cost, deviation cost, and relocation cost. Observations from experimental analysis are also reported in this paper. Our proposed methodology demonstrates that it has a potential to integrate several related decision-making problems in a unified framework.     

Designing group layout of unequal-area facilities in a dynamic cellular manufacturing system with variability in number and shape of cells

This paper presents a new mixed-integer non-linear programming model for designing the group layout (GL) of unequal-area facilities in a cellular manufacturing system (CMS) under a dynamic environment. There are some features that make the presented model different from the previous studies. These include: (1) manufacturing cells with variable numbers and shapes, (2) machine depot keeping idle machines, (3) machines of unequal-areas, (4) manufacturing cells with rectangle regular shapes established on the continuous shop floor and (5) integration of cell formation and GL as interrelated decisions involved in the design of a CMS in a dynamic environment. The objective function is to minimises the total costs of intra- and inter-cell material handling, machine overhead, machine relocation, machine processing, purchasing machines and forming cells. Since the problem is NP-hard, an efficient simulated annealing (SA) algorithm is developed to solve the presented model. The performance of this model is illustrated by two numerical examples. It is then tested using several test problems with different sizes and settings to verify the computational efficiency of the developed algorithm in comparison to the classical genetic algorithm (GA). The obtained results show that the quality of the solutions obtained by SA is better than GA.     

Solution of facility layout problems with pickup/drop-off locations using random search techniques

Due to non-polynomial hardness, the facility layout problem (FLP) becomes more critical when pickup/drop-off (P/D) locations are considered in the design of an open field layout under a manufacturing environment. This paper proposes an indigenous model of the facility layout problem based on random search techniques and its solution methodology using a genetic algorithm (GA), simulated annealing (SA) and a hybrid algorithm (HA). The paper illustrates the performance of different random search operating parameters in solving the facility layout problem considering P/D locations along the periphery of rectangular machine blocks. The preliminary experiments were carried out on three facility layout test problems having six, eight and ten machines in order to fix the different operating parameters such as crossover operator, crossover rate, initial temperature, temperature reduction factor, number of generations, population size, etc. The results of extensive preliminary experimentation were utilized to solve facility layout problems having 12 and 18 machines and, finally, were compared with the existing procedures in the literature. The experimental tables and related analysis performed via the solution methods by applying GA, SA and HA revealed that random-search-based modeling of FLP considering P/D and its solution as suggested in this paper is worth pursuing.