Scheduling mixed-parallel application onto multicluster grid with background workloads

In a shared multicluster grid where mixed-parallel application workload and background workload co-exist, available processors for executing mixed-parallel application workload are those time-varying residual processors after reservations for background workloads. The grid scheduler aims to minimize the makespan of the mixed-parallel application and allocate processors to tasks belong to the mixed-parallel application with a coordinated manner, whereas advance reservation capability from Local Resource Manager(LRM) are fully exploited. We develop a heuristic algorithm MHEFT-RSV (ReSerVation) adapted from MHEFT (Mixed-Heterogeneous Earliest Finish Time) to multicluster grid with background workloads. Based on MHEFT-RSV, we further propose an exact branch-and-cut scheduling algorithm, which exploits the intertask precedence and resource constraints as much as possible, to accelerate the process of obtaining the schedule with minimized makespan. From the detailed simulation experiment we find that on average the exact branch-and-cut algorithm obtains shorter or equal makespan as MHEFT-RSV while MHEFT-RSV achieves better tradeoff between makespan and computation time.