Online Algorithms for Maximizing Weighted Throughput of Unit Jobs with Temperature Constraints

摘要

We consider a temperature-aware online deadline scheduling model. The objective is to schedule a number of unit jobs, with release dates, deadlines, weights and heat contributions, to maximize the weighted throughput subject to a temperature threshold. We give an optimal randomized algorithm and another resource-augmented constant-competitive randomized algorithm for the problem. We also give almost tight upper and lower bounds for the multiple processor case. Keywords: Online algorithms, scheduling, competitive analysis, temperature, resource augmentation.