MULTIPLE-PURPOSE SOLUTION TO HOMOGENEOUS ALLOCATION PROBLEMS BASED ON MODIFIED ROMANOVSKY ALGORITHM AND SELECTIVE-PERMUTATION ALGORITHM

Abstract

The problem on improving precision properties of the fast approx imate algorithms without sacrifice of their resource properties is set. A multiple - purpose approach to the application of the modified Rom a novsky algorithm (MRA) and the selective - permutation method (SPM) for solving homogeneous allocation problems (HAP) i s proposed. The a pproach is based on the approximate solution improvement o b tained by the modified Romanovsky algorithm through the selected operation exchange between exec u tors. The comparative analysis with such approximate algorithms as the critical pat h technique (CPT) and the evolutional genetic algorithm (EGA) is carried out. The computational e xperiments at different problem parameter values are conducted. The combined application of the MRA a nd SPM for the mo d est dimension HAP solution permits to re ach rather high resource - precision figures in comparison to other approximate algorithms. However, at the higher problem dimensions, the SPM not even once improved th e sol utions obtained by the MRA, which most likely, is caused by the MRA high precision pr operties. That is why the a ppropriateness of the MRA and SPM application to the high dimension HAP sol u tion invites fur ther investigations.