Search

A quadratic assignment problem (QAP), which is a combinatorial optimisation problem, is developed to model the problem of locating facilities with material flows between them. The aim of solving the QAP formulation for a facility layout problem (FLP) is to increase a system’s operating efficiency by reducing material handling costs, which can be measured by interdepartmental distances and flows. The QAP-formulated FLP can be viewed as a discrete optimisation problem, where the quadratic objective function is optimised with respect to discrete decision variables subject to linear equality constraints. The conventional approach for solving this discrete optimisation problem is to use the linearisation of the quadratic objective function whereby additional discrete variables and constraints are introduced. The adoption of the linearisation process can result in a significantly increased number of variables and constraints; solving the resulting problem can therefore be challenging. In this paper, a new appro...

In this paper we discuss two particular layout problems, namely the Single-Row Equidistant Facility Layout Problem (SREFLP) and the Single-Row Facility Layout Problem (SRFLP). Our aim is to consolidate the two respective branches in the layout literature. We show that the SREFLP is not only a special case of the Quadratic Assignment Problem but also a special case of the SRFLP. This new connection is relevant as the strongest exact methods for the SRFLP outperform the best approaches specialised to the SREFLP. We describe and compare the exact approaches for the SRFLP, the SREFLP and Linear Arrangement that is again a special case of the SREFLP. In a computational study we showcase that the strongest exact approach for the SRFLP clearly outperforms the strongest exact approach tailored to the SREFLP on medium and large benchmark instances from the literature.

The Quadratic Assignment Problem (QAP) is a difficult and important problem studied in the domain of combinatorial optimisation. It is possible to solve QAP instances with 10--20 facilities using exhaustive parallel algorithms within a few days on a cluster machine. However, large QAP instances with more than 100 facilities are not solvable using exhaustive techniques. We have explored a variety of Genetic Algorithm crossover operators for this problem and verified its performance experimentally using well-known instances from the QAPLIB library. By increasing the number of processors, generations and population sizes we have been able to find solutions that are the same as (or very close to) the best reported solutions for large QAP instances in QAPLIB. In order to parallelise the Genetic Algorithm we generate and evolve separate solution pools on each cluster processor, using an island model. This model exchanges 10% of each processor’s solutions at the initial stages of optimisation. We show experiment...

In real decision making problems, many conflicting objectives have to be taken into account. With increasing awareness of this, multi-objective problems have become more and more popular. Similarly, the design of the multi-objective facility layout problem (MOFLP) has generally been recognised as an important issue in the modern manufacturing system. The MOFLP is formulated as a quadratic assignment problem (QAP) which is NP-hard and solving MOFLP is a tough problem. A new three-level AHP-based heuristic algorithm for resolving the MOFLP is presented here. It also presents a new normalisation procedure (H-1), and a new heuristic method (H-2) for generating objective weights. The proposed approach consists of three levels. The first level applies AHP to generate paired comparison matrices, the consistency of matrix, to convert inconsistent matrices into consistent ones and then generate a qualitative objective matrix; the second level applies normalisation procedure (H-1) to normalise matrices of qualitati...

The Generalised MAchine Layout Problem (GMALP) is a generalisation of the integrated machine and layout problem, which is an extension of the machine layout problem. More specifically, the GMALP is the designing of a facility layout by defining the product mix, selecting the number of machines to be used, assigning these machines to the plant floor, and assigning products to machines such that total profit is maximised. Moreover, the GMALP integrates the quadratic assignment problem with a multicommodity flow problem. Therefore, the GMALP is a computationally intractable problem. Consequently, a mixed-integer nonlinear programming model was developed and used to solve small problem instances. Also, two simple construction algorithms and a tabu search (TS) heuristic were developed for solving large GMALP instances in acceptable computation times. In addition, a test dataset was used to evaluate the performances of the TS heuristic using the different construction algorithms. The results show that the TS he...

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, Xij s take real values between zero and one. We identify promising Xij s having a value strictly greater than 0.5 in the optimal solution and set them to one. We add the constraints (Xij = 1) associated with promising Xij 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.

This paper describes a heuristic algorithm for solving the plant/facility location problem by applying ant-colony optimization meta-heuristic. The facility location problem is discussed, and a mathematical formulation is presented. The problem is then modelled as a quadratic assignment problem. An ant algorithm is developed to solve the problem. The results reveal that the proposed algorithm can be adaptively constructed to solve discrete plant location problems. This has been applied to a set of known test problems and appears to be able to compete with other current solutions with encouraging results.

This paper addresses two real-life assignment problems. In both cases, the number of employees to whom tasks should be assigned is significantly greater than the number of tasks. In the simple job ...

In a dynamic facilities layout problem, the objective is to minimize total costs: the flow costs over a series of discrete time periods plus the rearrangement costs of changing layouts between time periods. By assuming unit department sizes, the problem is modelled as a modified quadratic assignment problem. Five algorithms are modified to include the dynamic aspects. A cutting plane algorithm found the best solutions to a series of realistic test problems, outperforming exchange, branch and bound, dynamic programming and cut tree algorithms. It was able to solve a 30-location 5-time-period problem in 200 CPU seconds.

A methodology is proposed to design a GT cell by considering the intercell parts flow in GT cellular manufacturing systems. The problem of GT cell formation is described in a graph using the quantities to be produced in the specified time period and the process routes for producing the products. The objective of this paper is to minimize the total number of parts produced in more than one cell. The problem, formulated as a quadratic assignment problem (QAP), is solved using both Lagrangean relaxation technique and the optimality conditions of quadratic program. Furthermore, in order to obtain the giobal optimal solution rather than the local optimal solution, a branch-and-bound algorithm is employed. Finally, numerical examples are used to show the effectiveness of the solution techniques and GT cell formation procedure. Moreover, a computer simulation is presented, showing the effectiveness of cellular manufacturing systems

SUMMARY The problem of grouping of parts has been addressed in the past using clustering methods and integer programming. This paper presents an assignment model to solve the grouping problem. A similarity coefficient matrix is used as the input to the assignment problem. Closed loops in the form of subtours are identified after solving the problem and are used as the basis for grouping. The method has been applied to a number of examples. Compared with the earlier mathematical programming model, viz., the p-median model, the assignment method emerges as a distinctly superior technique both in terms of quality of solution and computational time.

In this paper, we formulate the quadratic assignment problem through multiple objective programming in which we can have several objectives. In the facility layout problem, the objectives can be materials handling cost, production rate, and flexibility. We define efficiency and describe how efficient alternatives can be generated. A heuristic procedure based on pairwise exchange of subfacilities is developed to generate the efficient solution associated with a given set of objective weights. Our approach could just as easily implement the graph theoretic or other approaches to solve the quadratic assignment problem and generate efficient points associated with given weights. A paired comparison method based on the strength of preference among alternatives is developed. The paired comparison method generates the decision maker's weights of an assumed unknown utility function. The method asks simple questions and uses linear programming to solve the problem. An experiment with the developed computer package...