A Note on “Orchestrating an Ensemble of MapReduce Jobs for Minimizing Their Makespan”

In paper [1], a scheduling model is considered for multiple MapReduce jobs. The goal in [1] is to design an automatic job scheduler that minimizes the makespan of such a set of MapReduce jobs. In this work, we find that there is a key assumption in [1] which leads to the violation of the conditions for classical Johnson´s algorithm and a suboptimal job scheduling for minimizing total makespan. By considering a better strategy and implementation, we can still meet the conditions of classical Johnson´s algorithm. Then we can still use Johnson´s algorithm for an optimal solution. As for BalancedPools algorithm proposed in paper [1], under our proposed new strategy, it is possible to solve it exactly in linear time, but not NP-hard as suggested in [1], the proof is provided. With the new strategy, results obtained in [1] need reevaluating.