Solving an extended multi-row facility layout problem with fuzzy clearances using GA

Multi-row facility layout problem (MRFLP) is a class of facility layout problems, which decides upon the arrangement of facilities in some fixed numbers of rows in order to minimize material handling cost. Nowadays, according to the new layout requirements, the facility layout problems (FLPs) have many applications such as hospital layout, construction site layout planning and layout of logistics facilities. Therefore, we study an extended MRFLP, as a novel layout problem, with the following main assumptions: 1) the facilities are arranged in a two-dimensional area and without splitter rows, 2) multiple products are available, 3) distance between each pair of facilities, due to inaccurate and flexible manufacturing processes and other limitations (such as WIPs, industrial instruments, transportation lines and etc.), is considered as fuzzy number, and 4) the objective function is considered as minimizing the material handling and lost opportunity costs. To model these assumptions, a nonlinear mixed-integer programming model with fuzzy constraints is presented and then converted to a linear mixed-integer programming model. Since the developed model is an NP-hard problem, a genetic algorithm approach is suggested to find the best solutions with a minimum cost function. Additionally, three different crossover methods are compared in the proposed genetic algorithm and finally, a sensitivity analysis is performed to discuss important parameters.     

Knowledge based approach to machine cell layout

In this paper, the machine cell layout problem is examined. A new methodology for solving the problem is proposed. The methodology involves three stages. In the first stage, an algorithm suitable for solving the machine grouping problem is utilized. In the second and third stages, mathematical programming models of the machine cell and machine layout problems are formulated and solved using suitable algorithms. The development of a knowledge based system which uses models and algorithms for solving the machine grouping and layout problems, is also outlined.     

Solving dynamic double row layout problem via combining simulated annealing and mathematical programming

Double row layout problem (DRLP) is to allocate facilities on two rows separated by a straight aisle. Aiming at the dynamic environment of product processing in practice, we propose a dynamic double-row layout problem (DDRLP) where material flows change over time in different processing periods. A mixed-integer programming model is established for this problem. A methodology combining an improved simulated annealing (ISA) with mathematical programming (MP) is proposed to resolve it. Firstly, a mixed coding scheme is designed to represent both of sequence of facilities and their exact locations. Secondly, an improved simulated annealing algorithm is suggested to produce a solution to DDRLP. Finally, MP is used to improve this solution by determining the optimal exact location for each facility. Experiments show that this methodology is able to obtain the optimal solutions for small size problems and outperforms an exact approach (CPLEX) for problems of realistic size.     

基于Wang-Landau算法的动态设施布局方法

动态设施布局问题是设施在车间内多个阶段的布局规划问题。目前,针对动态设施布局问题,国内外学者对离散模型研究较多,而对连续模型的研究却较少。根据连续动态设施布局的特性与需求,构建了不等面积设施的动态设施布局连续模型。求解该模型的难点在于缺乏一种高效的布局优化方法。Wang-Landau算法是一种改进的蒙特卡罗算法。通过将Wang-Landau算法与空位点放置策略、外推移动策略、内压移动策略三种启发式策略相结合,提出一种基于Wang-Landau抽样的启发式算法,并以此求解该模型。使用文献中已有的测试算例对提出的算法进行测试,计算结果表明,所提出的算法在求解连续动态设施布局问题上是有效的。     

Dynamic programming interpretation of construction-type plant layout algorithms and some results

This paper presents a dynamic programming interpretation of some existing construction-type algorithms for the CAD of plant layouts. The two sub-problems of constructing a layout by these algorithms are first, the selection of a department for next placement, and second, locating it in the available space in an optimum manner. The first problem is tackled by adopting a heuristic. Successive choices of this nature lend themselves to a dynamic programming interpretation. The second problem is solved by allocating those blocks of area in the vicinity of existing departments which minimize the cost of materials handling between the new and the existing departments. It is found that application of dynamic programming significantly improves the efficiency of existing construction-type procedures. Some new heuristics for the first sub-problem are also examined. Computational results on test problems indicate that more complex policies might yield better results when the number of departments becomes larger.     

