Numerical Methods and Algorithms to Solve the Problem of Quadratic Assignment and Their Application in Space-Planning Industrial Design
The problem of optimal placement of equipment indoors and the determination of the optimal parameters of transport-pipe-wire networks is considered. A fixed set of apparatus positions and a distance matrix based on an orthogonal metric are given. The Monte Carlo method, combinatorial analogs of the Gauss-Seidel method, the genetic algorithm and the corresponding hybrid methods, as well as known methods for obtaining the initial placement, namely, algorithms for sequential placement and placement according to the connectivity criterion for solving the problem of quadratic assignment with the optimal placement of equipment elements in the shops of enterprises, have been studied and implemented on a computer. A series of computational experiments based on the multistart procedure was carried out; it showed satisfactory computational qualities of the proposed variants of the methods, and also made it possible to identify their advantages and disadvantages. It has been established that the Gauss-Seidel method and hybrid analogues based on it have the best characteristics. The problem from the field of computer-aided design of the most complex and time-consuming stage of designing multi-assortment productions is considered - determining the rational layout of production. The actual applied problem of optimal placement of equipment for the production of phenyl-gamma-acid and phenyl-n-acid for both single and multiple connections of apparatuses has been solved.