Preemptive Scheduling of Equal-Length Jobs to Maximize Weighted Throughput

2002/09/30 by Philippe Baptiste, Marek Chrobak, Baptiste, Philippe +7
Computer Science · #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #cs.DS

paper · pdf · doi:10.48550/arxiv.cs/0209033

gained one author and lost one degree in the complexity

arxiv created 2003/03/11 · arxiv updated 2009/11/30

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, 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⁴)-time algorithm for this problem, improving the previous bound of O(n¹⁰) by Baptiste.

Related

• A Note on Scheduling Equal-Length Jobs to Maximize Throughput
• An efficient model for the preemptive single machine scheduling of\n equal-length jobs
• Preemptive Multi-Machine Scheduling of Equal-Length Jobs to Minimize the Average Flow Time
• Throughput Maximization in the Speed-Scaling Setting
• A 2.542-Approximation for Precedence Constrained Single Machine\n Scheduling with Release Dates and Total Weighted Completion Time Objective