A lagrangian based procedure for solving twin objective facility layout problem.

• Author: Mishra, Rajesh P.

1. INTRODUCTION AND LITERATURE REVIEW

   Multi objective FLP has been attempted by many reserchers in the past (see Rosenblatt (1979, 1983); Dutta and Sahu (1982); Fortenberry and Cox (1985); Malakooti and D'Souza (1987); Urban (l987, 1989); Malakooti (1989); Harmonsky and Tothero (1992); Chen and Sha (2005)). Matai et. al (2010) and Singh and Sharma (2006) for a detailed review of literature. If all objectives are quantitative, then a composite objective is constructed by assigning weights to these objectives. If some objectives are qualitative, then efforts are made to convert these into quantitative measures; and again after that a composite measure is prepared by assigning weights to these objectives.

   In this paper, we put constraints associated with all but one objectives (that assures some minimum fulfilment of these); and then use lagrangian relaxation based heuristic to reduce the problem to standard QAP. The QAP is then solved by procedure due to Singh and Sharma (2006). This novel procedure is likely to have many merits; and these are described in conclusion.

2. FORMULATION OF TWO OBJECTIVE FLP

   Problem P

   [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

   [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2)

   [n.summation over (j=1)] [X.sub.ij] = 1 [for all] i = 1, ..., n (3)

   [n.summation over (i=1)] [X.sub.ij] = 1 [for all] i = 1, ..., n (4)

   [X.sub.ij] = {0,1} [for all] i, j = 1, ..., n (5)

   Where,

   [x.sub.ij] is 1 if facility 'i' is located at location 'j' ELSE 0. [f.sub.ik] is flow between facilities 'i' and 'k', [d.sub.jl] is

   distance between locations 'j' and T, and [C.sub.jl] is travelling time between locations 'j' and T. T is the upper limit on the travel time.

   Constraint (1) denotes the material handling cost; constraint (2) denotes the time taken to move through the shop. Constraints (3) ensure that every job is assigned to a slot; and constraints (4) ensure that every vacant slot gets a job. Constraints (5) ensure that variable [x.sub.ij] are binary 0-1 variables.

   We associate a multiplier U with constraint (2) and include it in the objective function. Now the problem P is reduced to its lagrangian relaxation as given below.

   Problem LR_P

   [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (6)

   s.t. (3)-(5).

   The problem LR_P is identical to QAP and is NP-Hard. We use the heuristic due to Singh and Sharma (2008) to obtain a very good solution to LR_P. This is reproduced below for the sake of completeness.

3. SOLUTION...