A Min-Min average algorithm for scheduling transaction-intensive grid workflows

Abstract

Transaction-intensive grid workflows are attracting more and more attentions with the prosperity of e-business and e-government applications. They are workflows normally with a huge number of relatively simple concurrent instances, such as business transactions, whilst some of which may involve considerable communication overheads. However, there are almost no specific scheduling algorithms which deal with such workflows, and existing scheduling algorithms are not efficient enough for such a scenario if corresponding adjustments are not conducted. To address this problem, we propose a novel Min-Min-Average (MMA) algorithm for efficiently scheduling transaction-intensive grid workflows involving considerable communication overheads. The MMA algorithm is based on the popular Min-Min algorithm but uses a different strategy for transaction-intensive grid workflows with the capability of adapting to the change of network transmission speed automatically. The comparison based on the simulation performed on SwinDeW-G, our peer-to-peer based grid workflow environment, demonstrates that the MMA algorithm can improve the scheduling performance significantly over the original Min-Min algorithm when scheduling transaction-intensive grid workflows with considerable communication overheads involved.