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) ) 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.
- Interval scheduling
- Online algorithms
- Secretary problem
ASJC Scopus subject areas
- Management Science and Operations Research
- Industrial and Manufacturing Engineering
- Applied Mathematics