Task assignment for scheduling jobs and resources in parallel distributed systems - Hanh, Pham Hong; Simonenko, Valery (Journal of Computer Science and Cybernetics, 2016)
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.