In this talk, a generalization of the Shortest Remaining Processing Time (SRPT) scheduling algorithm will be demonstrated as an effective approach for various scheduling problems to minimize total weighted flow time. SRPT can essentially be interpreted as a gradient descent approach based on an estimate of the remaining jobs' cost. In particular, it will be shown that gradient descent is effective when the residual estimate exhibits supermodularity. This supermodularity can be achieved when the scheduling constraints induce gross substitute valuations in a Walrasian Market. This approach will then be compared to proportional fairness, another general scheduling algorithm that's related to a Fisher Market.

Sungjin Im is an associate professor of Computer Science and Engineering at UC Santa Cruz. He earned his BS and MS in CSE from Seoul National University and his PhD in computer science from the University of Illinois at Urbana-Champaign. Prior to joining UC Santa Cruz, he was an associate professor at UC Merced. His expertise lies in designing and analyzing algorithms, with current research focused on enhancing traditional worst-case algorithms with machine learning predictions and developing adaptable meta-algorithms for scheduling and resource allocation. His broader research interests span a wide range of areas, including approximation algorithms, online algorithms, combinatorial optimization, scheduling algorithms, game theory, machine learning, and database theory.