Online busy time scheduling

Abstract

In this thesis we study the online busy time scheduling problem with infinite processors, where each job has a release time , a processing time and a deadline . The objective of busy time scheduling is to use multiple processors to schedule jobs concurrently in order to minimize the time a machine has to be processing jobs. We present an algorithm using machine learned advice that is able to achieve better results than a pure online algorithm. This algorithm will use a trust parameter, λ ∈ [0, 1], which allows us to control the tradeoff between consistency and robustness. Moreover, for purely online busy time problem, we introduce a lower bound of 2 for eager algorithms, disprove the currently claimed upper bound of 4, and present a general framework for analysis.