A note on the online interval scheduling secretary problem

作者：Li, Bo; Wang, Chenhao^*; Zhang, Ruilong^*

来源：Operations Research Letters, 2022, 50(1): 72-75.

DOI：10.1016/j.orl.2021.12.007

• Secretary problem
• Interval scheduling
• Online algorithms

The interval scheduling secretary problem models the scenario when a number of job intervals arrive randomly and the decider needs to assign some of them to machines irrevocably such that all assigned job intervals can be processed by machines without overlap, with the goal of maximizing the social welfare. Im and Wang ((2011) [7]) designed an almost optimal logarithm-competitive online algorithm for the single-machine case. In this note, we extend this result to multiple heterogeneous machines. Our algorithm preserves the competitive ratio and is thus nearly optimal.