Preemptive Scheduling of Equal-Length Jobs to Maximize Weighted Throughput
<|reference_start|>Preemptive Scheduling of Equal-Length Jobs to Maximize Weighted Throughput: 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_j;p_j=p;pmtn | sum w_j U_j). We provide an O(n^4)-time algorithm for this problem, improving the previous bound of O(n^{10}) by Baptiste.<|reference_end|>
@article{baptiste2002preemptive,
    title={Preemptive Scheduling of Equal-Length Jobs to Maximize Weighted
  Throughput},
    author={Philippe Baptiste, Marek Chrobak, Christoph Durr, Wojciech Jawor and
  Nodari Vakhania},
    journal={arXiv preprint arXiv:cs/0209033},
    year={2002},
    archivePrefix={arXiv},
    eprint={cs/0209033},
    primaryClass={cs.DS}
}