Classification Of Facility Layout Problems

The purpose of this literature review is to explore the general facility layout problem, the dynamic facility layout problem, the models that have been used to represent the facility layout problem and the algorithms that solve the models,.

Classification of Facility Layout Problems

“Determining the most efficient arrangement of physical departments within a facility is defined as a facility layout problem (FLP)” (SMTF Ghomi et al, 2011). Over the period of several couple of decades, FLP have been studied by several researchers to a significant extent for establishing optimum and universal method to solve the problem and a large variety of solution procedures based on algorithms have been proposed.

Facility layout problems are classified into two categories, static facility layout problem (SFLP) and dynamic facility layout problem (DFLP).

Static facility layout problem (SFLP)

The static facility layout problem (SFLP) is the determination of the most efficient arrangement of departments within a facility with scope of improvement only within the layout boundary. The facility can be manufacturing plants, administrative office buildings, or service facilities,( Alan R, jin et al 2005). The static facility layout problem (SFLP) approach generally assumes that flow between machines, product demand, and levels of product mix are constant during the planning horizon.

Dynamic facility layout problem (DFLP)

When material flow assumes varied path between departments during the planning horizon, the problem becomes the dynamic facility layout problem (DFLP). Under a volatile environment, demand is not stable. It changes from one production period to another. To operate efficiently under such environments, the facilities must be adaptive to changes of production requirements. From a layout point of view, this situation requires the solution of the dynamic layout problem (DLP). (Adil, Turkay et al 2005)

Tree representation of the layout problems

Essential feature of layout problems are characterized in tree representation diagram as shown in fig.

Tree representation of the layout problems (Amine,henri et al 2007)

Algorithms for Solving facility layout problems

There are two types of algorithms for solving facility layout problems. One is heuristic algorithm and another is optimal algorithm.

Heuristic algorithms

These algorithms provide a solution which possibly might not just be the best fit for the problem. A good heuristic approach usually produces the best solution for most of the small problems. A heuristic algorithm works towards an optimal solution but ends its search when it finds a ‘good enough’ solution. As computation increases, these algorithms will approach the optimal solution. The purpose of the heuristic algorithm is not to find the best or optimal solution but to find an acceptable solution in an acceptable amount of time using an acceptable amount of computer memory. Heuristic algorithms can also be classified as construction algorithms and improvement algorithms.

Construction algorithms

In Construction algorithms layout is constructed from the beginning and facilities are assigned to a site, one at a time, until the complete layout is obtained. (andrew, et al 1987). The plant layout software using a construction type algorithm will first construct a solution in an open floor area from raw data. The algorithm basically takes relationships between activity areas into account and generates a block layout. Their basic approach is to find a starting point or initial activity placement and then add the remaining activity areas according to certain rules. In some algorithms the rules are similar to Muther’s vowel letter sequencing (A-E-I-O-U-X) for closeness relationships. Three well known examples of construction algorithms are CORELAP, PLANET, and ALDEP.

CORELAP

Computerized Relationship Layout Planning (CORELAP) is a construction algorithm and was developed by Robert C. Lee. It is the oldest construction algorithm based on Richard Muther’s manual procedure of converting the Relationship Chart into a layout. The basic inputs required by CORELAP are the relationship chart and the area requirements of each department. CORELAP begins by calculating the “total closeness rating” (TCR) for each department where TCR is the sum of the numerical values assigned to the closeness relationships (A=6, E=5, 1=4, etc.).

A disadvantage of CORELAP is that it has problems when an attempt is made to fix departments in a certain location. CORELAP does not take into account the building and is dependent on the layout arrangement. It is useful for new plants where the objective is to determine new building design and not for buildings that are already in existence.( Altaf et al 1995)

ALDEP

