Escaping the makespan plateau: annealed power-mean guidance for task scheduling in heterogeneous cloud environments

Metaheuristic load balancers for cloud data centres are almost always driven by the makespan of the scheduling batch. We show that this objective is degenerate as a search signal. Because the makespan is a maximum, migrating a task away from the critical virtual machine merely promotes the runner-up, so the objective does not change and the search stalls. Measured over the full migration neighbourhood, 16.43 per cent of single-task migrations leave the makespan unchanged, and steepest descent under the makespan halts after only 2.8 accepted moves. We replace the makespan during the search by the normalised power mean of the machine completion times and anneal its exponent geometrically. The substitution is safe: the power mean is proved to bracket the makespan within a factor equal to the number of machines raised to the reciprocal of the exponent, so the terminal exponent controls the worst-case loss. Under this guidance the same descent sustains 162.5 moves and reaches a 6.83 per cent lower makespan. The resulting scheduler, APEX-BC, is a memetic bee colony in which each food source is refined by an incremental power-mean descent step. On an inconsistent expected-time-to-compute model with heterogeneous virtual machines, APEX-BC reduces the makespan by 5.81 per cent relative to the strongest heuristic and halves the gap to a linear-programming lower bound from 12.08 to 5.40 per cent, while artificial bee colony, particle swarm and genetic baselines at an identical evaluation budget remain statistically indistinguishable from their seed. We also report two negative results. Under the uniform speed model used by most of the literature the problem is degenerate: the longest-processing-time rule lies 0.65 per cent from the lower bound and no search method improves on it, which questions gains previously reported in that model. In an online rolling-horizon setting the makespan is arrival-bound and non-discriminating, and no metaheuristic, including ours, matches the Sufferage heuristic on response time. All results are simulation results.