Online Flexible Busy Time Scheduling on Heterogeneous Machines by Gruia Calinescu

Venue: Bharti501

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.

Joint work with Sami Davies, Samir Khuller, and Shirley Zhang

Bio: Gruia Calinescu has studied at University of Bucharest, received his PhD in 1998 from Georgia Institute of Technology and has worked since 2000 at Illinois Tech. He has held short term positions at DIMACS, U. Waterloo, U. Wisconsin Milwaukee, and Northwestern University, and also visited the Max Plank Institute for Informatics and the Hausdorff Research Institute for Mathematics.

His best works (all of them improved or generalized by now) are on Multiway Cut, Zero Extension, and Maximizing a Monotone Submodular Function Subject to a Matroid Constraint.