the parallel program
task allocation problem
an abstract resource
M-Dimensional Vector Packing Problem
In the article «Task allocation problem in parallel programs of conducting a database of space debris elements» a task allocation problem is discussed. The major factors on which the decision process for this problem depends are considered. For formal representation of these factors the concept of an Abstract resource is defined. The concept of an abstract resource plays a key role in construction of model of planning procedure. The model also includes a parameter of current utilization of computing system U, and restrictions on this parameter, which determine minimal and maximal values of utilization of the computing system. The equivalence of the examined task allocation problem and the problem of integer programming for m-Dimensional Vector Packing Problem is shown on the basis of the entered model. This equivalence entails NP-completeness of task allocation problem. For the decision of the problem it is proposed to use heuristic algorithms. For simplification of algorithm the special procedure «the reinterpretaion» is offered . One-passage heuristic algorithm of task allocation is developed. This algorithm provides uniform distribution of processes and minimizes number of computing nodes. In the article the analysis of other works devoted to the given theme is carried out. In the conclusion of the article the brief review of the received results is given and the further directions of researches are defined.