Efficient minimization of sum and differential costs on machines with job placement constraints

Abstract

We revisit the problem of assigning n jobs to m machines/servers. We study this problem under more general settings, which capture important aspects of applications that arise in networking and information systems. In particular, we consider jobs that have placement constraints and machines that are heterogeneous. The cost incurred at a machine is given by any general convex function on the number of jobs assigned to it. We aim to minimize the sum cost and the maximum differential cost. Through a network-flow equivalence transformation, we observe how these two objectives are fundamentally related, showing that sum-cost minimization implies maximum-differential-cost minimization. We propose an efficient algorithm termed Maximum Edge-Cost Cycle Cancelling (MEC3) to solve the sum-cost minimization problem with O(n2m2) time complexity. Furthermore, for applications where only the maximum differential cost is of concern, we further improve the efficiency of MEC3by proposing an early stop condition. We implement MEC3and two other algorithms from the literature. Using benchmark input instances, we show that MEC3has substantially lower run time than the other algorithms.