Brief Announcement: Scheduling Jobs for Minimum Span: Improved Bounds and Learning-Augmented Algorithms
Mozhengfu Liu, Xueyan Tang · 2024
We study a flexible job scheduling problem. A set of jobs is released over time, each with a starting deadline and a processing length. The jobs are to be started by an online scheduler no later than their starting deadlines and will run nonpreemptively. The objective is to minimize the span -- the time duration for which at least one job is running. We present a new lower bound of 4 on the competitiveness of any online algorithm. We also establish tight competitiveness bounds in the learning-augmented setting of the problem.