Facility Layout Problems with Fixed Areas and Variable Shapes:

The objective of the facility layout problem is to determine the placement of a group of departments within a facility in such a way that, over a given period, the total distance traveled by personnel or equipment is minimized. Unfortunately, many layout algorithms represent departments in a rather simple way, mostly as cells, Le., squares of equal size. As a result, in a real-world application, the dimensions and positions in which departments are to be placed must often be figured out by the user on the basis of some cellular program output. In [14J an efficient heuristic was presented for the green field case (Le., design a layout from scratch) in which this shortcoming is overcome. The heuristic allows departments of different area and free shape. Each department is represented as a group of connected cells. The fixed number of cells used in this representation is a measure for the user defined area of the department. During the optimization process, which is based on simulated annealing, the department shapes change repeatediy until the final near-optimal layout is produced. In this paper we consider the brown field case, Le., we modify an existing layout. Basically, we use the same heuristic as in [14J. Only now, during the annealing process, the motion of the departments is confined to the ground floor of the present layout. In practice, apart from the area restrictions, many additional constraints may be imposed upon the departments. To show how to deal with such constraints we perform a case study based on a real life problem we solved in practice. Here one of the constraints is that four of the departments must lie at one particular side of the building. We present a series of steps to solve the problem. One of these steps is a Branch-and-Bound procedure with approximate lower bounds that are each obtained through an annealing process fixing certain departments. In the last step we design a detailed blueprint of the desired layout for the building.