Preemptive Multi-Machine Scheduling of Equal-Length Jobs to Minimize the Average Flow Time

2004/12/20 by Philippe Baptiste, Marek Chrobák, Baptiste, Philippe +5
Computer Science · Engineering · #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #Optimization and Packing Problems #Optimization and Search Problems #Scheduling and Optimization Algorithms

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

openalex publication_date 2004/12/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study the problem of preemptive scheduling of n equal-length jobs with given release times on m identical parallel machines. The objective is to minimize the average flow time. Recently, Brucker and Kravchenko proved that the optimal schedule can be computed in polynomial time by solving a linear program with O(n³) variables and constraints, followed by some substantial post-processing (where n is the number of jobs.) In this note we describe a simple linear program with only O(mn) variables and constraints. Our linear program produces directly the optimal schedule and does not require any post-processing.

Related

• The Complexity of Mean Flow Time Scheduling Problems with Release Times
• An efficient model for the preemptive single machine scheduling of\n equal-length jobs
• On Preemptive Scheduling of Unrelated Machines Using Linear Programming
• Preemptive Scheduling of Equal-Length Jobs to Maximize Weighted Throughput
• A Note on Scheduling Equal-Length Jobs to Maximize Throughput