The plant layout problem: a quadratic set covering approach and a branch and bound hybrid construction algorithm

Sander van der Zwan

The econometric most interesting part the Plant Layout Problem is the minimization of the distance dependent costs and moving costs. The biggest part of the distance dependent costs can be attributed to the variable internal transport costs. Minimizing variable internal transport costs can therefore be translated to minimizing the frequency of transport between plant areas (like machine areas or storage areas) times the cost per unit of transport times the distance between plant areas. This implies that the location of all areas should be chosen so that variable internal layout costs are minimized.

The problem of determining the optimal location of areas in a plant falls in the class of the Quadratic Set Covering (QSC) problems. Because of the large amount of possible area shapes and locations in a plant, there are no computationally feasible optimal or hybrid algorithms available for the QSC problem.

However, relaxing the problem by restricting plant area shapes and locations, gives the opportunity to design two hybrid solution methods for the particular problem studied in the thesis.

The first method, called the Quadratic Set Covering (QSC) Approach, relaxes the problem by assigning (part of) squared blocks to areas and by relaxing restrictions. A reduced gradient method and quasi Newton algorithm are used to solve the layout problem for a local optimum. Using several tricks, the global optimum among the local optima, is searched for. A proof for global optimality of this relaxed layout, however, can not be provided. The locally optimal relaxed layout is then transformed into a feasible one by reintroducing the restrictions. With the help of an improvement algorithm the feasible layout is improved. Finally, the system provides the user the possibility to adjust the layout interactively.

Layouts produced by the QSC Approach can not be proven to be globally optimal and computation time is too high for producing alternative layouts quickly.

For this reason a second algorithm, called the Branch & Bound Hybrid Construction Algorithm, is designed. To decrease computation time, the area shapes and locations were restricted even more than for the QSC Approach. A Branch & Bound algorithm produces the global optimal layout among all feasible relaxed layouts. By applying the feasibility and improvement algorithm to the global optimal and alternative relaxed layouts and by making interactive changes, several good layouts are found.

To choose the layout to be implemented in a real life situation, the layouts produced by both methods have to be compared on qualitative criteria.

05-04-2000   Info: