A Note on Scheduling Equal-Length Jobs to Maximize Throughput
<|reference_start|>A Note on Scheduling Equal-Length Jobs to Maximize Throughput: We study the problem of scheduling equal-length jobs with release times and deadlines, where the objective is to maximize the number of completed jobs. Preemptions are not allowed. In Graham's notation, the problem is described as 1|r_j;p_j=p|\sum U_j. We give the following results: (1) We show that the often cited algorithm by Carlier from 1981 is not correct. (2) We give an algorithm for this problem with running time O(n^5).<|reference_end|>
@article{chrobak2004a,
    title={A Note on Scheduling Equal-Length Jobs to Maximize Throughput},
    author={Marek Chrobak, Christoph Durr, Wojciech Jawor, Lukasz Kowalik, Maciej
  Kurowski},
    journal={arXiv preprint arXiv:cs/0410046},
    year={2004},
    archivePrefix={arXiv},
    eprint={cs/0410046},
    primaryClass={cs.DS}
}