Scheduling with setup costs and monotone penalties
Rohit Khandekar, Kirsten Hildrum, et al.
FSTTCS 2012
This paper provides a unified family of algorithms with performance guarantees for malleable scheduling problems on flows. A flow represents a set of jobs with precedence constraints. Each job has a speedup function that governs the rate at which work is done on the job as a function of the number of processors allocated to it. In our setting, each speedup function is linear up to some job-specific processor maximum. A key aspect of malleable scheduling is that the number of processors allocated to any job is allowed to vary with time. The overall objective is to minimize either the total cost (minisum) or the maximum cost (minimax) of the flows. Our approach handles a very general class of cost functions, and in particular provides the first constant-factor approximation algorithms for total and maximum weighted completion time. Our motivation for this work was scheduling in MapReduce, and we also provide experimental evaluations that show good practical performance.
Rohit Khandekar, Kirsten Hildrum, et al.
FSTTCS 2012
Anupam Gupta, Viswanath Nagarajan, et al.
Operations Research
Kevin S. Beyer, Vuk Ercegovac, et al.
VLDB
Nikhil Bansal, Uriel Feige, et al.
SIAM Journal on Computing