UMR2: A betterand more realistic scheduling algorithm for the Grid

Numerous studies have been targeting the problem of scheduling divisible workloads in distributed computing environments. The UMR (Uniform Multi-Round) algorithm stands out from all others by being the first close-form optimal scheduling algorithm. However, present algorithms, including the UMR, do not pay due attention to optimizing the set of workers that get selected to participate in processing workload chunks. In addition to the absence of a good resource selection policy, the UMR relies primarily in its computation on the CPU speed and overlooks the role of other key parameters such as network bandwidth. In this paper, we propose an extended version of UMR, called UMR2, that overcomes these limitations and adopts a worker selection policy that aims at minimizing the makespan. We, theoretically and experimentally, show that UMR2 is superior to UMR, specifically in a WAN computing platform such as the Grid.