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.     

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.     

Simulated annealing based parallel genetic algorithm for facility layout problem

The facility layout problem (FLP), a typical combinational optimisation problem, is addressed in this paper by implementing parallel simulated annealing (SA) and genetic algorithms (GAs) based on a coarse-grained model to derive solutions for solving the static FLP with rectangle shape areas. Based on the consideration of minimising the material flow factor cost (MFFC), shape ratio factor (SRF) and area utilisation factor (AUF), a total layout cost (TLC) function is derived by conducting a weighted summation of MFFC, SRF and AUF. The evolution operations (including crossover, mutation, and selection) of GA provide a population-based global search in the space of possible solutions, and the SA algorithm can lead to an efficient local search near the optimal solution. By combing the characteristics of GA and SA, better solutions will be obtained. Moreover, the parallel implementation of simulated annealing based genetic algorithm (SAGA) enables a quick search for the optimal solution. The proposed method is tested by performing a case study simulation and the results confirm its feasibility and superiority to other approaches for solving FLP.     

An integrated approach for the concurrent determination of the block layout and the input and output point locations based on the contour distance

This paper presents an integrated approach for the facilities design problem. It develops a method for the concurrent determination of the block layout, the locations of departmental input and output (I/O) points using the contour distances between the I/O points, and the material flow paths between the I/O points. The topology of block layouts is represented using two linear sequences (sequence-pair), which allows the layout to have either a slicing or a non-slicing structure. The block layout is obtained from the sequence-pair with a linear programming formulation. Three heuristic methods are then presented to determine for a given block layout the locations of the I/O points on the perimeters of the departments. The flow paths from output to input points are found by determining the shortest paths that follow the perimeters of the departments. The linear programming algorithm, the shortest path algorithm, and the I/O point location heuristics are embedded into a simulated annealing algorithm that modifies the sequence-pair to obtain a high-quality layout based on the contour distances between the I/O points. Results of computational experiments show that the performance of this integrated algorithm compares favourably with those of algorithms using a sequential approach and is capable of solving industrial-sized problems in acceptable computation time.     

A multi-objective particle swarm optimisation algorithm for unequal sized dynamic facility layout problem with pickup/drop-off locations

This paper deals with a multi-objective unequal sized dynamic facility layout problem (DFLP) with pickup/drop-off locations. First, a mathematical model to obtain optimal solutions for small size instances of the problem is developed. Then, a multi-objective particle swarm optimisation (MOPSO) algorithm is implemented to find near optimal solutions. Two new heuristics to prevent overlapping of the departments and to reduce ‘unused gaps’ between the departments are introduced. The performance of the MOPSO is examined using some sets of available test problems in the literature and various random test problems in small, medium, and large sizes. The percentage of improvements on the initial solutions is calculated for small, medium and large size instances. Also, the generation metric and the space metric for non-dominated solutions are examined. These experiments show the good performance of the developed MOPSO and sensitivity analysis show the robustness of the obtained solutions.     

Mitigation of risk in facility layout design for single and multi-period problems

The most desirable characteristic of a facility layout is its ability to maintain its efficiency over time while coping with the uncertainty in product demand. In the traditional facility layout design method, the facility layout is governed by the flow intensity between departments, which is the product flow quantity between departments. Hence, an error in the product demand assessment can render the layout inefficient with respect to material handling costs. Most of the research integrates uncertainty in the form of probability of occurrence of different from-to charts. In an environment where the variability of each product demand is independent, the derivation of ‘probabilistic from-to chart’ based scenario cannot be used to address uncertainty of individual demands. This paper presents an FLP (facility layout problem) approach to deal with the uncertainty of each product demand in the design of a facility layout. Two procedures are presented: the first procedure is utilised to assess the risk associated with the layout, while the second procedure is used to develop the layout that minimises the risk. Results from case studies have shown that the procedure produces a reduction of risk as high as 68%.     

A fuzzy linear programming approach for municipal solid-waste management under uncertainty

In this study, a fuzzy linear programming (FLP) method is developed for dealing with uncertainties expressed as fuzzy sets that exist in the constraints’ left-hand and right-hand sides and the objective function. A direct transforming algorithm is advanced for solving the FLP model that improves upon the existing method through provision of a quantitative expression for uncertain relationships among a large number of fuzzy sets. The proposed solution method can greatly reduce computational requirements, which is particularly meaningful for the application of FLP to large-scale practical problems with many fuzzy sets. The developed FLP method is applied to a case of long-term waste-management planning. The results indicate that reasonable solutions have been obtained. They can be used for generating decision alternatives and to help managers identify desired policies for waste management under uncertainty. Compared with the conventional interval-parameter linear programming approach, FLP can provide more information for solutions, containing not only the lower and upper bounds but also the most possible value for decision variables and objective function.     

