| Facility
Layout Design using Genetic Algorithm |
Any major industry's success depends invariably on the location of its bases,
production centers and warehouses. Thus locating the sites before establishing
these units is done by facility location and planning unit of the industry. For
greater profits the facilities should be located at an optimum distance from the
market , raw material procurement sites utilities like water , sand etc. For these
problems involving layout a number of algorithms are in use like ALDEP,CORELAP,
CRAFT etc. But since the location of facilities have become very complex due to
greater constraints these days a determined search of a good algorithm begins.
This can be achieved by using GENETIC ALGORITHMS. This type of evolutionary algorithms
have made the computational effort fast and accurate.
Introduction
Material handling and layout related costs have been estimated to be
about 20%-50% of the total operating expenses in manufacturing. To stay competitive
in the market these high overhead costs have to be reduced considerably. One way
of doing this is to develop an efficient facility layout. The secondary benefit
of doing so is in reducing the large Work-In-Process inventory and justifying
the costly long-term investment. Developing an efficient layout is primarily finding
the most efficient arrangement of n facilities in m locations (m >= n).
Traditionally
the layout problem has been presented as a Quadratic Assignment problem (QAP).
The layout problem can also be termed as one-dimensional or two-dimensional problem
corresponding to the single-row or multi-row patterns of layout. It is well known
that QAP is NP-complete category due to the combinatorial function involved and
cannot be solved for large layout problems. An alternative model for the QAP that
consists of absolute values in the objective function and constraints that can
be used for continuous formulations instead of discrete. The efficiency of these
models however depends upon the efficient integer programming algorithms. PROBLEM
FORMULATION
The facility layout problem has been termed as Quadratic Assignment
Problem (QAP) because the objective function is a second-degree polynomial function
of the variables, and the constraints are identical to the constraints of the
assignment problem. The objective of the QAP is to find the optimal assignment
of n facilities to n sites in order to minimize the material handling cost expressed
as the product of workflow and the travel distance. The QAP can be formally stated
as where wij is the workflow between the facilities i and j, a(i) denotes the
location to which i has been assigned. The distance function d is anyone of the
lp distance between the facilities i and j and is defined as where (xi, yj )and
(xi, yj ) are the geometric centers for the locations a(i) and a(j) . If p = 1
the distances are the rectilinear distances whereas when p = 2 the distances are
Euclidean. Each position can be occupied by only one facility and no facilities
overlap each other. The Algorithms are based on those aforementioned statements
and assumptions taking care of both the Rectilinear and the Euclidean distances
while minimizing the objective.
<<back |