A Stronger Model of Dynamic Programming Algorithms

We define a formal model of dynamic programming algorithms which we call Prioritized Branching Programs (pBP). Our model is a generalization of the BT model of Alekhnovich et al. (IEEE Conference on Computational Complexity, pp. 308–322, 2005), which is in turn a generalization of the priority algorithms model of Borodin, Nielson and Rackoff. One of the distinguishing features of these models is that they not only capture large classes of algorithms generally considered to be greedy, backtracking or dynamic programming algorithms, but they also allow characterizations of their limitations. Hence they give meaning to the statement that a given problem can or cannot be solved by dynamic programming. After defining the model, we prove three main results: (i) that certain types of natural restrictions of our seemingly more powerful model can be simulated by the BT model; (ii) that in general our model is stronger than the BT model—a fact which is witnessed by the classical shortest paths problem; (iii) that our model has very real limitations, namely that bipartite matching cannot be efficiently computed in it, hence suggesting that there are problems that can be solved efficiently by network flow algorithms and by simple linear programming that cannot be solved by natural dynamic programming approaches.     

Fuzzy random programming models for location-allocation problem with applications

Three types of fuzzy random programming models based on the mean chance for the capacitated location-allocation problem with fuzzy random demands are proposed according to different criteria, including the expected cost minimization model, the α-cost minimization model, and the chance maximization model. In order to solve the proposed models, some hybrid intelligent algorithms are designed by integrating the network simplex algorithm, fuzzy random simulation, and genetic algorithm. Finally, some numerical examples about a container freight station problem are given to illustrate the effectiveness of the devised algorithms.     

A simulated annealing algorithm for dynamic layout problem

Increased level of volatility in today's manufacturing world demanded new approaches for modelling and solving many of its well-known problems like the facility layout problem. Over a decade ago Rosenblatt published a key paper on modelling and solving dynamic version of the facility layout problems. Since then, various other researchers proposed new and improved models and algorithms to solve the problem. Balakrishnan and Cheng have recently published a comprehensive review of the literature about this subject. The problem was defined as a complex combinatorial optimisation problem. The efficiency of SA in solving combinatorial optimisation problems is very well known. However, it has recently not been applied to DLP based on the review of the available literature. In this research paper a SA-based procedure for DLP is developed and results for test problems are reported.

Scope and purpose

One of the characteristic of today's manufacturing environments is volatility. Under a volatile environment (or dynamic manufacturing environment) demand is not stable. To operate efficiently under such environments facilities must be adaptive to changing demand conditions. This requires solution of the dynamic layout problem (DLP). DLP is a complex combinatorial optimisation problem for which optimal solutions can be found for small size problems. This research paper makes use of a SA algorithm to solve the DLP. Simulated annealing (SA) is a well-established stochastic neighbourhood search technique. It has a potential to solve complex combinatorial optimisation problems. The paper presents in detail how to apply SA to solve DLP and an extensive computational study. The computational study shows that SA is quite effective in solving dynamic layout problems.     

Solving fuzzy assembly-line balancing problem with genetic algorithms

Assembly-line balancing problem is known as one of difficult combinatorial optimization problems. This problem has been solved with linear programming, dynamic programming approaches, but unfortunately these approaches do not lead to efficient algorithms. Recently, genetic algorithm has been recognized as an efficient and usefull procedure for solving large and hard combinatorial optimization problems, such as scheduling problems, travelling salesman problems, transportation problems, and so on. Fuzzy sets theory is frequently used to represent uncertainty of information. In this paper, to treat the data of real-world problems we use a fuzzy number to represent the processing time and show that we can get a good performance in solving this problem using genetic algorithms.     

Tools of soft computing as applied to the problem of facilitieslayout planning

