|
|||||
|
|
Preemptive scheduling of equal-length jobs to maximize weighted throughput |
|
| Authors: | Philippe Baptiste,Christoph Dü rr,Wojciech Jawor,Nodari Vakhania |
| Affiliation: | a CNRS LIX, Ecole Polytechnique, Palaiseau 91128, France b Department of Computer Science, University of California, Riverside, CA 92521, USA c Laboratoire de Recherche en Informatique, Université Paris-Sud, Orsau 91405, France d Facultad de Ciencias, Universidad Autonoma del Estado de Morelos, Cuernavaca 62251, Morelos, Mexico |
| Abstract: | 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. In Graham's notation this problem is described as  . We provide an O(n4)-time algorithm, improving the previous bound of O(n10). |
| Keywords: | Single machine preemptive scheduling Weighted throughput |
| 本文献已被 ScienceDirect 等数据库收录！ | |