Automated Layout Design Program (ALDEP) was developed within IBM and was presented by Jerrold Seehof and Wayne Evans. It was first published in 1967. ALDEP has the same basic data input requirements as CORELAP. It differs from CORELAP in using the Total Closeness Rating for placement of departments; ALDEP selects and places departments randomly. CORELAP attempts to construct the one best layout while ALDEP constructs many layouts and rates each layout and thus leaves the final decision of selecting the appropriate layout to the facility designer. Advantages of using ALDEP include rectangular or square layouts. It is also capable of handling facilities with up to three floors and provides the capability to fix departments in a certain location and to include docks, elevators and stairwells. The disadvantage of ALDEP is that it randomly picks departments for consideration in the layout process. Hence, ALDEP should be executed several times to assure that the layouts generated are the “best” layouts. The “best” layout will eventually generated will be presented to the facility designer for selecting the most appropriate and feasible layout.

PLANET

Plant Layout Analysis and Evaluation Technique (PLANET) is another construction type algorithm. It uses the same input requirements as CRAFT. PLANET is flexible in that it will accept material flow data in three formats and that there are three different layout construction phases available. The three phases that are available to generate a layout are as follows: The first phase involves the translation of the input data so that it is useful to the algorithm in PLANET. The second phase involves the selection of the order in which the departments are to be considered in the layout. The third phase involves the determination of the placements of the departments when they are considered for the layout (placement priority from the highest to the lowest is 1 to 9).

PLANET converts the materials flow information from either a from-to cost chart, a from-to chart or a penalty chart to a flow-between cost chart. This is done by adding the values in both directions between departments and then entering the sum for the flow in each direction. The basis for the PLANET selection algorithms are the flow-between cost chart and placement priorities

The advantages of using PLANET are that it is very flexible in allowing inputs such as materials flow data to be entered in three formats and having three methods in constructing a layout. The disadvantages with PLANET are that in its conversion of inputs to a flow-between cost chart, it considers the closeness relationships between departments but conceals the direction of flow among departments. This may result in layouts that have a considerable amount of backtracking among the departments.

Improvement algorithms

An improvement algorithm always begins with an initial layout. The algorithm exchanges department locations until a layout is found that cannot be improved. The quality of the layout generated depends upon the initial layout and the ability of the algorithm to exchange multiple departments at a time. The basic approach of improvement algorithms is to minimize transportation cost or movement cost by reducing the distance on the most traveled routes. Popular examples of improvement type computer routines are COFAD, CRAFT and BLOCKPLAN.

CRAFT

Computerized Relative Allocation of Facilities Technique (CRAFT) was the first improvement type algorithm used in computerized facilities design. CRAFT was developed in 1964 by Armour and Buffa. CRAFT begins with an initial layout that is entered by the analyst. The layout is evaluated, and pair wise exchanges of departments are made to try to improve the layout. Layouts are evaluated on the minimization of material flow cost between departments. Pair wise exchanges are only made between departments that are of equal size or have common boundaries. CRAFT can handle up to 40 departments and is preferred by many over CORELAP and ALDEP due to its evaluation of layouts. CORELAP and ALDEP minimize the quantity of flow between departments and maximize closeness ratings, while CRAFT minimizes the cost of flow between departments. The initial layout utilized by CRAFT restricts the boundaries of all layouts generated from it. CRAFT does not work well with departments having unequal areas because it is unable to shift the layout to allow nonadjacent departments of unequal areas to be exchanged. (jin et al 1996) used CRAFT to solve the failure-to-fit problem by changing the size and/or shape of the departments in a systematic manner without the help of humans

COFAD

Computerized Facilities Design (COFAD) is a modification of CRAFT. COFAD’s algorithm first tries to improve the initially inputted layout by a procedure that Is similar to CRAFT except that COFAD is capable of considering straight line as well as rectilin2ar distances between departments being considered for interchange. This is useful for materials handling systems that use conveyors that do not have to follow aisles in a rectilinear fashion. COFAD then determines the cost of performing each move using the feasible materials handling system alternatives available. This is dependent on the type of material handling system chosen (ie. fixed path equipment such as conveyors or mobile equipment such as tote carts). COFAD’s next function is to use the above move costs to determine a minimal cost of materials handling system. The disadvantages of using COFAD are that the sensitivity analysis within COFAD only considers variations in the total flow volume for a predefined product mix and does not evaluate changes in product mix. (Vic Kichodhan et al 1990)

