Preemptive Scheduling of Equal-Length Jobs to Maximize Weighted Throughput

Simple item page
dc.creatorBaptiste, Philippe
dc.creatorChrobak, Marek
dc.creatorDurr, Christoph
dc.creatorJawor, Wojciech
dc.creatorVakhania, Nodari
dc.date2002-09-30
dc.date2003-03-11
dc.date.accessioned2026-07-07T03:18:54Z
dc.date.available2026-07-07T03:18:54Z
dc.descriptionWe 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.
dc.descriptiongained one author and lost one degree in the complexity
dc.identifierhttps://arxiv.org/abs/cs/0209033
dc.identifierhttp://arxiv.org/abs/cs/0209033
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/31303
dc.subjectData Structures and Algorithms
dc.subjectF.2.2
dc.titlePreemptive Scheduling of Equal-Length Jobs to Maximize Weighted Throughput
dc.typetext

Files

Collections

arXiv