An iterative facility layout algorithm

In this paper we present a facility layout algorithm that iterates between a genetic algorithm with a slicing tree representation and a mixed-integer program with a subset of the binary variables set via the genetic algorithm. The genetic algorithm is very good at finding low-cost solutions while maintaining shape constraints on the departments. The slicing tree representation and the mixed-integer program are compatible in terms of layout representation, with the mixed-integer program representation more general. The mixed-integer program allows us to relax the last remaining constraints of the slicing tree representation of the genetic algorithm. We present our genetic algorithm and the iterative algorithm, while illustrating their performance on test problems from the literature. In 10 of the 12 problems, new lower best-cost solutions are found.     

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.     

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 hybrid genetic algorithm for the single row layout problem

The arrangement of machines or departments along a straight line is known as single row layout and it is a widely employed configuration in flexible manufacturing systems. In this paper, a hybrid genetic algorithm (HGA) is proposed to solve the single row layout design problem with unequal sized machines and unequal clearances. The algorithm is developed by hybridisation of a genetic algorithm with a local search operator. The proposed HGA is tested on 51 well known data sets from the literature with equal and unequal clearances, and the results are compared with the best known solutions. Finally, algorithm's effectiveness in reaching previously known best solutions is revealed and improvements up to 7% in problems with unequal clearance are obtained.     

Two-level modified simulated annealing based approach for solving facility layout problem

In this paper, we are considering the quadratic assignment model (QAP) of the facility layout problem (FLP) which is known to be NP-hard. We relax the integer constraints of the QAP and solve it on a commercially available package called LINGO 8. In the optimal solution so obtained, X_ij s take real values between zero and one. We identify promising X_ij s having a value strictly greater than 0.5 in the optimal solution and set them to one. We add the constraints (X_ij ?=?1) associated with promising X_ij s into the QAP (with integer restrictions) and resolve using LINGO 8. In all the cases attempted we obtained a superior feasible solution to the QAP which was further improved by the proposed modified simulated annealing (MSA) procedure. An encouraging comparative performance of this procedure is thus reported.     

Unequal-area,fixed-shape facility layout problems using the firefly algorithm

In manufacturing industries, the facility layout design is a very important task, as it is concerned with the overall manufacturing cost and profit of the industry. The facility layout problem (FLP) is solved by arranging the departments or facilities of known dimensions on the available floor space. The objective of this article is to implement the firefly algorithm (FA) for solving unequal-area, fixed-shape FLPs and optimizing the costs of total material handling and transportation between the facilities. The FA is a nature-inspired algorithm and can be used for combinatorial optimization problems. Benchmark problems from the previous literature are solved using the FA. To check its effectiveness, it is implemented to solve large-sized FLPs. Computational results obtained using the FA show that the algorithm is less time consuming and the total layout costs for FLPs are better than the best results achieved so far.     

Industrial robot layout based on operation sequence optimisation

The robot layout is one of the primary problems in the robot work cell design. An optimal layout not only makes the robotic end-effector reach the desired position with the desired orientation, but also minimises the robot cycle time for completing a given task with collision avoidance. There may be many feasible robot operation sequences for a given task. The optimisation of operation sequence for a robot placed in a fixed location is NP-complete. There may be different optimal operation sequences as the robot is placed in the different locations. Hence the problem of robot layout is quite complex. This paper presents a method of industrial robot layout based on operation sequence optimisation. The robot motion control model with velocity, acceleration and jerk is established. The feasible space of robot base is calculated and then divided into discrete grids before the optimisations. Then the ant colony algorithm is applied to optimise the operation sequence for each grid. The adjacent grids are merged or divided enough times to form the bigger grids. The pattern search algorithm is adopted to solve the local optimal position and orientation of the robot base in each big grid, and the global optimal layout is found through the comparison of the local solutions. The industrial robot layout method has been applied to the work cell design for car door welding.     

Integrated low-carbon distribution system for the demand side of a product distribution supply chain: a DoE-guided MOPSO optimiser-based solution approach

This article contributes to distribution system literature on three inter-linked aspects viz. formulation of a novel integrated low-carbon/green distribution system for the demand side of a Supply Chain (SC) with a single product and multiple consumers, i.e. drop-off points, a novel and robust solution approach through a Design of Experiment (DoE)-guided Multiple-Objective Particle Swarm Optimisation (MOPSO) optimiser and exhaustive analysis of the solutions (i.e. prioritisation, ranking and scenario analysis). The total costs, CO₂ emission and the traversed distances of the vehicles during transportation are optimised. The optimisation model for the strategic decision-making is formulated by effectively integrating the 0–1 mixed-integer programming with a green constraint based on Analytic Hierarchy Process. Due to the computationally NP-hard characteristic of the model, a systematic and technically robust DoE-guided solution approach is designed using a commercial solver – modeFRONTIER^®. DoE guides the solution through the MOPSO optimiser in order to eliminate the un-realistic set of feasible and optimal solution sets. A popular multi-attribute decision-making approach, TOPSIS, evaluates the solutions found from the Pareto optimal solution space of the solver. Finally, decision-makers’ preferences are analysed for monitoring the changes in the controlling parameters with respect to the changes in the decisions. A scenario analysis of the events by considering alternative possible outcomes is also conducted. It is found that the implemented methodology successfully routes the vehicles with optimal costs and low-carbon emission thus contributing to greening the environment on the demand side of a SC network.     

A tight upper bound for quadratic knapsack problems in grid-based wind farm layout optimization

The 0-1 quadratic knapsack problem (QKP) in wind farm layout optimization models possible turbine locations as nodes, and power loss due to wake effects between pairs of turbines as edges in a complete graph. The goal is to select up to a certain number of turbine locations such that the sum of selected node and edge coefficients is maximized. Finding the optimal solution to the QKP is difficult in general, but it is possible to obtain a tight upper bound on the QKP's optimal value which facilitates the use of heuristics to solve QKPs by giving a good estimate of the optimality gap of any feasible solution. This article applies an upper bound method that is especially well-suited to QKPs in wind farm layout optimization due to certain features of the formulation that reduce the computational complexity of calculating the upper bound. The usefulness of the upper bound was demonstrated by assessing the performance of the greedy algorithm for solving QKPs in wind farm layout optimization. The results show that the greedy algorithm produces good solutions within 4% of the optimal value for small to medium sized problems considered in this article.     

A genetic algorithm for optimal unequal-area block layout design

The use of a genetic algorithm (GA) to optimise the binary variables in a mixed-integer linear programming model for the block layout design problem with unequal areas that satisfies area requirements is analysed. The performance of a GA is improved using a local search through the possible binary variables assignment; results encourage the use of this technique to find a set of feasible solutions for the block layout design with more than nine departments.     

A genetic algorithm for facility layout

Facility layout is an important aspect of designing any manufacturing setup. However, the problem of finding optimal layouts is hard and deterministic techniques are not computationally feasible. In this work a genetic algorithm is presented for obtaining efficient layouts. The different aspects involved in the design of efficient genetic algorithms are discussed in detail. It is shown that the population maintained by the genetic algorithm for facility layout should consist of feasible solutions only. A new efficient crossover operator is developed. Experimental results obtained with the proposed algorithm on test problems taken from the literature are promising.     

Preprocessing for static and dynamic facility layout problems

Most facility layout problems have departments with unequal areas and have significant rearrangement costs. This paper describes a model and improved algorithm which simultaneously handles these parameters. An existing algorithm solves the dynamic facilities layout problem while permitting the departments to have unequal areas. One part of the algorithm solves a mixed integer programming problem to find the desired block diagram layout. This large, complex problem could only be solved optimally for small problems. Therefore a preprocessing method was developed to prespecify certain obvious department pair orientations, which had previously required binary variables. The method uses estimated location, department sizes, and flow costs to determine the probable variable values. Then, a revised branch and bound strategy solves for the less obvious department pair orientations. Test results show a significant cost reduction on a variety of previously published problems, and feasible solutions to previously unsolved problems. The algorithm found a layout solution to the standard . CRAFT problem which has 10 5% lower costs than the previously best published layout.     

Flexible job-shop scheduling problems with ‘AND’/‘OR’ precedence constraints

The purpose of this research is to solve flexible job-shop scheduling problems with ‘AND’/‘OR’ precedence constraints in the operations. We first formulate the problem as a Mixed-Integer Linear Program (MILP). The MILP can be used to compute optimal solutions for small-sized problems. We also developed a heuristic algorithm that can obtain a good solution for the problem regardless of its size. Moreover, we have developed a representation and schedule builder that always produces a legal and feasible solution for the problem, and developed genetic and tabu search algorithms based on the proposed schedule builder. The results of the computational experiments show that the developed meta-heuristics are very effective.