BLOCKPLAN

BLOPLAN stands for Block Layout Overview with Computerized Planning. A computer routine which allows the use of random, construction, and improvement type algorithms is BLOCPLAN. It was developed by Dr. Charles E. Donaghey, Chairman of the Industrial Engineering Department at the University of Houston. BLOCPLAN is an interactive program used to develop and improve both single and multi storey layout BLOCPLAN is a departmental location system that includes random, construction and improvement type algorithms for developing layouts It is a simple program which generates good initial layouts due to its flexibility based on several imbedded options. It uses both quantitative and qualitative data to generate several block layouts and their measure of fitness. ( Pinto, et al 2007). BLOCPLAN can display a layout graphically on the screen.

The inputs that are required are: the no of department (maximum 18) The Names of the departments, their corresponding areas, and a relationship chart. The chart relationship format is the same as suggested by Mather in his Systematic Layout Planning procedures. Once the relationship chart has been entered, BLOCKPLAN then displays a relationship vector of “Code equivalent Score”. The purpose of this is to allow the facility designer to indicate the importance attached to the rating of the relationship chart, BLOCPLAN needs to use some quantifiable factor to rake decisions when it generates and scores layouts. It uses the CES vector to assign a numeric value relationship chart. The default CES vector values are 10, 5, 3, 2, 1, 0, and -10. This means that has “A” rating is worth 10, an “E” rating is worth 5 and so on. .An “X” rating is worth -10. The facility designer can also set his/her own values if desired. (Vic Kichodhan et al 1990)

The procedure that BLOCPLAN uses to generate layouts is that it first determines an Importance Rating (IR) for each department in the layout. The rating is the sum of all the relationship scores for each department, using the CES vector values. Second, a menu for the facility designer is displayed. The options are:

Random Layout.

Layout Algorithm.

Improvement Algorithm.

Adjust Relationship Information.

Manually Insert Departments.

Review Saved Layouts.

Stop.

Save Problem Data

Selecting option one, Random Layout, will cause layout to be developed without regard to the relationship chart. The Departments will be located randomly in one of the eighteen zones that the software has generated. BLOCPLAM divides the building layout in to three tiers, with three zones per tier. Each zone can be further divided into its left and right side giving the possible eighteen zones.

BLOCPLAN randomly selects one of the eighteen locations for each department and assigns it to a particular location.

After all the departments have been assigned a location, the software proceeds to draw the layout. It looks at the departments that are located in Tier 1 up to six departments can be located in Tier 1. The total required area of a tier is the sum of all the areas for the departments located in that particular tier. Each department is drawn in proportion to its area and the departments are rectangular in shape. If a department with a small area is the only one located in a tier, it will be drawn as a long narrow department stretching across the entire layout. BLOCPLAN continues with this procedure for all the tiers.

The layout generated is scored by the scoring algorithm based on an adjacency criterion. The CES scores for departments that share a common boundary in the layout are summed and then divided by the sum of all the positive CES scores from the relationship chart. A score of 1.0 indicates that all “good” relationships in the relationship chart have been satisfied in the layout

Selecting option two, Layout Algorithm, will cause the software to make available to the facility designer a layout algorithm. The algorithm places departments that have high IR scores in the center of the layout and then surrounds them with departments with high relationships. Departments with an “X” relationship are separated as much as possible. This method of locating the departments produces layouts that are “better” than the random process.

