MULTICRITERIA SCHEDULING HEURISTICS FOR GRIDRPC SYSTEMS

摘要

In this paper, we address the problem of dynamically scheduling independent tasks and/or application task graphs on a GridRPC environment. Resources are assumed to compute submitted jobs within the time-share model. We present a non-intrusive predictive module, the historical trace manager (HTM), which is able to give the completion date of each task in the system. Four heuristics relying on its estimations are proposed and compared to the well-known minimum completion time (MCT) algorithm. We first analyze the accuracy of the HTM. Then we show with an extensive simulation study, and with numerous scenarios of execution performed on a real-world platform, that our heuristics outperform MCT on several metrics among which are the makespan and the response time.