The layout of temporary facilities in a construction site deals with the selection of their most efficient layout in order to operate efficiently and cost effectively. The layout design seeks the best arrangement of facilities within the available area. In the design process of the layout, many objectives must be considered to effectively utilize people resources, equipment, space, and energy. This study proposes a soft-computing-based approach to improve the layout process of facilities. The main objective is on obtaining the closeness relationship values between each pair of facilities in a construction site. To achieve this, an integrated approach, using fuzzy set theory and genetic algorithms, is used to investigate the layout of temporary facilities in relation with the planned building(s) in a construction site. An example application is presented to illustrate the proposed approach and the results are then discussed along with recommendations for further work. Depending on the importance of relationships among the various facilities in the construction site, this study is expected to provide engineers with an appropriate tool to compare and evaluate different layouts and select the most appropriate and efficient one     

An artificial intelligence approach for fuzzy possibilistic-stochastic multi-objective logistics network design

In this paper, a logistics network is investigated which includes multi-suppliers, collection centers, transfer stations, treatment stations, and products. For this purpose, a multi-objective mathematical programming model is proposed that minimizes the total costs including the fixed costs for opening facilities and transportation costs between facilities, minimizes the distance between each waste-generating facilities and transfer stations, maximizing the distance between treatment and disposal stations and customer zones, and maximizes the sum of the reliability of coverage for the potential facilities which will be open. In order to make the results of this paper more realistic, a case study in the iron and steel industry has been investigated. Besides, a new solution approach is proposed by combining fuzzy possibilistic programming, stochastic programming, and fuzzy multi-objective programming. Moreover, an imperialist competitive algorithm is proposed to obtain near optimal solution in comparison with other evolutionary algorithms. Finally, computational experiments are provided to demonstrate the applicability and suitability of the proposed model and solution approaches.     

A hybrid fuzzy-GA algorithm for the integrated machine allocation problem with fuzzy demands

The integrated machine allocation and facility layout problem (IMALP) is a branch of the general facility layout problem in which, besides selecting machine locations, the processing route of each product is determined. Most research in this area suppose that the flow of material is certain and exact, which is an unrealistic assumption in today's dynamic and uncertain business environment. Therefore, in this paper the demand volume has been assumed as fuzzy numbers with different membership functions. To solve this problem, the deterministic model is first integrated with a fuzzy implication via the expected value model, and thereafter an intelligent hybrid algorithm, including a genetic algorithm and a fuzzy simulation approach has been applied. Finally, the efficiency of the proposed algorithm is evaluated with a set of numerical examples. The results show the effectiveness of the hybrid algorithm in finding the IMALP solutions.     

Hybrid imperialist competitive algorithm,variable neighborhood search,and simulated annealing for dynamic facility layout problem

Today’s manufacturing plants tend to be more flexible due to rapid changes in product mix and market demand. Therefore, this paper investigates the problem of location and relocation (when there are changes incurred to the material flows between departments) manufacturing facilities such that the total cost of material flows and relocation costs are minimized. This problem is known as the dynamic facility layout problem (DFLP), which is a general case of static facility layout problem. This paper proposes a robust and simply structured hybrid technique based on integrating three meta-heuristics: imperialist competitive algorithms, variable neighborhood search, and simulated annealing, to efficiently solve the DFLP. The novel aspect of the proposed algorithm is taking advantage of features of all above three algorithms together. To test the efficiency of our algorithm, a data set from the literature is used for the experimental purpose. The results obtained are quite promising in terms of solution quality for most of the test problems.     

基于最优子段的矩形优化排样

为有效解决企业实际生产中的矩形优化排样问题,对矩形优化排样算法进行研究, 给出基于最优子段的矩形优化排样算法,有效解决了企业实际生产中的长板矩形优化排样问题。 首先基于动态规划算法求出所有小于剪床刀刃长度的最优子段的最佳排样方式,然后以所求的最 优子段作为可用子段在长板上进行优化排样,并将矩形优化排样问题转化为完全背包问题。最后 基于分支定界技术的整数规划算法对其进行求解。企业应用实例表明该算法在解决长板矩形优化 问题方面优于其他算法。     

考虑搬运车辆空载的多行设备布局设计