Selecting option three, Improvement Algorithm, will cause the software to try to improve on a layout that has been saved in memory. The improvement algorithm interchanges each pair of departments in the layout and then displays its score before moving to the next interchange when the facility designer hits the “Return Key”. The number of interchanges is the combination of the number of departments taken two at a time. For example, for ten departments there will be forty five interchanges. The optimum layout can be obtained by using option two, Layout Algorithm, and then using this option, Improvement Algorithm, to improve on the previous saved layout.

Selecting option four, Adjust Relationship Info, allows the relationship information to be changed. The facility designer can change the relationship information and the CES scores that were originally entered. This allows the effects of changes in the relationship chart to be evaluated

Selecting option five, Manually Insert Departments, will allow the manual placement of departments in the layout. Each department can be manually placed in the desired tier and zone. This is the same as fixing a department in a layout

The advantages of BLOCPLAN are that it is a useful tool to facility designers in that layouts can be generated or evaluated, the effects of changing the values in a relationship chart can be analyzed, and it only requires a microcomputer as opposed to a mainframe to operate. Although the processing time varies with the number of departments that have to be located, the limitation of BLOCPLAN being able to only handle eighteen departments limits the processing time to a reasonable amount. The disadvantages of BLOCPLAN are:

BLOCPLAN can only handle layouts with eighteen departments or less.

BLOCPLAN can only store twenty layouts in memory.

All the layouts are displayed on the screen within a rectangular drawing that has a horizontal length of 6.75 inches and a vertical height of 4.75 inches regardless of the number of departments in the layout or their placement in the layout.

Simulated Annealing Algorithms

Simulated Annealing (SA) is a method based on Monte Carlo simulation, which solves difficult combinatorial optimization problems. The name comes from the analogy to the behavior of physical systems by melting a substance and lowering its temperature slowly until it reaches freezing point (physical annealing). Simulated annealing was first used for optimization by Kirkpatrick et al. (1983). In the numerical optimization framework, SA is a procedure that has the capability to move out of regions near local minima. SA is based on random evaluations of the objective function, in such a way that transitions out of a local minimum are possible. It does not guarantee, of course, to find the global minimum, but if the function has many good near-optimal solutions, it should find one (George D. et al 2002)

Simulated annealing was also used in General Facility Layout Problems (GFLP) considering facilities areas, shapes and orientations or in Machine Layout problems (MLP) considering machine’s pick-up and drop-off points (Leonardo Chwif et al 1998).

SA was also used for dynamic facility layout problems for solving the problems for arranging and rearranging (when there are changes between the flows of materials between departments) manufacturing facilities such that the sum of the material handling and rearrangement costs is minimized (Alan R et al 2006).

Wang et al (2001) developed a model to solve the facility layout problem in cellular manufacturing system. In the model, they assumed that the demand rate varies over the product life cycle. The objective function was to minimize the total material handling cost and solve both inter and intra cell facility layout problems simultaneously.

Simulated annealing heuristic for the DFLP with budget constraint, and show the effectiveness of this heuristic on a set of numerical experiments (Ramazan et al., 2010).

Artificial Neural Networks

Neural networks are a potent method of optimization which relies on developing systems that exhibits self organization and adaptation in a similar, though basic, manner to the way in which biological systems work. A kind of artificial neural network model has been implemented for computation to solve a wide variety of discrete combinatorial optimization problems. A neural expert system is an interactive classification system with justification capability. This system begins with the knowledge representatives from a set of training examples, learns through representatives, and then develops the capability to correctly classify new cases based on learned knowledge. This classification capability makes the proposed neural expert system generate a conceptual construction layout in the form of the learned symbolic knowledge resonant to the input layout requirements.

ANN can be a system comprising N Ã- N neurons based on an artificial two-dimensional maximum neural network for an N-facility layout problem. ANN algorithm has given improved solutions for several benchmark problems over the best existing algorithms (Kazuhiro Tsuchiya et al 1996).

The annealed neural network combines characteristics of the simulated annealing algorithm and the neural network for rapid convergence of the neural network, while preserving the solution quality afforded by simulated annealing (Yeh, 2006). This have also found implementation in solving the facility layout problem

