Uncertainty Seminar

Makespan Minimization via Posted Prices

We consider job scheduling settings, with multiple machines, where jobs arrive online and choose a machine selfishly so as to minimize their cost. Our objective is the classic makespan minimization objective, which corresponds to the completion time of the last job to complete.

We set dynamic prices determined by the past (assuming nothing about upcoming events). We give tight results for the competitive ratios that can be achieved by dynamic and static pricing schemes in the various settings. Our main result is a dynamic pricing scheme for related machines that gives a constant competitive ratio, essentially matching the competitive ratio of online algorithms for this setting. In contrast, dynamic pricing gives poor performance in the context of unrelated machines.

Joint work with Michal Feldman and Alan Roytman.