Online Competitive Algorithms for Maximizing Weighted Throughput of Unit Jobs

摘要

We study an online scheduling problem for unit-length jobs, where each job is specified by its release time, deadline, and a nonnegative weight. The goal is to maximize the weighted throughput, that is the total weight of scheduled jobs. We first give a randomized algorithm RMIX with competitive ratio of e/(e — 1) ≈ 1.582. Then we consider s-bounded instances where the span of each job is at most s. We give a 1.25-competitive randomized algorithm for 2-bounded instances, and a deterministic algorithm EDF_α, whose competitive ratio on s-bounded instances is at most 2 — 2/s + o (1/s). For 3-bounded instances its ratio is φ ≈ 1.618, matching the lower bound. We also consider 2-uniform instances, where the span of each job is 2. We prove a lower bounds for randomized algorithms and deterministic memoryless algorithms. Finally, we consider the multiprocessor case and give an 1/(1 — (M/(M+1))~M)-competitive algorithm for M processors. We also show improved lower bounds for the general and 2-uniform cases.