A Computer Science Department team received the George Nicholson Prize in Operations Research, which recognizes the best student-written paper at the 2022 Institute for Operations Research and the Management Sciences (INFORMS) annual meeting.
Ziv Scully, who completed his Ph.D. earlier this year, and Isaac Grosof, a Ph.D. candidate in the Computer Science Department (CSD), earned the award for their paper, "The Gittins Policy Is Nearly Optimal in the M/G/k Under Extremely General Conditions."
Under the mentorship of CSD professor Mor Harchol-Balter, Scully and Grosof studied how to schedule computational jobs in a queue to minimize average waiting time. In general, it is best to complete short jobs before long ones, but this is hard to do when there is uncertainty about how long each job will take. The Gittins policy is a scheduling strategy designed to cope with this uncertainty, and it is proven optimal for single-server queues that do one job at a time. But researchers didn't know whether the Gittins policy still applied in situations with multiple servers, since they are much harder to analyze. In their paper, Scully and Grosof showed that the Gittins policy does indeed perform well in multiserver queues, and introduced multiple queuing-theoretic techniques to perform their analysis.
The team's paper was among six finalists for the prize at this year's INFORMS conference, which was held Oct. 16–19 in Indianapolis.