Genetic Algorithms

GAs came to the fore in the 1960s, through the work of Holland for solving many industrial and service sector problems that proved extremely difficult to solve with the available methods known at that time. The main contribution of GAs is solving optimization and search problems by providing a solution which is not the optimal one but which is nevertheless a good approximation to the optimal one. As a result of the enormous increase in the capacity of computer technology, applying GAs, in recent years has become more and more well-known, since the problem of the cost of using computer facilities which might have arisen, is in reality only a minor one (A.Gomez et al 2003).

With cyber technology gaining impetus software based on GA have been developed for problem solving. An improved hybrid genetic algorithm (IHGA) was developed to use a robust local improvement procedure as well as an effective restart mechanism that is based on so-called ‘shift mutations’ and applied to the well-known combinatorial optimization problem and quadratic assignment problem (QAP) (Alfonsas Misevicius et al 2004).

Extensive computational experiments for solving quadratic assignment problems using various variants of a hybrid genetic algorithm were carried out (Zvi Drezner et al 2008). Simple tabu and modified robust tabu as improvement algorithms in a hybrid genetic algorithm are superior than other tabu searches (concentric tabu, ring moves, all moves, robust tabu) (Jasmit singh kochher et al 1997) outline a GA based algorithm for solving the single floor facility layout problems for equal and unequal size department.

(Ming-Jaan Wang et al 2005) is focus on the unequal areas department facilities layout problem, and implements analysis of variance (ANOVA) of statistics to find out the best site size of layout by genetic algorithm.

