[CS Colloquium] Sungjin Im, Competitive Scheduling from Competitive Equilibria

Scheduling jobs is a fundamental problem that arises in numerous forms and in various situations. In this talk, we introduce and study a general scheduling problem that we term the Packing Scheduling problem (PSP). In this problem, jobs can have different arrival times and sizes, and the rates at which a scheduler can process jobs are subject to arbitrary packing constraints. The PSP framework captures a variety of scheduling problems, including the classical problems of heterogeneous machines scheduling, broadcast scheduling, and scheduling jobs of different parallelizability. It also captures scheduling constraints arising in diverse modern environments ranging from individual computer architectures to data centers. More concretely, PSP models multidimensional resource requirements and parallelizability, as well as network bandwidth requirements found in data center scheduling. We design non-clairvoyant online algorithms for PSP and its special cases, meaning that they make scheduling decisions without knowing the future jobs, or even outstanding jobs sizes until their completion. Interestingly, our algorithms are inspired by ideas developed in game theory, which at first sight seems to have no connection to online scheduling.