A new heuristic procedure for quadratic assignment problems

الملخص EN

In this work, a new heuristic procedure is developed for the solution of Quadratic assignment problems after illustrating various known procedures, and an attempt to increase the efficiency of near-optimal solutions obtained from known heuristic procedures is carried out.

Quadratic assignments are used for solving a wide range of problems such as the design of control panels to minimize execution time and the assignment of manufacturing departments among locations to achieve optimal product movements.

This work is based on developing a new heuristic procedure using an improved decision procedure developed form the NP-complete nature and environment of assignment problems.

In order to assess the efficiency of the new procedure, which depends on constructing the solution, a comparison is made with that of VNZ (for Vollmann, Nugent and Zartler) which is considered to be one of the most efficient procedures used for solving such problems, and which depends on improving a given initial solution.

Final results show a distinctive improvement in the solutions of the various randomly generated problems, and obviously, evidence of the exact solution gained using total enumeration techniques is far essential, as a measure, in the comparisons carried out between the resulting solutions of the mentioned procedures.

Three different tests are carried out in this work including 26 randomly generated problem, each is represented by adistance and a volume flow matrix with different matrix dimensions, to be employed in the process of evaluating the efficiency of the improved heuristic procedure in terms of solution accuracy and processing time consumption.

C++ was employed in constructing the program structures of the mentioned procedures.