2025/02/19 by Danny Hermelin, Tomohiro Koana, Hermelin, Danny +3
Computer Science · Engineering · #Data Structures and Algorithms (cs.DS) #Distributed and Parallel Computing Systems #FOS: Computer and information sciences #Parallel Computing and Optimization Techniques #Scheduling and Optimization Algorithms
paper · pdf · doi:10.48550/arxiv.2502.13631
openalex publication_date 2025/02/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the classical problem of minimizing the total weighted completion time on a fixed set of m identical machines working in parallel, the Pm||∑ wjCj problem in the standard three field notation for scheduling problems. This problem is well known to be NP-hard, but only in the ordinary sense, and appears as one of the fundamental problems in any scheduling textbook. In particular, the problem served as a proof of concept for applying pseudo-polynomial time algorithms and approximation schemes to scheduling problems. The fastest known pseudo-polynomial time algorithm for Pm||∑ wjCj is the famous Lawler and Moore algorithm from the late 1960's which runs in O(Pm-1n) time, where P is the total processing time of all jobs in the input. After more than 50 years, we are the first to present an algorithm, alternative to that of Lawler and Moore, which is faster for certain range of the problem parameters (e.g., when their values are all O(1)).