Solving multi objective facility layout problem: modified simulated annealing based approach.

• Author: Singh, Surya Prakash

1. INTRODUCTION AND PROBLEM DESCRIPTION

   The facility layout problem (FLP) is of crucial importance to industrial engineers and well researched problem in academics. It was first formulated as quadratic assignment problem (QAP) by Koopmans and Beckman (1957) and later, Sahni and Gonzalez (1976) showed QAP is NP-complete. FLP is widely classified into single-objective FLP and multi objective facility layout problem (MOFLP). The first work on MOFLP was reported by Rosenblatt (1979) and the problem was described using the formulation shown below. The MOFLP is expressed as the multi-objective quadratic assignment problem (mQAP) given in equation (1)-(4).

   [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (1)

   [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (2)

   [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (3)

   [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (4)

   Where, n = number of facility, [X.sub.ij] = 1 if facility 'i' is assigned to location 'j' otherwise 0, Z =objective function value for MOFLP. [A.sub.ij,kl] (Cost term) in equation (1) represents the combined quantitative and qualitative factors in MOFLP. For in-depth details papers by Rosenblatt (1979), Dutta and Shahu (1982), Fortenberry and Cox (1985) and Urban (1987), Khare et al. (1988a, b), Harmonsky and Tothero (1992), and Chen and Sha (1999) can be referred. In this paper, authors have proposed modified simulated annealing based approach for generating layouts for MOFLP which removes the shortcomings of past approaches.

2. NORMALIZATION OF OBJECTIVES

   In this paper, authors have adopted the normalization procedure of Harmonosky and Tothero (1992). More details can be seen from the paper. The normalization steps for developing single composite objective are explained here using a sample problem of six departments. For ease of explanation only two objectives are considered here: one qualitative and another quantitative are shown in Table 1.

   The qualitative objective has closeness ratings from A to X. The quantitative objective is characterized by work flow ranging from 2 to 20 units of flow. All qualitative objectives are quantified by assigning closeness ratings with the highest value assigned to the A relationships. The value zero is assigned to U relationships, so they will have no effect on the final objective function value assigned to a layout. Negative values are assigned to X relationships. The objective function value is called the final layout score. The values used for quantifying the qualitative objective in the sample problem range from -1 for X relationships to 4 for A relationships, as suggested by Dutta and Sahu (1982). The qualitative matrix resulting from this conversion is shown in Table 2 along with the quantitative matrix.

   Once all objectives have been quantified, the data is normalized by dividing data from the sum of all relationship values for that objective. The result of this division is that the sum of all relationship values for any objective will be one. The result of normalization for the sample problem is shown in

   Next all values are multiplied by weights representing the relative importance of each objective. Then the total of all values for each pair of facilities is calculated. The composite relationships resulting for this conversion are shown in Table 4. This composite relationship matrix and distance matrix are used to calculate objective function...