Obtaining an Initial Solution for Facility Layout Problem

The facility layout approaches can generally be classified into two groups, constructive approaches and improvement approaches. All improvement procedures require an initial solution which has a significant impact on final solution. In this paper, we introduce a new technique for accruing an initial placement of facilities on extended plane. It is obtained by graph theoretic facility layout approaches and graph drawing algorithms. To evaluate the performance, this initial solution is applied to rectangular facility layout problem. The solution is improved using an analytical method. The approach is then tested on five instances from the literature. Test problems include three large size problems of 50, 100, and 125 facilities. The results demonstrate effectiveness of the technique especially for large size problems. 1. Introduction The facility layout problem seeks the best positions of facilities to optimize some objective. The common objective is to reduce material handling costs between the facilities. The problem has been modeled by a variety of approaches. A detailed review of the different problem formulations can be found in Singh and Sharma [1]. The facility layout problem is an optimization problem which arises in a variety of problems such as placing machines on a factory floor, VLSI design, and layout design of hospitals, schools. The facility layout approaches can generally be classified into two groups, constructive methods and improvement methods. In this paper, we consider the placement of facilities on an extended plane. Many improvement approaches have been proposed for this problem. All improvement procedures require an initial solution. Some approaches start from a good but infeasible solution [2–4]. These models contain a penalty component in their objective function. Hence, these approaches minimize objective function value for feasible solutions. But some approaches require a feasible initial solution. These approaches use a randomly generated initial solution [5, 6]. Mir and Imam [7] have proposed simulated annealing for a better initial solution. They have shown that a good initial solution has a significant impact on final solution. In this paper, we introduce a new technique for accruing an initial placement of facilities on an extended plane. The technique consists of two stages. In the first stage, a maximal planar graph (MPG) is obtained. In the second stage, the vertices of MPG are drawn on the plane by graph drawing algorithms. Then, vertices are replaced by facilities. Hence, an initial solution is obtained. In an MPG,