Abstract
This article considers a new variation of the online interval scheduling problem, which consists of scheduling C-benevolent jobs on multiple heterogeneous machines with different positive weights. The reward for completing a job assigned to a machine is given by the product of the job value and the machine weight. The objective of this scheduling problem is to maximize the total reward for completed jobs. Two classes of approximation algorithms are analyzed, Cooperative Greedy algorithms and Prioritized Greedy algorithms, with competitive ratios provided. We show that when the weight ratios between machines are small, the Cooperative Greedy algorithm outperforms the Prioritized Greedy algorithm. As the weight ratios increase, the Prioritized Greedy algorithm outperforms the Cooperative Greedy algorithm. Moreover, as the weight ratios approach infinity, the competitive ratio of the Prioritized Greedy algorithm approaches four. We also provide a lower bound of 3/2 and 9/7 for the competitive ratio of any deterministic algorithm for scheduling C-benevolent jobs on two and three machines with arbitrary weights, respectively.
Additional information
Funding
Notes on contributors
Ge Yu
Ge Yu is a research scientist at Amazon Inc. She has a B.Sc. in electronics engineering from Tsinghua University, China and a M.Sc. and Ph.D. in electrical and computer engineering from the University of Illinois at Urbana Champaign. Her research interests include machine learning algorithm designs, probability and random processes, optimization under uncertainty and real-time decision making. Her current work focuses on natural language understanding, language model development, and data efficiency for machine learning models.
Sheldon H. Jacobson
Sheldon H. Jacobson is a Founder Professor of Computer Science at the University of Illinois. He has a B.Sc. and M.Sc. (both in Mathematics) from McGill University, and a M.S. and Ph.D. (both in Operations Research) from Cornell University. From 2012–2014, he was on leave from the University of Illinois, serving as a Program Director at the National Science Foundation. His research interests span theory and practice, covering decision-making under uncertainty and optimization-based artificial intelligence, with applications in aviation security, public policy, public health, and sports. He has been recognized by numerous awards, including a Guggenheim Fellowship from the John Simon Guggenheim Memorial Foundation. He is a fellow of both IISE and INFORMS.