Improving scheduling times for weighted tardy jobs on machines
Compressing the Lawler-Moore Dynamic Program for Weighted Tardy Jobs
Data Structures and Algorithms
Summary
Scheduling jobs on multiple machines so that the total penalty from late jobs is as small as possible can take a long time with classic methods. The authors found a way to speed up the calculation by focusing only on important parts of the problem. This improvement greatly reduces the time needed to find the best schedule, especially when there are many jobs or large deadlines. They also answered a long-standing question about how fast this can be done on a single machine.
What this means in practice
- •For manufacturing planners: Generate schedules minimizing penalties from late jobs more quickly when assigning tasks to multiple identical machines.
- •For data center schedulers: Optimize compute job schedules on identical servers with weighted importance and deadlines faster than previous methods.
A theory result. No direct application yet.
Authors
Klaus Jansen, Björn Schumacher, Corinna Wambsganz
Abstract
The classic scheduling problem of minimizing the total weight of tardy jobs ($P_m||\sum_jw_jU_j$) asks for a schedule of jobs each with a processing time, weight, and due date on a constant number of parallel identical machines. A job is late in a schedule if it completes after its due date, and an optimal schedule is one where the total weight of all late jobs is minimized. The classic dynamic programming algorithm of Lawler and Moore [Manag. Sci., 1969] solves this problem in $O(nd_{\max}^m)$ where $n$ is the number of jobs, $d_{\max}$ is the maximum due date of any job, and $m$ is the number of identical machines. We show that it is sufficient to only compute part of the dynamic program and obtain the running time $\tilde{O}(n + d_{\max}^{m + 1})$ where $\tilde{O}$ suppresses polylogarithmic factors. This affirmatively answers the open question posed by Hermelin, Molter, and Shabtay [INFORMS J. Comput., 2024], whether a running time of $\tilde{O}(n + d_{\max}^2)$ is possible on a single machine.