AGCO Seminar “Proportional Fairness for the Polytope Scheduling Problem”

Abstract:  Given 𝑛 jobs with known weights but unknown processing times, our goal is to minimize their total weighted completion time. It is well known that even ona single machine, no algorithm can be better tan 2-competitive, and this ratio is achieved by the (preemptive) Weighted Round-Robin rule. This initiated a line of work extending this positive result to more general scheduling settings involving parallel machines, release dates, or precedence constraints. Recently, the Polytope Scheduling Problem has received considerable attention. In this problem, there are finitely many resources, each with total availability 1, and processing a job 𝑗 at rate 𝑦_𝑗 requires 𝑏_{𝑑𝑗} 𝑦_𝑗 of resource 𝑑. In other words, at any time, the processing-rate vector must lie in the polytope {𝑦 ≥ 0 ∣ 𝐵𝑦 ≤ 1}. A natural generalization of the Weighted Round-Robin rule to this problem is the Proportional Fairness Algorithm.

We show that this algorithm achieves a competitive ratio of 2 on a large subclass of the Polytope Scheduling Problem that includes many classical scheduling problems, such as scheduling on unrelated machines or matroid scheduling. This subclass, which we call support-submodular, is characterized by the fact that, for all prices 𝛼_𝑗 ≥ 0 per unit of processing rate of job 𝑗, the maximum total price of a processing-rate vector for a subset 𝑈 of the jobs is a submodular function of 𝑈.

This is joint work with Alexander Lindermayr and Bart Zondervan.

Speakers: Sven Jäger, TU Berlin