Performance analysis of work-conserving schedulers for minimizing total flow-time with phase precedence

We consider the problem of minimizing the total flow-time of multiple jobs in a pool of multiple homogeneous machines, where the jobs arrive over time and have to be served with phase precedence. This is a common occurrence in job scheduling for the increasingly popular data center oriented systems, where jobs need to be processed through Map and Reduce procedures before leaving the system. For this problem, one can construct an arrival pattern such that no scheduler can achieve a constant competitive ratio. However, what we find is that by using a slightly weaker performance metric, which we call the efficiency ratio, we can provide bounds on the performance. We say that a scheduler achieves an efficiency ratio of γ when the flow-time incurred by that scheduler divided by the minimum flow-time achieved over all possible schedulers is less than or equal to γ almost surely, when the time slots or job arrivals go to infinity. Under some weak assumptions, we show a surprising property that all work-conserving schedulers for the flow-time problem with phase precedence have a constant efficiency ratio in both preemptive and non-preemptive scenarios. We provide numerical results to support our analysis.