Multiple-purpose solution to homogeneous allocation problems based on modified Romanovsky algorithm and selective-permutation algorithm

The problem on improving precision properties of the fast approximate algorithms without sacrifice of their resource properties is set. A multiple-purpose approach to the application of the modified Romanovsky algorithm (MRA) and the selective-permutation method (SPM) for solving homogeneous allocation problems (HAP) is proposed. The approach is based on the approximate solution improvement obtained by the modified Romanovsky algorithm through the selected operation exchange between executors. The comparative analysis with such approximate algorithms as the critical path technique (CPT) and the evolutional genetic algorithm (EGA) is carried out. The computational experiments at different problem parameter values are conducted. The combined application of the MRA and SPM for the modest dimension HAP solution permits to reach rather high resource-precision figures in comparison to other approximate algorithms. However, at the higher problem dimensions, the SPM not even once improved the solutions obtained by the MRA, which most likely, is caused by the MRA high precision properties. That is why the appropriateness of the MRA and SPM application to the high dimension HAP solution invites further investigations.