Task assignment for scheduling jobs and resources in parallel distributed systems

Abstract

In managing multiprocessing of parallel distributed systems the central issue is the scheduling of jobs and resources in the optimum way. This paper describes a  new approach for  the solution of this problem. The proposed approach allows us to create an algorithm that  adapts to any kind of systems constraints and the optimization criterion as well. The key idea in our approach  is to divide the process of the scheduling into preliminary analyzing initial data and finding  the solution with the support of the results of this analysis. This algorithm for analyzing is built on the principle of step by step  forming  and is called Adaptive Multi-analyzing Algorithm (AMA). The proposed algorithm is based on our development of the Malgrange method for task assignment. The results of our investigation are presented in  a system  of theorems  which are shown in this paper. The time complexity of the proposed algorithm varies from O[N log(N)+E] to less time, depending on the characters of the initial data of the systems analyzed. The adding of this algorithm based on  our theoretical system for analyzing initial  data allow us to decrease the  whole  time  complexity for  finding the  schedule of jobs and resources. These advances of AMA are shown theoretically by describing the analyzing process and through the results of experiments in the simulation mutilprocessing systems  as well.