Data-Intensive Distributed Systems LaboratoryCS Seminar
Date: April 22nd, 2026
Time: 12:50pm
Room: SB111
Dr. Gruia Calinescu
Associate Professor
Computer Science Department
Illinois Institute of Technology
Talk Title
Online Flexible Busy Time Scheduling on Heterogeneous Machines
Talk Abstract
We study the online busy time scheduling model on heterogeneous machines. In our setting, jobs with uniform length arrive online with a deadline that becomes known to the algorithm at the job's arrival time. An algorithm has access to machines, each with different associated capacities and costs. The goal is to schedule jobs on machines by their deadline, so that the total cost incurred by the scheduling algorithm is minimized. While busy time scheduling has been well-studied, relatively little is known when machines are heterogeneous (i.e., have different costs and capacities), despite this natural theoretical generalization being the most practical model for clients using cloud computing services. We make significant progress in understanding this model by designing an 8-competitive algorithm for the problem on unit-length jobs and provide a lower bound of 2 on the competitive ratio. The lower bound is tight in the setting when jobs form non-nested intervals. Our 8-competitive algorithm generalizes to one with competitive ratio 8(2p-1)/p < 16 when all jobs have uniform length p.
Speaker Bio
Gruia Calinescu studied at the University of Bucharest, received his PhD in 1998 from the Georgia Institute of Technology, and has worked at Illinois Institute of Technology since 2000. He has held short-term positions at DIMACS, the University of Waterloo, the University of Wisconsin-Milwaukee, and Northwestern University, and has also visited the Max Planck Institute for Informatics and the Hausdorff Research Institute for Mathematics.
His best-known works (all improved or generalized by now) are on Multiway Cut, Zero Extension, and maximizing a monotone submodular function subject to a matroid constraint.