CDS Invited Lecture: Randy Cogill, "Scheduling Strategies"
Wednesday, December 5, 2007
2168 A.V. Williams Building
301 405 6576
Control and Dynamical Systems Invited Lecture Series
Simple, effective scheduling strategies based on randomized load balancing
Department of Systems and Information Engineering
University of Virginia
P.S. Krishnaprasad and Vijay Gupta
Many scheduling problems in networks can be posed as standard optimization or stochastic control problems. However, computing and implementing optimal strategies often involves impractical levels of computation and communication.
Although optimal strategies are often not practically implementable, simple randomized strategies often work surprisingly well. In this talk, I'll discuss the problems of matching in peer-to-peer networks, multiprocessor scheduling, and packet switching. In each case, a simple randomized strategy performs comparably to an optimal strategy. I will also present several probability inequalities that are used in the analysis of these strategies.
Since fall 2007, Randy Cogill has been an Assistant Professor in the department of Systems and Information Engineering at University of Virginia. Prior to joining University of Virginia, he was a Ph.D. candidate in the department of Electrical Engineering at Stanford University, earning his Ph.D. in June 2007. His research interests fall into the broad categories of control, optimization, scheduling, randomized algorithms, and networks. He was a recipient of the Stanford Graduate Fellowship, and was co-awarded the best student paper award at the 2005 IEEE Conference on Decision and Control.