The dynamic plant layout problem (DPLP deals with the design of multi-period layout plans Although an optimal solution method based on dynamic programming is available, it is not practical for large DPLPs and heuristics based on genetic algorithms can solve large DPLPs. (Jaydeep Balakrishnan et al 2003) extend and improve the use of genetic algorithms by creating a hybrid genetic algorithm and a computational study is carried out to compare the proposed algorithm with the existing genetic algorithms and a recent simulated annealing algorithm.

An important methodology in facility layout problems that can be used to gauge current and emerging trends in new design objectives and methodologies that address combinatorial optimization aspects and presents a state-of-the-art review of the application of the Genetic Algorithm (GA)(Kundu A et al 2010)

NP-hard problem of arranging a number of facilities on a line with minimum cost, known as the single row facility layout problem (SRFLP) and to solve this type of problems permutation-based genetic algorithm (GA) is used. (Dilip Datta et al 2011)

Tabu Search Algorithm

TS technique is a meta-heuristic search that is used to solve the combinatorial optimization problems TS, is usually dominated by neighborhood solutions in searching for an optimal solution. Unlike the GA, it is highly dependent on the values of the algorithm’s control parameters. TS is based on flexible memory structures in connection with strategic restrictions and aspiration levels as an approach for exploiting solutions.

The search begins when the parameters are chosen and a feasible solution to the problem is generated. The main parameters of TS technique are the neighborhood size, the size of tabu list, the aspiration criteria and stopping criteria. The operator that can be altered in order to generate neighborhood solutions is ‘move’. This operator can place each element to move from its location to any other location in the solution. From ‘move’, a set of neighboring solutions is generated through a pre- defined change to the current solution. Then the best solution is selected from the current set of neighboring solutions and this becomes the new current solution. Again, a new set of neighboring solutions is generated from the new current solution and the process repeats itself until the stopping criteria are met. (Lou Y. Liang et al 2008).

There are two new reaction strategies for the tabu search algorithm. The first strategy treats the tabu search algorithm as a target system to be controlled and uses a control-theoretic approach to adjust the algorithm parameters that affect search intensification. The second strategy is a flexible diversification strategy which can adjust the algorithm’s parameters based on the search history. These two strategies, combined with tabu search, form the Self Controlling Tabu Search (SC-Tabu) algorithm. The algorithm is implemented and tested on the Quadratic Assignment Problem (QAP). The results show that the self-controlling features of the algorithm make it possible to achieve good performance on different types of QAP instances. (Nilgun Fescioglu-Unver et al 2011)

Two extensions were suggested and tested for concentric tabu search for the quadratic assignment problem to include more permissible moves (Zvi Drezner et al 2005).

The optimal solution for special case of Single Row Facility Layout Problem (SRFLP) was proposed through a theorem by Hamed Samarghandi et al in 2010. He proposed a new algorithm based on tabu search for the SRFLP and suggest computational results of the proposed algorithm on benchmark problems show the greater efficiency of the algorithm compared to the other heuristics for solving the SRFLP.

Slicing tree based tabu search heuristic for the rectangular, continual plane facility layout problem (FLP) had been designed with procedure to calculate the layout corresponding to a given slicing tree on the basis of bounding curves (Daniel Scholz et al 2009). These layouts are slicing structures which are able to contain empty spaces to guarantee that stringent shape restrictions of facilities are kept. Due to these features this approach is better suited for practical use than so far existing ones.

Graph Theory

Graph theory (Seppanen and Moore, 1970) can be used as a means to create good layouts based on the flow matrix. A relationship diagram can be drawn as a weighted graph with the nodes signifying the departments and the edges representing the flow between the department pairs. The dual of this graph is a block diagram layout.

Graph theory approach, relationships (or flows) among facilities can be represented by a (relationship) graph in which vertices denote facilities and edges denote existence of flows or relationships between facilities. A requirement for existence of a block layout satisfying the relationships represented by a graph is that the graph be planar. A graph is planar if it can be drawn in the plane and each edge intersects no other edges and passes through no other vertices. The relationship graph may not be planar. A planar sub graph of a relationship graph is called a maximal planar graph (MPG) if no edges can be added without making the graph no planar. The dual of a (primal) planar graph can be constructed by placing a dual node in each face of the primal planar graph and by joining vertices corresponding to two faces (in the primal graph) that share an edge in their common boundary. (Here, faces are regions defined by a planar graph.) The dual of a planar graph is planar as well. (J-Y KIM et al 1995)

Russell D. Meller et al 1996 tells about developing a layout in the graph-theoretic approach requiring the following three steps:

(1) Developing an adjacency graph from department relationships (which departments are adjacent),

(2) Constructing the dual graph of the adjacency graph (represent departments as adjacent regions having specific boundaries),

(3) Converting the dual graph into a block layout (specifying departments with regular shapes and specific areas)

Graph theoretic approaches were also used to handle the unequal area block plan. In these approaches a block plan is constructed as the dual of a planar graph where nodes represent spaces and links represent required adjacencies. While it is always possible to construct a block plan from a planar graph which meets the given adjacency requirements between spaces and between spaces and the outside area, the resulting plan may not meet size and shape requirements imposed on each space. Constructing a block plan that meets size and shape requirements is a nontrivial problem. (Robin S. Liggett et al 2000). Other industrial problems like furniture production line designing were also solved using graph (Wilsten and Shayan 2007).

The main problem concerned with applying graph theory to facilities layout is the conversion of the dual graph to a block layout (S. A. IRVINE et al 2010) gives a new method of producing a planar orthogonal layout or floor plan of a set of facilities subject to adjacency and area constraints. It improves upon previous approaches by accepting any maximal planar graph representing the adjacencies as input. Simple selection criteria for choosing the next facility to be inserted into the floor plan are used. Further, any sensible orthogonal shape for the facilities in the resulting floor plan can be generated.

Optimal algorithm

During the 1960’s considerable research was done in developing optimal algorithms. Optimal algorithms find the best solution. However they are not practical due to limitations on computer time and space. Some optimal algorithms are classified as given below.

Quadratic Assignment Model

The quadratic assignment model (Koopmans and Beckman 1957) represents the problem of locating numerous facilities that required material flow between them. The name QAP was given because the objective function is a second degree function of the variables and the constraints are linear functions of the variables. The objective function maximizes the revenue gained by assigning the departments to a location, less the cost of the material flow between the departments. The mathematical model of the quadratic assignment problem (QAP) is:

The integer variable, Xij is equal to 1 if department i is assigned to location j, otherwise the variable is equal to 0. The constant aij is the area required for department i to location j and fik is the material flow between departments i and k, and Cjl is the cost of material flow between location j and l. The first constraint ensures that each location will be assigned exactly one department and second constraint ensures that each department will be assigned to exactly one location.

Layouts generated using the quadratic assignment models are often used as a tool in formulating a final layout. The QAP takes into consideration the material flow between departments, however, the model operates under the assumption that all department areas are equal which in many cases is impractical to presume. For this reason, the layout generated by the quadratic assignment problem often serves as a starting point for developing a final layout. (Ekrem Duman et al 2007) used the quadratic assignment problem in the context of the printed circuit board assembly process. (A.S. Ramkumar et al 2008) concentrates on multi-row machine layout problems that can be accurately formulated as quadratic assignment problems (QAPs). A genetic algorithm-based local search approach is proposed for solving QAPs.

2.4.2.2 Quadratic set covering problem

The quadratic set covering problem takes the quadratic assignment problem a step further by including the area of each department in the model (Bazaraa 1975). A branch and bound approach is used to optimize the problem. The quadratic set covering problem models single or multi-story buildings, and departments with irregular shapes. It is able to generate initial layouts and add departments to an already existing layout.

The quadratic set covering problem has the advantage of varying areas, but it falls short of being realistic. The model assumes that the shape of the departments is known and fixed. This limits the problem’s ability to find a better solution by varying the shapes of the departments to reduce the distance between centroids.

2.4.2.3 Linear Integer Programming Problem

The linear integer programming problem is a reformulation of the quadratic assignment problem. Lawler (1963) was the first to formulate the facility layout problem as a linear integer programming problem by defining Yijkl = Xij Xkl which reformulates the quadratic assignment problem into a linear integer programming problem. The number of integer variables required are n2+n4 the number of constraints required are nd+2n+l (n = number of departments). The number of integer variables and constraints required is much more than required for the quadratic assignment problem. These larger problems are more difficult to solve optimally because of the increased amount of computation and memory required.

The facility layout problem (FLP) with unequal departmental areas which is encountered in many manufacturing, service facilities (Abdullah Konak et al 2006) and the problem of arranging a number of departments on a line (Andre R.S. 2006) were solved by a mixed-integer programming formulation.

2.4.2.4 Branch and Bound Algorithms

The first two branch and bound algorithms were developed by Gilmore (1962) and Lawler (1963) separately for solving the quadratic assignment problem. These algorithms implicitly evaluate all possible solutions to a problem, resulting in an optimal solution. These algorithms require a large amount of memory and computational time governed by the number of integer variables required. In this algorithm, each facility is allocated to each location stage by stage. The partial layout is evaluated and compared to a lower bound. If the cost of partial layout is less than the lower bound, the partial layout is kept and used as a lower bound in subsequent iterations, otherwise it is discarded and the branch is fathomed.

The branch and bound algorithm are also used to solve the two-dimensional layout problem (Solimanpur and Jafari, 2008). A two-dimensional layout is a systematic arrangement, in which the manufacturing facilities are laid in a planar area. A mathematical model was proposed for determining the optimum layout of machines in a two-dimensional area. The parameters considered by the proposed model were (a) production capacity of machines, (b) multiple machines of each type (machine redundancy), (c) processing route of parts, (d) dimensions of machines. A new parallel Branch and Bound algorithm for the Quadratic Assignment Problem, which is a Combinatorial Optimization problem known to be very hard to solve exactly also exist in literature (Bernard Mans et al 1995). The branch and bound algorithm are also used for continuous facility layout problem (Xie and Sahinidis, 2008).