betaFeedback

WorksComputer Science

Compressing the Lawler-Moore Dynamic Program for Weighted Tardy Jobs

Abstract

The classic scheduling problem of minimizing the total weight of tardy jobs (Pm∣∣∑jwjUjP_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(ndmax⁡m)O(nd_{\max}^m) where nn is the number of jobs, dmax⁡d_{\max} is the maximum due date of any job, and mm 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 O~(n+dmax⁡m+1)\tilde{O}(n + d_{\max}^{m + 1}) where O~\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 O~(n+dmax⁡2)\tilde{O}(n + d_{\max}^2) is possible on a single machine.

Introduction

Minimizing the total weight of tardy jobs is a classic scheduling problem. We are given nn jobs with processing times pj∈Z≥1p_j \in\mathbb{Z}_{\ge1}, weights wj∈Z≥1w_j \in\mathbb{Z}_{\ge1}, and due dates dj∈Z≥1d_j \in\mathbb{Z}_{\ge1} such that pj≤djp_j \le d_j as well as mm parallel identical machines. A schedule τ\tau for this problem is an assignment of jobs to machines together with an order of execution on every machine. Let Cj(τ)C_j(\tau) be the completion time of job jj in schedule τ\tau. A job jj is on time in τ\tau if Cj(τ)≤djC_j(\tau) \le d_j and late otherwise. We set Uj(τ)=0U_j(\tau) = 0 if jj is on time and Uj(τ)=1U_j(\tau) = 1 if it is late. The goal is to find a schedule τ\tau that minimizes the total weight of late jobs

∑j=1nwjUj(τ).\sum_{j=1}^{n} w_jU_j(\tau).

On a single machine the problem is denoted by 1∣∣∑jwjUj1||\sum_j w_jU_j and on m∈O(1)m \in O(1) identical parallel machines by Pm∣∣∑jwjUjP_m||\sum_j w_jU_j using the three-field notation by Graham, Lawler, Lenstra, and Rinnooy Kan [10].

Even on a single machine the problem is NP-hard as it is one of the original 21 problems shown to be NP-hard by Karp [16]. For an exact solution it is equivalent to maximize the weight of the on-time jobs instead. Thus, 1∣∣∑jwjUj1||\sum_j w_jU_j is closely related to the knapsack problem as the problems are the same in the case where all jobs share the same due date.

The classic algorithm for this problem on a single machine is the dynamic programming algorithm due to Lawler and Moore [19] with running time O(n⋅dmax⁡)O(n \cdot d_{\max}) where dmax⁡d_{\max} is the maximum due date of any job. It is similar to the algorithm by Bellman [3] for knapsack that has a running time of O(n⋅t)O(n \cdot t) where tt is the capacity of the knapsack. Both algorithms follow the same principle: For a job index j∈[n]j \in[n] and a point in time t∈[dmax⁡]t \in[d_{\max}] the dynamic program stores the largest possible weight of on-time jobs with total processing time tt while only using jobs from the set {1,…,j}\{1,\ldots,j\}. In contrast to Bellman’s algorithm, the algorithm still needs to handle the different due dates. To cope with these, the jobs are ordered non-decreasingly by due dates before filling the dynamic program table. This is sufficient since there is always an optimal solution where the on-time jobs are ordered non-decreasingly according to their due dates, also known as the earliest-due-date (EDD) order. The algorithm is depicted in Algorithm 1. It generalizes to Pm∣∣∑jwjUjP_m||\sum_j w_jU_j with running time Om(n⋅dmax⁡m)O_m(n \cdot d_{\max}^m) where OmO_m suppresses multiplicative factors depending only on mm.

We modify the algorithm by Lawler and Moore by restricting the range of values tt may take in line 3 of Algorithm 1 and updating the same row in every iteration. To justify this we give all jobs a priority based on their weight and their index. We show that there is always a canonical optimal schedule that uses high-priority jobs. Combining this with the insight that a schedule may contain at most ⌊dmax⁡p⌋\left\lfloor\frac{d_{\max}}{p}\right\rfloor on-time jobs with processing time pp, we can restrict the necessary updates. Generalizing this to multiple machines yields the following result.

Theorem 1.1. Given an instance of Pm∣∣∑jwjUjP_m||\sum_j w_jU_j, the optimal value can be calculated in O~m(n+dmax⁡m+1)\widetilde{O}_m(n+d_{\max}^{m+1}) time and Om(n+dmax⁡m)O_m(n+d_{\max}^m) space. Using additional O~m(dmax⁡m+1)\widetilde{O}_m(d_{\max}^{m+1}) space, we can construct an optimal schedule in the same time.

This presents an improvement over the Lawler-Moore algorithm when nn is larger than dmax⁡d_{\max} up to logarithmic factors. Together, we obtain a running time of O~m(n+dmax⁡mmin⁡{dmax⁡,n})\widetilde{O}_m(n+d_{\max}^m\min\{d_{\max},n\}). We also positively answer the open question posed by Hermelin, Molter, and Shabtay [13], whether there exists an algorithm for 1∣∣∑jwjUj1||\sum_j w_jU_j with running time O~(n+dmax⁡2)\widetilde{O}(n+d_{\max}^2). Moreover, this result is an extension of the folklore reduction for knapsack to reduce the number of items to O~(t)\widetilde{O}(t) mentioned in Remark 1.5 of [20], which also yields an O~(n+t2)\widetilde{O}(n+t^2) algorithm for knapsack. The extension is not straightforward since jobs may have distinct due dates, which complicates a simple exchange argument. We cope with this difficulty by introducing a priority order on the jobs and considering the highest-priority jobs that may be on time for every point in time.

Algorithm 1 Algorithm by Lawler and Moore for 1∣∣∑jwjUj1||\sum_j w_jU_j

Require: nn jobs each with (pj,dj,wj)(p_j,d_j,w_j)

Ensure: Maximum total weight of on-time jobs

  1. Initialize fj[t]←−∞f_j[t] \leftarrow-\infty for every j∈{0,…,n}j \in\{0,\ldots,n\} and t∈{0,…,dmax⁡}t \in\{0,\ldots,d_{\max}\} and f0[0]←0f_0[0] \leftarrow0

  2. for j=1,…,nj=1,\ldots,n in non-decreasing order by due dates do

  3.     for t=0,1,…,dmax⁡t=0,1,\ldots,d_{\max} do

  4.         if pj≤t≤djp_j \leq t \leq d_j then

  5.             fj[t]←max⁡{fj−1[t],fj−1[t−pj]+wj}f_j[t] \leftarrow\max\{f_{j-1}[t],f_{j-1}[t-p_j]+w_j\}

  6.         else

  7.             fj[t]←fj−1[t]f_j[t] \leftarrow f_{j-1}[t]

  8. return max⁡t∈{0,…,dmax⁡}fn[t]\max_{t\in\{0,\ldots,d_{\max}\}} f_n[t]

Related Work

The dependency on dmax⁡d_{\max} in the running time of the Lawler-Moore algorithm for 1∣∣∑jwjUj1||\sum_j w_jU_j cannot be improved without incurring an exponential dependence on nn: Assuming the SETH, for any ε>0\varepsilon> 0 there is a δ>0\delta> 0 such that there is no algorithm with running time O(2δn(dmax⁡+P)1−ε)O(2^{\delta n}(d_{\max}+P)^{1-\varepsilon}) where PP is the sum of all processing times [15]. Under the (min⁡,+)(\min,+)-convolution hypothesis there is also no O~((n+dmax⁡)2−ε)\widetilde{O}((n+d_{\max})^{2-\varepsilon}) algorithm [7]. Hence, on a single machine the quadratic dependence on dmax⁡d_{\max} in Theorem 1.1 is necessary in combination with the near-linear dependence on nn. On multiple machines we do not know whether the m+1m+1 exponent is optimal. The running time of the Lawler-Moore algorithm can also be stated as O(n⋅Pm)O(n\cdot P^m). When the maximum processing time pmax⁡p_{\max} is smaller than P\sqrt{P} and m≥2m\geq2, Bringmann, Hermelin, Koana, and Shabtay [BHKS26] showed that the running time can be improved to O(n⋅P⋅pmax⁡2m−2)≤O(n2⋅pmax⁡2m−1)O(n\cdot P\cdot p_{\max}^{2m-2})\leq O(n^2\cdot p_{\max}^{2m-1}).

Under the ∀∃\forall\exists-SETH, for all ε>0\varepsilon> 0, no algorithm with running time O~(n+pmax⁡⋅n1−ε)\widetilde{O}(n+p_{\max}\cdot n^{1-\varepsilon}) is possible for 1∣∣∑jwjUj1||\sum_j w_jU_j [1]. Their reductions also rule out any running time of O~(n+pmax⁡c)\widetilde{O}(n+p_{\max}^c) for any constant c>0c>0 as noted in [BHKS26] and thus we cannot hope for a running time of O~(n+pmax⁡2)\widetilde{O}(n+p_{\max}^2), which is possible for knapsack [14, 5]. Also in the special case of minimizing the tardy processing time on a single machine (1∣∣∑jpjUj1||\sum_j p_jU_j), where wj=pjw_j=p_j, a running time of the form O~(n+pmax⁡O(1))\widetilde{O}(n+p_{\max}^{O(1)}) is possible. In particular, Klein, Polak, and Rohwedder [17] developed an O~(n+pmax⁡3)\widetilde{O}(n+p_{\max}^3) algorithm.

Hermelin, Molter, and Shabtay [13] showed that 1∣∣∑jwjUj1||\sum_j w_jU_j can be solved in O~(n+d#dmax⁡2)\widetilde{O}(n+d_{\#}d_{\max}^2) and O~(d#n+d#dmax⁡pmax⁡)\widetilde{O}(d_{\#}n+d_{\#}d_{\max}p_{\max}) where d#d_{\#} is the number of distinct due dates and pmax⁡p_{\max} is the maximum processing time. The second summand in both of these running times can be bounded by dmax⁡3d_{\max}^3, which leaves the gap that this paper closes.

For the special case Pm∣∣∑jpjUjP_m||\sum_j p_jU_j improvements over the Lawler-Moore algorithm are known: the problem can be solved in O~(Pm)\widetilde{O}(P^m) [9] and O(n⋅pmax⁡O(m))O(n\cdot p_{\max}^{O(m)}) [17]. A recent lower bound shows that for any ε>0\varepsilon> 0 there is no 2o(m)2^{o(m)}-time algorithm for Pm∣∣∑jpjUjP_m||\sum_j p_jU_j, assuming the SETH [2].

Due to its connection to knapsack, 1∣∣∑jwjUj1||\sum_j w_jU_j is NP-hard even when d#=1d_{\#}=1 where d#d_{\#} is the number of different due dates. Parameterized solely by the number of different processing times p#p_{\#} or the number of different weights w#w_{\#}, the problem is W[1]-hard [11] but in XP [12]. In contrast, the problem is FPT parameterized by any two of {d#,p#,w#}\{d_{\#},p_{\#},w_{\#}\} [12].

The fastest known exponential algorithms for this are O∗(212n)O^*(2^{\frac{1}{2}n}) [18] and O∗(2n)O^*(2^n) [8] for 1∣∣∑jwjUj1||\sum_j w_jU_j and P∣∣∑jwjUjP||\sum_j w_jU_j (where mm is part of the input), respectively. O∗O^* suppresses polynomial factors.

Organization of the Paper First we establish the existence of an optimal canonical schedule in § 2. Then, in § 3 we show how to use the canonical structure algorithmically. We conclude with an overview of future work in § 4.

Structure of an Optimal Schedule

We assume that the jobs are given in EDD order, i.e., d1≤⋯≤dnd_1\leq\cdots\leq d_n. For our application this is not a restriction as such an order can be calculated in O(nlog⁡n)O(n\log n) or O(n+dmax⁡)O(n+d_{\max}) time using standard sorting algorithms. We define [k]:={1,2,…,k}[k]:=\{1,2,\ldots,k\} for k∈Nk\in\mathbb{N}.

Notice that on a single machine at most ⌊dmax⁡p⌋\left\lfloor\frac{d_{\max}}{p}\right\rfloor jobs with processing time pp may be on time. Thus, in every schedule at most κp:=m⌊dmax⁡p⌋\kappa_p:=m\left\lfloor\frac{d_{\max}}{p}\right\rfloor jobs with processing time pp are on time. In contrast to knapsack we cannot simply restrict the set of jobs with processing time pp to the κp\kappa_p most profitable ones since not all jobs share the same due date. To avoid violating the due dates we consider the most profitable jobs for every point in time. By fixing a global order we can show that every job may only be considered in a certain time interval. Further, we prove that the total length of these intervals is bounded by O~m(dmax⁡2)\widetilde{O}_m(d_{\max}^2).

We start by defining a total order >w>_w for jobs based on the weights of the jobs; ties are broken based on the index. More precisely, the jobs are ordered non-increasingly and lexicographically by (wj,j)(w_j,j). Let Tp,t:={j∈[n]:pj=p,dj≥t}T_{p,t}:=\{j\in[n]:p_j=p,d_j\geq t\} be the set of jobs with processing time pp that may be on time when finishing at t∈{p,…,dmax⁡}t\in\{p,\ldots,d_{\max}\}. We restrict the set Tp,tT_{p,t} to the min⁡{κp,∣Tp,t∣}\min\{\kappa_p,|T_{p,t}|\} most profitable jobs according to >w>_w and denote this set of jobs by T‾p,t\overline{T}_{p,t}. For a job j∈[n]j\in[n], we define C‾j:={t∈{pj,…,dmax⁡}:j∈T‾pj,t}\overline{C}_j:=\{t\in\{p_j,\ldots,d_{\max}\}:j\in\overline{T}_{p_j,t}\} to be the set of canonical completion times of the job. Clearly, we have

T‾p,p⊇T‾p,p+1⊇⋯⊇T‾p,dmax⁡(1)\overline{T}_{p,p}\supseteq\overline{T}_{p,p+1}\supseteq\cdots\supseteq\overline{T}_{p,d_{\max}} \tag*{(1)}

for every p∈[dmax⁡]p\in[d_{\max}]. This directly implies that every C‾j\overline{C}_j is an interval. The structure of the intervals is depicted in Figure 1.

Depiction of the overlapping intervals

Figure 1. Depiction of the overlapping intervals C‾j\overline{C}_j for the jobs with processing time pp. The interval of job jj starts at aj=dj′+1a_j=d_{j'}+1 because job j′j' is more profitable according to >w>_w and “pushes” jj out of T‾p,dj′\overline{T}_{p,d_{j'}}, since there are already κp\kappa_p overlapping intervals. The figure also illustrates why the total length of the intervals is bounded by dmax⁡⋅κpd_{\max}\cdot\kappa_p.

Lemma 2.1. For every j∈[n]j\in[n], there is an aj∈{pj,pj+1,…,dj+1}a_j\in\{p_j,p_j+1,\ldots,d_j+1\} such that C‾j={aj,aj+1,…,dj}\overline{C}_j=\{a_j,a_j+1,\ldots,d_j\}. If C‾j=∅\overline{C}_j=\emptyset, aj=dj+1a_j=d_j+1.

Proof. Let j∈[n]j\in[n]. For every t∈{pj,…,dj−1}t\in\{p_j,\ldots,d_j-1\}, we have that j∈T‾pj,tj\in\overline{T}_{p_j,t} implies j∈T‾pj,t+1j\in\overline{T}_{p_j,t+1} by Equation (1). Thus, let aja_j be the smallest point in time such that j∈T‾pj,ajj\in\overline{T}_{p_j,a_j}. By the above property we have that j∈T‾pj,tj\in\overline{T}_{p_j,t} for all t∈{aj,aj+1,…,dj}t\in\{a_j,a_j+1,\ldots,d_j\}. If no such aja_j exists, i.e., C‾j=∅\overline{C}_j=\emptyset, we set aj=dj+1a_j=d_j+1 as C‾j\overline{C}_j is the empty set.

Theorem 2.2. There exists an optimal schedule τ\tau such that every on-time job completes at a canonical completion time, i.e., Uj=0U_j=0 implies that Cj(τ)∈C‾jC_j(\tau)\in\overline{C}_j for every j∈[n]j\in[n]. Furthermore, all on-time jobs are ordered in the EDD order given by the indices.

Proof. Take an optimal schedule that schedules the on-time jobs in index EDD order before it schedules the late jobs on every machine. Choose such an optimal schedule τ\tau that also maximizes the sum of on-time indices. Thus, τ\tau lexicographically maximizes

∑j∈[n]Uj(τ)=0(wj,j).\sum_{\substack{j\in[n]\\ U_j(\tau)=0}}(w_j,j).

Towards a proof by contradiction, suppose that there exists a j∈[n]j\in[n] such that Uj(τ)=0U_j(\tau)=0 and Cj(τ)∉Cj‾C_j(\tau)\notin\overline{C_j}. Then there exists a job j′∈T‾pj,Cj(τ)j'\in\overline{T}_{p_j,C_j(\tau)} with Uj′(τ)=1U_{j'}(\tau)=1 since ∣T‾pj,Cj(τ)∣=κpj|\overline{T}_{p_j,C_j(\tau)}|=\kappa_{p_j} and at most κpj\kappa_{p_j} jobs with processing time pjp_j are on time in τ\tau, including jj. We swap j′j' and jj in τ\tau and restore the EDD order of the on-time jobs. Restoring the EDD order cannot cause an on-time job to be late as pj=pj′p_j=p_{j'} and dj≤dj′d_j\le d_{j'}. Since j′>wjj'>_w j, this either increases the weight of the on-time jobs in the schedule or leaves the weight unchanged and increases the sum of indices; both cases yield a contradiction to the choice of τ\tau. Hence, Cj(τ)∈Cj‾C_j(\tau)\in\overline{C_j} for all j∈[n]j\in[n] with Uj(τ)=0U_j(\tau)=0.

Next we bound the total length of the canonical intervals.

Lemma 2.3. It holds that

∑j=1n∣Cj‾∣=∑p=1dmax⁡∑t=pdmax⁡∣T‾p,t∣≤mdmax⁡2(1+ln⁡dmax⁡)≤O~m(dmax⁡2).\sum_{j=1}^{n}|\overline{C_j}|=\sum_{p=1}^{d_{\max}}\sum_{t=p}^{d_{\max}}|\overline{T}_{p,t}|\le md_{\max}^{2}(1+\ln d_{\max})\le\widetilde{O}_m(d_{\max}^{2}).

Proof. Let p∈[dmax⁡]p\in[d_{\max}]. We have

∑j∈[n]pj=p∣Cj‾∣=∑t=pdmax⁡∣T‾p,t∣\sum_{\substack{j\in[n]\\p_j=p}}|\overline{C_j}|=\sum_{t=p}^{d_{\max}}|\overline{T}_{p,t}|

by the definition of the Cj‾\overline{C_j}. Summing over all processing times shows the first equality. Further, we have ∑t=pdmax⁡∣T‾p,t∣≤dmax⁡κp=dmax⁡m⌊dmax⁡p⌋≤mdmax⁡21p\sum_{t=p}^{d_{\max}}|\overline{T}_{p,t}|\le d_{\max}\kappa_p=d_{\max}m\left\lfloor\frac{d_{\max}}{p}\right\rfloor\le md_{\max}^{2}\frac{1}{p}. Thus,

∑p=1dmax⁡∑t=pdmax⁡∣T‾p,t∣≤∑p=1dmax⁡mdmax⁡21p=mdmax⁡2∑p=1dmax⁡1p≤mdmax⁡2(1+ln⁡dmax⁡)\sum_{p=1}^{d_{\max}}\sum_{t=p}^{d_{\max}}|\overline{T}_{p,t}|\le\sum_{p=1}^{d_{\max}}md_{\max}^{2}\frac{1}{p}=md_{\max}^{2}\sum_{p=1}^{d_{\max}}\frac{1}{p}\le md_{\max}^{2}(1+\ln d_{\max})

where the last inequality holds because the kkth harmonic number is at most 1+ln⁡k1+\ln k (cf. Appendix A.2 in [6]).

Improved Algorithm

In this section, we prove Theorem 1.1 and present our algorithm, which is an improved version of Algorithm 1 by Lawler and Moore. The algorithm is a dynamic program that iterates over all jobs and computes the maximum weight of an EDD schedule that uses only the jobs considered up to that point and in which the on-time jobs complete at canonical completion times. The maximum weight of such an EDD schedule for all jobs corresponds to an optimal solution for the Pm∣∣∑jwjUjP_m||\sum_j w_jU_j problem. In Section 3.1 we show how to obtain the canonical completion times; in Section 3.2 we present our algorithm and in Section 3.3 we prove how to construct an optimal solution to Pm∣∣∑jwjUjP_m||\sum_j w_jU_j by using our algorithm.

Computation of the Intervals Cj‾\overline{C_j}

The values aja_j, j∈[n]j\in[n], defining the intervals Cj‾\overline{C_j} in Lemma 2.1 can be calculated by iterating over the jobs in reverse EDD order and using a heap to keep track of the κp\kappa_p most profitable items according to >w>_w for every processing time pp. More precisely, we first build lists Gp={j∈[n]:pj=p}G_p=\{j\in[n]:p_j=p\} of all jobs with the same processing time in increasing EDD index order. For each of those lists, we do the following two steps: Initialize an empty min-heap where we store jobs with the pair (wj,j)(w_j,j) as their key and sort them according to >w>_w. Now we iterate over the jobs in reversed order. For job jj we insert (wj,j)(w_j,j) into the heap. If the number of heap entries exceeds κp=m⌊dmax⁡p⌋\kappa_p = m\left\lfloor\frac{d_{\max}}{p}\right\rfloor, we remove the job with the smallest key. Let this job be hh. Note that we may have h=jh=j. We set ah′=dj+1a'_h=d_j+1. After iterating over all jobs, we set aj′=pa'_j=p for all jobs still in the heap.

Lemma 3.1. The values aj′a'_j computed by the procedure above are the correct values aja_j for all j∈[n]j \in[n].

Proof. Let h∈[n]h \in[n]. We show ah′=aha'_h=a_h by showing the inequality in both directions.

ah′≤aha'_h \le a_h If hh is never removed from the heap, we have ah′=ph≤aha'_h=p_h \le a_h and we are done. Now assume that hh was removed. Then there exists a job jj whose addition to the heap caused the removal of hh. When jj is added, all jobs currently in the heap have a due date of at least djd_j and a higher priority than hh. Therefore h∉T‾ph,djh \notin\overline{T}_{p_h,d_j} and ah′=dj+1≤aha'_h=d_j+1\le a_h.

ah≤ah′a_h \le a'_h If ah=pha_h=p_h, the job hh is one of the κph\kappa_{p_h} most profitable jobs according to >w>_w and thus still in the heap after all jobs are processed, which implies ah′=pha'_h=p_h. Now assume that ph<ahp_h<a_h. After all jobs in T‾ph,ah−1\overline{T}_{p_h,a_h-1} are processed, hh cannot be in the min-heap anymore since T‾ph,ah−1\overline{T}_{p_h,a_h-1} has κph\kappa_{p_h} entries and does not contain hh, which implies that hh was removed before jobs with due dates smaller than ah−1a_h-1 are considered. Therefore, ah′>ah−1a'_h>a_h-1, which means ah′≥aha'_h\ge a_h.

Lemma 3.2. The values a1,…,ana_1,\ldots,a_n for the intervals C‾1,…,C‾n\overline{C}_1,\ldots,\overline{C}_n can be computed in O(nlog⁡n)O(n\log n) time using O(n)O(n) space.

Proof. By Lemma 3.1 the procedure above computes the values a1,…,ana_1,\ldots,a_n for the intervals C‾1,…,C‾n\overline{C}_1,\ldots,\overline{C}_n. We analyze its running time and space consumption. We can build the lists GpG_p in O(n)O(n) time using O(n)O(n) space. For each job, we have at most one insertion and one deletion operation on the min-heap. The min-heap has size at most nn. Therefore, these operations can be done in O(nlog⁡n)O(n\log n) time and O(n)O(n) space (cf. [6]). All update operations for the values aja_j, j∈[n]j\in[n], can also be done in O(n)O(n) time using O(n)O(n) space. Together, this yields a running time of O(nlog⁡n)O(n\log n) and a space consumption of O(n)O(n).

The Algorithm

In the following, we write eie_i for the iith unit vector. First we give the formal recurrence for the classic Lawler-Moore algorithm and afterwards the changes we make for our algorithm.

We define values Fj(t)F_j(t) as the maximum weight of an EDD schedule using a subset of the jobs {1,…,j}\{1,\ldots,j\} with machine-load vector tt. If no such schedule exists, its value is −∞-\infty. For j=0j=0 and t∈{0,1,…,dmax⁡}m∖{0}t\in\{0,1,\ldots,d_{\max}\}^m\setminus\{0\}, we initialize

F0(0)=0,F0(t)=−∞.F_0(0)=0,\qquad F_0(t)=-\infty.

For j∈{1,…,n}j\in\{1,\ldots,n\} and t∈{0,…,dmax⁡}mt\in\{0,\ldots,d_{\max}\}^m, we set

Fj(t)=max⁡{Fj−1(t), max⁡r∈[m]pj≤tr≤dj{Fj−1(t−pjer)+wj}}.(2)F_j(t)=\max\left\{F_{j-1}(t),\ \max_{\substack{r\in[m]\\p_j\le t_r\le d_j}}\left\{F_{j-1}(t-p_j e_r)+w_j\right\}\right\}. \tag*{(2)}

We use −∞+wj=−∞-\infty+w_j=-\infty and Fj′(t)=−∞F'_j(t)=-\infty for every t∉{0,…,dmax⁡}mt\notin\{0,\ldots,d_{\max}\}^m to simplify the notation. Compared to the classic algorithm, our algorithm stores only a single row of the dynamic program and not a row per job. For a job, we first collect all updates and then apply them afterwards to avoid using any job more than once. Further, we restrict the value of trt_r in Equation (2) to values from C‾j\overline{C}_j. Theorem 2.2 guarantees that we still find the optimal total weight of on-time jobs.

For the algorithm, we define a function

Insert⁡r:{{0,…,dmax⁡}m−1×{0,…,dmax⁡}→{0,…,dmax⁡}m,(u,t)↦(u1,…,ur−1,t,ur,…,um−1)\operatorname{Insert}_r: \left\{ \begin{aligned} \{0,\ldots,d_{\max}\}^{m-1}\times\{0,\ldots,d_{\max}\}&\to\{0,\ldots,d_{\max}\}^{m},\\ (u,t)&\mapsto(u_1,\ldots,u_{r-1},t,u_r,\ldots,u_{m-1}) \end{aligned} \right.

for each r∈[m]r \in[m], which constructs from a vector u∈{0,…,dmax⁡}m−1u \in\{0,\ldots,d_{\max}\}^{m-1} a new vector x∈{0,…,dmax⁡}mx \in\{0,\ldots,d_{\max}\}^{m} by placing the value tt as its rrth coordinate and copying the old values from uu as its other coordinates. The complete algorithm is given as Algorithm 2. The array ff in the algorithm represents the dynamic computation. It is only modified at the end of every iteration of the outermost loop by applying the updates from the corresponding list.

Algorithm 2 WeightedTardyJobs

Require: All original jobs (pj,dj,wj)(p_j,d_j,w_j) in EDD order, mm identical parallel machines

Ensure: Maximum total weight of on-time jobs

  1. Compute the values (a1,…,an)(a_1,\ldots,a_n) as described in § 3.1

  2. Initialize f[x]←−∞f[x] \leftarrow-\infty for every x∈L:={0,…,dmax⁡}mx \in L := \{0,\ldots,d_{\max}\}^{m}

  3. f[0]←0f[0] \leftarrow0

  4. for j=1,…,nj=1,\ldots,n in increasing order do

  5. Updates ←[ ]\leftarrow[\ ]

  6. for t=dj,dj−1,…,ajt=d_j,d_j-1,\ldots,a_j in decreasing order do

  7. for u∈{0,…,dmax⁡}m−1u \in\{0,\ldots,d_{\max}\}^{m-1} do

  8. for r=1,…,mr=1,\ldots,m do

  9. x←Insert⁡r(u,t)x \leftarrow\operatorname{Insert}_r(u,t)

  10. y←x−pjery \leftarrow x-p_je_r

  11. if f[y]≠−∞f[y] \ne-\infty then

  12. Updates.append(x,f[y]+wj)(x,f[y]+w_j)

  13. for (x,best)(x,\mathit{best}) in Updates do

  14. f[x]←max⁡{f[x],best}f[x] \leftarrow\max\{f[x],\mathit{best}\}

  15. return max⁡x∈Lf[x]\max_{x\in L} f[x]

Lemma 3.3. Given an instance II of P∣∣∑jwjUjP||\sum_j w_jU_j, Algorithm 2 computes a value ww such that ∑j∈[n]wj−w≤OPT(I)\sum_{j\in[n]}w_j-w \le OPT(I) where OPT(I)OPT(I) denotes the optimal value of the instance II.

Proof. By Theorem 2.2 we know that there exists an optimal schedule τ\tau such that every on-time job completes at a canonical completion time and such that all on-time jobs are ordered in EDD order given by the indices. Lemma 3.1 guarantees that the values a1,…,ana_1,\ldots,a_n in Algorithm 2 are correct. Since Algorithm 2 iterates for every job jj through all canonical completion times C‾j\overline{C}_j and determines for every possible machine-load vector the maximum weight, Algorithm 2 also considers the same placement of jj as in the optimal schedule τ\tau. With this, we obtain ∑j∈[n]wj−w≤OPT(I)\sum_{j\in[n]}w_j-w \le OPT(I).

Lemma 3.4. Algorithm 2 has a running time of O~m(n+dmax⁡m+1)\widetilde{O}_m(n+d_{\max}^{m+1}) and uses Om(n+dmax⁡m)O_m(n+d_{\max}^{m}) space.

Proof. The values a1,…,ana_1,\ldots,a_n can be computed in O(nlog⁡n)O(n\log n) time using O(n)O(n) space by Lemma 3.2. The initialization of ff runs in O((dmax⁡+1)m)O((d_{\max}+1)^m) time and space. Afterwards, Algorithm 2 considers all possible canonical completion times and all vectors u∈{0,…,dmax⁡}m−1u \in\{0,\ldots,d_{\max}\}^{m-1} for every machine. The function Insert⁡r(u,t)\operatorname{Insert}_r(u,t) takes O(m)O(m) time and space. All other operations done by Algorithm 2 are simple comparisons, computations, array accesses and modifications that run in O(1)O(1) time. In total, we obtain a running time of

O(nlog⁡n+m⋅∑j=1n∣C‾j∣⋅(dmax⁡+1)m−1⋅m)≤O~m(n+dmax⁡m+1)O\left(n\log n+m\cdot\sum_{j=1}^{n}|\overline{C}_j|\cdot(d_{\max}+1)^{m-1}\cdot m\right)\le\widetilde{O}_m(n+d_{\max}^{m+1})

where the inequality holds by Lemma 2.3. The list Updates takes at most Om(dmax⁡m)O_m(d_{\max}^{m}) space while all updates performed in ff are in-place. Altogether, Algorithm 2 uses Om(n+dmax⁡m)O_m(n+d_{\max}^{m}) space.

Finding an Optimal Schedule

Constructing an optimal schedule from the dynamic program cannot be done by simple backtracking due to the restriction to a single row. To be able to construct a schedule without constructing the entire n⋅(dmax⁡+1)mn \cdot(d_{\max}+1)^m table, we store a sparse pointer data structure. The number of necessary back links can be bounded in the same way as the number of updates we perform to calculate the table.

Lemma 3.5. There exists a schedule where the weighted number of on-time jobs is at least the output of Algorithm 2. Using additional O~m(dmax⁡m+1)\widetilde{O}_m(d_{\max}^{m+1}) space, we can construct a schedule in time Om(n+dmax⁡m)O_m(n+d_{\max}^m) after running the dynamic program.

Proof. Let f0f_0 be the initial state of ff in Algorithm 2 and fif_i the state after the iith job was processed. Let x∈Lx \in L be such that fn(x)=max⁡y∈L{fn(y)}f_n(x)=\max_{y\in L}\{f_n(y)\}. By the recursive formula of the dynamic program every entry in fif_i has a predecessor in fi−1f_{i-1}. We denote the predecessors of xx by

0=x(0),x(1),…,x(n)=x.0=x^{(0)},x^{(1)},\ldots,x^{(n)}=x.

When x(i−1)≠x(i)x^{(i-1)} \ne x^{(i)}, then there exists an ri∈[m]r_i \in[m] such that x(i−1)+pieri=x(i)x^{(i-1)}+p_i e_{r_i}=x^{(i)} and fi−1(x(i−1))+wi=fi(x(i))f_{i-1}(x^{(i-1)})+w_i=f_i(x^{(i)}). We construct a schedule as follows: for all indices i∈[n]i \in[n] with a defined rir_i we schedule job ii on machine rir_i. Since Algorithm 2 only considers canonical completion times for each job jj, it holds that Cj(τ′)≤djC_j(\tau') \le d_j for our constructed schedule τ′\tau'. We arbitrarily schedule the remaining jobs after the on-time jobs. The weight of the on-time jobs is at least fn(x)f_n(x), which shows the first part of the claim.

Next, we discuss how to obtain such a schedule constructively by introducing back links. Every entry is associated with a reference to a back link that describes how this value was achieved. More precisely, every time we find an improvement over a value in ff in line 12 we record the current job index, the machine placement, and a reference to the back link yielding the predecessor. During the update process we also update the associated back link for every entry by keeping a reference to the back link from the most profitable update. After the dynamic program has finished, the back links can be used to construct a schedule as described above. This takes O(mdmax⁡+n)O(md_{\max}+n) time since at most mdmax⁡md_{\max} back links need to be considered and the remaining jobs need to be scheduled somewhere.

The number of back links created during the algorithm is bounded by the number of candidates considered in the dynamic program. The proof of Lemma 3.4 shows that the number of candidates considered is bounded by O~m(dmax⁡m+1)\widetilde{O}_m(d_{\max}^{m+1}), which directly gives the necessary space bound.

Now we have all the ingredients needed to prove our main result.

Theorem 1.1. Given an instance of Pm∥∑jwjUjP_m \mathbin{\|} \sum_j w_j U_j, the optimal value can be calculated in O~m(n+dmax⁡m+1)\widetilde{O}_m(n+d_{\max}^{m+1}) time and Om(n+dmax⁡m)O_m(n+d_{\max}^m) space. Using additional O~m(dmax⁡m+1)\widetilde{O}_m(d_{\max}^{m+1}) space, we can construct an optimal schedule in the same time.

Proof. Combining Lemmas 3.3 and 3.5 shows that Algorithm 2 calculates the optimal value. Lemma 3.5 shows how to construct the schedule. Lemmas 3.4 and 3.5 together show the running time and space bounds.

Conclusion

We showed that Pm∥∑jwjUjP_m \mathbin{\|} \sum_j w_j U_j can be solved in time O~m(n+dmax⁡m+1)\widetilde{O}_m(n+d_{\max}^{m+1}). For 1∥∑jwjUj1\mathbin{\|} \sum_j w_j U_j this result implies an algorithm with running time O~(n+dmax⁡2)\widetilde{O}(n+d_{\max}^2), which answers the open question by Hermelin, Molter, and Shabtay [13]. Assuming the (min⁡,+)(\min,+)-convolution hypothesis there is no algorithm with running time O~((n+dmax⁡)2−ε)\widetilde{O}((n+d_{\max})^{2-\varepsilon}) for any ε>0\varepsilon>0 due to the connection to the knapsack problem. In contrast to knapsack it is not known whether a truly subquadratic (min⁡,+)(\min,+)-convolution algorithm yields a subquadratic algorithm for 1∥∑jwjUj1\mathbin{\|} \sum_j w_j U_j. An interesting open question is whether these problems are equivalent under subquadratic reductions.

For the single-machine problem, it is known that a running time O~(n+pmax⁡c)\widetilde{O}(n + p_{\max}^{c}) for any constant c>0c > 0 is impossible under the ∀∃\forall\exists-SETH [1 BHKS26]. In particular, a running time of O~(n+pmax⁡2)\widetilde{O}(n + p_{\max}^{2}) is ruled out under this assumption, but is a hybrid running time of O~(n+dmax⁡pmax⁡)\widetilde{O}(n + d_{\max}p_{\max}) possible? This would also be a direct improvement over the O~(d#n+d#dmax⁡pmax⁡)\widetilde{O}(d_{\#}n + d_{\#}d_{\max}p_{\max}) algorithm by Hermelin, Molter, and Shabtay [13], removing both d#d_{\#} factors.

Declaration of Generative AI Use

The idea for the algorithm was generated by GPT-6 Astra. The authors independently verified the idea and worked out the details of the algorithm and the proofs. Afterwards, GPT-6 Astra was used to polish the paper. The authors take full responsibility for the entire content, technical claims, and integrity of the paper.

References

  1. [1]A. Abboud, K. Bringmann, D. Hermelin, and D. Shabtay. “Scheduling lower bounds via AND subset sum”. In: J. Comput. Syst. Sci. 127 (2022), pp. 29–40. DOI: 10.1016/J.JCSS.2022.01.005.DOI
  2. [2]K. Bringmann, A. Dürr, and K. Węgrzycki. “Tight (S)ETH-Based Lower Bounds for Pseudopolynomial Algorithms for Bin Packing and Multi-machine Scheduling”. In: Proceedings of the 58th Annual ACM Symposium on Theory of Computing, STOC 2026, Salt Lake City, UT, USA, June 22-26, 2026. Ed. by A. Bhaskara and A. Czumaj. ACM, 2026, pp. 2094–2105. DOI: 10.1145/3798129.3800913.DOI
  3. [3]R. Bellman. Dynamic Programming. Princeton, NJ: Princeton University Press, 1957.pubmed.ncbi.nlm.nih.gov/17730601
  4. [5]K. Bringmann. “Knapsack with Small Items in Near-Quadratic Time”. In: Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024. Ed. by B. Mohar, I. Shinkar, and R. O’Donnell. ACM, 2024, pp. 259–270. DOI: 10.1145/3618260.3649719.DOI
  5. [6]T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms, 3rd Edition. MIT Press, 2009. ISBN: 978-0-262-03384-8. URL: http://mitpress.mit.edu/books/introduction-algorithms.
  6. [7]M. Cygan, M. Mucha, K. Węgrzycki, and M. Włodarczyk. “On Problems Equivalent to (min, +)-Convolution”. In: ACM Trans. Algorithms 15.1 (2019), 14:1–14:25. DOI: 10.1145/3293465.DOI
  7. [8]A. Dhar, A. Dürr, A. Ghazy, J. Greilhuber, and K. Węgrzycki. “Faster Exponential Algorithms for Multi-Machine Scheduling Problems”. In: 34th Annual European Symposium on Algorithms, ESA 2026, L’Aquila, Italy, August 31 - September 4, 2026. Ed. by P. Bille, S. Pettie, and S. Storandt. Vol. 388. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, 53:1–53:22. DOI: 10.4230/LIPICS.ESA.2026.53.DOI
  8. [9]N. Fischer and L. Wennmann. “Minimizing Tardy Processing Time on a Single Machine in Near-Linear Time”. In: TheoretiCS 4, 14 (2025). DOI: 10.46298/THEORETICS.25.14.DOI
  9. [10]R. Graham, E. Lawler, J. Lenstra, and A. Rinnooy Kan. “Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey”. In: Discrete Optimization II. Ed. by P. Hammer, E. Johnson, and B. Korte. Vol. 5. Annals of Discrete Mathematics. Elsevier, 1979, pp. 287–326. DOI: 10.1016/S0167-5060(08)70356-X.DOI
  10. [11]K. Heeger and D. Hermelin. “Minimizing the weighted number of tardy jobs is W[1]-hard”. In: J. Comput. Syst. Sci. 161 (2026), p. 103817. doi: 10.1016/J.JCSS.2026.103817.DOI
  11. [12]D. Hermelin, S. Karhi, M. L. Pinedo, and D. Shabtay. “New algorithms for minimizing the weighted number of tardy jobs on a single machine”. In: Ann. Oper. Res. 298.1 (2021), pp. 271–287. doi: 10.1007/S10479-018-2852-9.
  12. [13]D. Hermelin, H. Molter, and D. Shabtay. “Minimizing the Weighted Number of Tardy Jobs via (max,+)-Convolutions”. In: INFORMS J. Comput. 36.3 (2024), pp. 836–848. doi: 10.1287/IJOC.2022.0307.DOI
  13. [14]C. Jin. “0-1 Knapsack in Nearly Quadratic Time”. In: Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024. Ed. by B. Mohar, I. Shinkar, and R. O’Donnell. ACM, 2024, pp. 271–282. DOI: 10.1145/3618260.3649618.DOI
  14. [15]K. Jansen and K. Kahler. “On the Complexity of Scheduling Problems with a Fixed Number of Parallel Identical Machines”. In: SOFSEM 2023: Theory and Practice of Computer Science, 48th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2023, Nový Smokovec, Slovakia, January 15-18, 2023, Proceedings. Vol. 13878. Lecture Notes in Computer Science. Springer, 2023, pp. 192–206. DOI: 10.1007/978-3-031-23101-8_13.DOI
  15. [16]R. M. Karp. “Reducibility among Combinatorial Problems”. In: Complexity of Computer Computations: Proceedings of a symposium on the Complexity of Computer Computations, held March 20–22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, and sponsored by the Office of Naval Research, Mathematics Program, IBM World Trade Corporation, and the IBM Research Mathematical Sciences Department. Ed. by R. E. Miller, J. W. Thatcher, and J. D. Bohlinger. Boston, MA: Springer US, 1972, pp. 85–103. DOI: 10.1007/978-1-4684-2001-2_9.DOI
  16. [17]K. Klein, A. Polak, and L. Rohwedder. “On Minimizing Tardy Processing Time, Max-Min Skewed Convolution, and Triangular Structured ILPs”. In: Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023. Ed. by N. Bansal and V. Nagarajan. SIAM, 2023, pp. 2947–2960. DOI: 10.1137/1.9781611977554.CH112.DOI
  17. [18]C. Lenté, M. Liedloff, A. Soukhal, and V. T’kindt. Exponential Algorithms for Scheduling Problems. Tech. rep. 2014. URL: https://hal.science/hal-00944382.
  18. [19]E. L. Lawler and J. M. Moore. “A Functional Equation and Its Application to Resource Allocation and Sequencing Problems”. In: Management Science 16.1 (1969), pp. 77–84. DOI: 10.1287/mnsc.16.1.77.DOI
  19. [20]A. Polak, L. Rohwedder, and K. Wegrzycki. “Knapsack and Subset Sum with Small Items”. In: 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, Glasgow, Scotland (Virtual Conference), July 12-16, 2021. Ed. by N. Bansal, E. Merelli, and J. Worrell. Vol. 198. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, 106:1–106:19. DOI: 10.4230/LIPICS.ICALP.2021.106.DOI

Paper details

vlnc:W_d2ssfecm
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents