Multi-Installment Scheduling for Large-Scale Workload Computation with Result Retrieval

Abstract Multi-installment scheduling (MIS) has made great strides in minimizing the makespan of large-scale workloads on distributed systems. By the makespan is meant the total time it takes for workload distribution, computation and result retrieval. However, existing studies have hardly taken result retrieval time into consideration due to an idealistic assumption that the amount of result generated after workload computation is so small that the retrieval time could be neglected. This unrealistic assumption may have a seriously negative effect on task-scheduling strategies especially for big-data-related applications nowadays. In view of this, this paper studies the MIS problem with result retrieval on heterogeneous distributed systems. We propose a new MIS model referred to as MIS-RR and solve three crucial issues: (1) we obtain, for the first time, a closed-form solution to an optimal load partition by strict mathematical derivation for this problem; (2) we get an optimal number of installments by designing a heuristic algorithm; (3) we obtain an optimal scheduling sequence of servers involved in computation by proposing an evolutionary algorithm. Experimental results clearly show that our proposed strategy can achieve the shortest makespan as well as the highest average CPU utilization and system utilization compared to existing scheduling strategies.