Dynamic programming interpretation of construction-type plant layout algorithms and some results

This paper presents a dynamic programming interpretation of some existing construction-type algorithms for the CAD of plant layouts. The two sub-problems of constructing a layout by these algorithms are first, the selection of a department for next placement, and second, locating it in the available space in an optimum manner. The first problem is tackled by adopting a heuristic. Successive choices of this nature lend themselves to a dynamic programming interpretation. The second problem is solved by allocating those blocks of area in the vicinity of existing departments which minimize the cost of materials handling between the new and the existing departments. It is found that application of dynamic programming significantly improves the efficiency of existing construction-type procedures. Some new heuristics for the first sub-problem are also examined. Computational results on test problems indicate that more complex policies might yield better results when the number of departments becomes larger.