对于多行设备布局问题,通过对搬运车辆运行情况的分析,建立的模型中以搬运设备的重载运行和空载运行的费用之和最小作为目标函数,设计了相应的遗传算法来求解。通过一个实例进行了模拟计算,进一步与原有模型的仿真结果进行了比较。比较结果说明了利用该模型得到的设备布置方案要优于采用原有模型得到的布置方案。     

Approach to decision making in fuzzy environment

A general approach to solving a wide class of optimization problems with fuzzy coefficients in objective functions and constraints is described. It is based on a modification of traditional mathematical programming methods and consists in formulating and solving one and the same problem within the framework of interrelated models with constructing equivalent analogs with fuzzy coefficients in objective function alone. This approach allows one to maximally cut off dominated alternatives from below as well as from above. The subsequent contraction of the decision uncertainty region is associated with reduction of the problem to multicriteria decision making in a fuzzy environment. The approach is applied within the context of fuzzy discrete optimization models, that is based on a modification of discrete optimization algorithms. The results of the paper are of a universal character and are already being used to solve problems of the design and control of power systems and subsystems.     

A class of multi-objective supply chain networks optimal model under random fuzzy environment and its application to the industry of Chinese liquor

An important issue, when shipping cost and customers demand are random fuzzy variables in supply chain network (SCN) design problem, is to find the network strategy that can simultaneously achieve the objectives of minimization total cost comprised of fixed costs of plants and distribution centers (DCs), inbound and outbound distribution costs, and maximization customer services that can be rendered to customers in terms of acceptable delivery time. In this paper, we propose a random fuzzy multi-objective mixed-integer non-linear programming model for the SCN design problem of Luzhou Co., Ltd. which is representative in the industry of Chinese liquor. By the expected value operator and chance constraint operator, the model has been transformed into a deterministic multi-objective mixed-integer non-linear programming model. Then, we use spanning tree-based genetic algorithms (st-GA) by the Prüfer number representation to find the SCN to satisfy the demand imposed by customers with minimum total cost and maximum customer services for multi-objective SCN design problem of this company under condition of random fuzzy customers demand and transportation cost between facilities. Furthermore, the efficacy and the efficiency of this method are demonstrated by the comparison between its numerical experiment results and those of tradition matrix-based genetic algorithm.     

Multicriteria distribution network planning using simulated annealing

The classical long-range distribution network planning problem involves deciding network investments to meet future demand at a minimum cost while meeting technical restrictions (thermal limits and maximum voltage drop). The decision whether to construct facilities and branches leads to a mixed integer programming problem with a large number of decision variables. The great deal of uncertainty associated with data that cannot be modeled using probabilistic methods leads to the use of fuzzy models to capture the uncertainty. In addition, several criteria must be taken into account that is resulting in the problem being fuzzy multiobjective. The combinatorial nature of the problem limits the use of traditional mathematical tools to limited size problems. This contribution presents a methodology that generates a sample of efficient solutions for the fuzzy multiobjective problem, based on a meta-heuristic, simulated annealing (SA). The results obtained with this approach are shown to be satisfactory compared to other methods under similar conditions.     

An exact and a simulated annealing algorithm for simultaneously determining flow path and the location of P/D stations in bidirectional path

In this paper, we present two algorithms to design flow path and the location of its pickup and delivery (P/D) stations simultaneously in a block layout for Automated Guided Vehicles (AGVs). We develop two algorithms to solve this problem. The first one is a cutting-plane algorithm to solve the mixed integer linear program that models the problem. The second one is a Simulated Annealing (SA) approach which solves the problem heuristically to a near best solution. Computational results show the performance of both algorithms.     

生成最优同形块两阶段布局方式的确定型算法

为解决大规模二维布局问题,提出一种生成同形块两阶段布局方式的确定型算法。首先通过动态规划确定最优同形块;然后求解背包问题确定同形块在同形级中的布局方式和同形级在同形段中的最优布局方式;最后选择两个同形段生成最优同形块布局方式。通过43道基准测题,将该算法与经典两阶段和三块算法进行比较。实验结果表明,该算法不仅能满足剪切工艺,在计算时间和板材利用率上优于以上算法,而且能在合理时间内取得好的优化结果。