A Dynamic Programming Framework for Non-Preemptive Scheduling Problems on Multiple Machines [Extended Abstract]

In this paper, we consider a variety of scheduling prob-lems where n jobs with release times are to be sched-uled non-preemptively on a set of m identical ma-chines. The problems considered are machine minimiza-tion, (weighted) throughput maximization and min-sum objectives such as (weighted) flow time and (weighted) tardiness. We develop a novel quasi-polynomial time dynamic programming framework that gives O(1)-speed O(1)-approximation algorithms for the offline versions of ma-chine minimization and min-sum problems. For the weighted throughput problem, the framework gives a (1+ )-speed (1 − )-approximation algorithm. The generic DP is based on improving a naı̈ve exponential time DP by developing a sketching scheme that compactly and ac-curately approximates parameters used in the DP states. We show that the loss of information due to the sketch-ing scheme can be offset with limited resource augmen-tation.This framework is powerful and flexible, allowing us to apply it to this wide range of scheduling objectives and settings. We also provide new insight into the relative power of speed augmentation versus machine augmen-tation for non-preemptive scheduling problems; specifi-cally, we give new evidence for the power and importance of extra speed for some non-preemptive scheduling prob-lems. This novel DP framework leads to many new algo-rithms with improved results that solve many open prob-lems, albeit with quasi-polynomial running times. We highlight our results as follows. For the problems wit