Preemptive Scheduling of Equal-Length Jobs to Maximize Weighted Throughput
Baptiste, Philippe · Chrobak, Marek · Durr, Christoph · Jawor, Wojciech · Vakhania, Nodari
Original · EN
We study the problem of computing a preemptive schedule of equal-length jobs with given release times, deadlines and weights. Our goal is to maximize the weighted throughput, which is the total weight of completed jobs. In Graham's notation this problem is described as (1 | rⱼ;pⱼ=p;pmtn | sum wⱼ Uⱼ). We provide an O(n⁴)-time algorithm for this problem, improving the previous bound of O(n¹⁰) by Baptiste.
English translation
This paper has no Arabic translation yet. Be the first: it takes a few seconds, and the result is stored for every future reader.