Research on Tasks Scheduling Algorithms for Dynamic and Uncertain Computing Grid Based on a+bi Connection Number of SPA

摘要

Task scheduling algorithms are key techniques intask management system of computing grid. Because of theuncertainty nature of a grid, traditional task schedulingalgorithms do not work well in an open, heterogeneous anddynamic grid environment of real world. In this paper, SetPair Analysis (SPA), a new soft computation method is usedto process the synthetic uncertainty in the task scheduling ofa computing grid. After introducing SPA and its application,the paper goes on to introduce the definition of connectionnumber to express the uncertain Expected Time to Computeof tasks, analysis operation properties and linear orderrelation suitable for computing grid scheduling. Threeonline uncertain dynamic scheduling algorithms,OUD_OLB, OUD_MET, OUD_MCT, and three batchuncertain dynamic scheduling algorithms BUD_Min-min,BUD_Min-max, BUD_Surferage, are presented for theuncertain dynamic computing grid. Theoretical analysisand experimental results illustrate that these algorithmsare capable of representing the dynamics and uncertaintyin a computing grid environment. These algorithms are thegeneralization of traditional grid scheduling algorithms, andthey possess high value in theory and application in a gridenvironment. Certainly it will be a new method to designtasks scheduling algorithm in uncertain computing gridenvironment.