Minimizing the Number of Tardy Jobs with Uniform Processing Times on Parallel Machines

We consider the case where release dates and weights are present and we have multiple identical parallel machines. However, we add the restriction that all processing times are the same. This problem is called $P\mid r_j,p_j=p\mid \sum w_j{U}_j$, we give a formal definition in Section 2. This problem arises naturally in manufacturing systems, where

• $\mathrm{■}$

  exact specifications by the customers for the product have negligible influence on the production time, but

• $\mathrm{■}$

  the specifications only become available at certain times and customers request the product to meet certain due dates.

As an illustrative example, consider the problem of scheduling burn-in operations in integrated circuit manufacturing. The specification of the layout of the circuit may only become available at a certain time, as it takes time to optimize it. At the same time, the specific layout has little to no influence on the processing time of the burn-in operation [31]. Furthermore, the customer may wish to have the circuit delivered at a certain due date.

To the best of our knowledge, the only known algorithmic result for $P\mid r_j,p_j=p\mid \sum w_j{U}_j$ is a polynomial-time algorithm by Baptiste et al. [2, 3] for the case where the number of machines is a constant. However, two special cases are known to be polynomial-time solvable. It is folklore that the case without release dates, $P\mid p_j=p\mid {\sum }_j{w}_j{U}_j$, and the case where the processing times equal one, $P\mid r_j,p_j=1\mid {\sum }_j{w}_j{U}_j$, can both be reduced to the Linear Assignment problem in a straightforward manner. The Linear Assignment problem is known to be solvable in polynomial time [27]. Furthermore, it is known that, given an instance of $P\mid r_j,p_j=p\mid \sum w_j{U}_j$, we can check in polynomial time whether all jobs can be scheduled such that no job is tardy [5, 37, 38].

The complexity status of $P\mid r_j,p_j=p\mid \sum w_j{U}_j$ and its unweighted version $P\mid r_j,p_j=p\mid \sum U_j$ was a longstanding open problem. Kravchenko and Werner [25] pointed out that this question remains unanswered in Note 2.1.19 and Sgall [36] listed this issue as Open Problem 2. Our main contribution is to resolve the complexity status of $P\mid r_j,p_j=p\mid \sum U_j$ (and hence also $P\mid r_j,p_j=p\mid \sum w_j{U}_j$) by showing the following.

• $\mathrm{■}$

  $P\mid r_j,p_j=p\mid \sum U_j$ is NP-hard.

Having established NP-hardness, we focus on studying the parameterized complexity of $P\mid r_j,p_j=p\mid \sum w_j{U}_j$. As mentioned before, Baptiste et al. [2, 3] showed that the problem is in XP when parameterized by the number of machines. Mnich and van Bevern [32, Open Problem 7] asked whether this result can be improved to an FPT algorithm. We answer this question negatively by showing the following.

• $\mathrm{■}$

  $P\mid r_j,p_j=p\mid \sum U_j$ is W[2]-hard when parameterized by the number of machines.

On the positive side, we give several new parameterized tractability results. By providing an alternative running time analysis of the algorithm for $P\mid r_j,p_j=p\mid \sum w_j{U}_j$ by Baptiste et al. [2, 3], we show the following.

• $\mathrm{■}$

  $P\mid r_j,p_j=p\mid \sum w_j{U}_j$ is in XP when parameterized by the processing time.

• $\mathrm{■}$

  $P\mid r_j,p_j=p\mid \sum w_j{U}_j$ is in FPT when parameterized by the combination of the number of machines and the processing time.

Finally, we give a new algorithm based on a mixed integer linear program (MILP) formulation for $P\mid r_j,p_j=p\mid \sum w_j{U}_j$. We show the following.

• $\mathrm{■}$

  $P\mid r_j,p_j=p\mid \sum w_j{U}_j$ is in FPT when parameterized by the number of different release dates.

• $\mathrm{■}$

  $P\mid r_j,p_j=p\mid \sum w_j{U}_j$ is in FPT when parameterized by the number of different due dates.

We conclude by pointing to new future research directions. Most prominently, we leave open whether $P\mid r_j,p_j=p\mid \sum w_j{U}_j$ is in FPT or W[1]-hard when parameterized by the processing time.

We give an overview of the literature investigating the parameterized complexity of minimizing the weighted number of tardy jobs in various related settings.

The problem of minimizing the weighted number of tardy jobs on a single machine, $1\mid \mid {\sum }_j{w}_j{U}_j$ has been extensively studied in the literature under various aspects and constraints. Hermelin et al. [20] showed that the classical pseudopolynomial time algorithm by Lawler and Moore [28] can be improved in several special cases. Hermelin et al. [19] give an overview of the parameterized complexity of $1\mid \mid {\sum }_j{w}_j{U}_j$ with respect to the parameters “number of processing times”, “number of due dates”, and “number of weights” (and their combinations). In particular, $1\mid \mid \sum w_j{U}_j$ is in XP when parameterized by the number of different processing times [19]. This presumably cannot be improved to an FPT result as recently, it was shown that $1\mid \mid \sum w_j{U}_j$ parameterized by the number of different processing times is W[1]-hard [16]. Faster algorithms are known for the case where the job weights equal the processing times [4, 12, 23, 35] and the problem has also been studied under fairness aspects [17]. Kaul et al. [22] extended the results of Hermelin et al [19] to $1\mid r_j\mid \sum w_j{U}_j$, considering the “number of release times” as an additional parameter.

Minimizing the weighted number of tardy jobs on parallel machines has mostly been studied in the context of interval scheduling ($P\mid d_j-r_j=p_j\mid {\sum }_j{w}_j{U}_j$) and generalizations thereof [1, 18, 26, 39].

The setting where processing times are assumed to be uniform has been studied under various optimization criteria (different from minimizing the weighted number of tardy jobs) and constraints. For an overview, we refer to Kravchenko and Werner [25] and Baptiste et al. [3]. The even more special case of unit processing times has also been extensively studied. Reviewing the related literature in this setting is out of scope for this work.

Using the standard three-field notation for scheduling problems by Graham et al. [15], the problem considered in this work is called $P\mid r_j,p_j=p\mid \sum w_j{U}_j$. In this problem, we have $n$ jobs and $m$ machines. Each machine can process one job at a time. Generally, we use the variable $j$ to denote jobs and the variable $i$ to denote machines. Each job $j$ has a processing time $p_j=p$, a release date $r_j$, a due date $d_j$, and a weight $w_j$, where $p$, $r_j$, $d_j$, and $w_j$ are nonnegative integers. We use $r_{\mathrm{\#}}$, $d_{\mathrm{\#}}$, and $w_{\mathrm{\#}}$ to denote the number of different release dates, due dates, and weights, respectively.

A schedule maps each job $j$ to a combination of a machine $i$ and a starting time $t$, indicating that $j$ shall be processed on machine $i$ starting at time $t$. More formally, a schedule is a function $\sigma :\{1,\mathrm{\dots },n\}\to \{1,\mathrm{\dots },m\}\times \mathbb{N}$. If for job $j$ we have $\sigma (j)=(i,t)$, then job $j$ is scheduled to be processed on machine $i$ starting at time $t$ until time $t+p$. A schedule $\sigma$ is feasible if there is no job $j$ with $\sigma (j)=(i,t)$ and and if there is no pair of jobs $j,j^{\prime }$ with $\sigma (j)=(i,t)$ and $\sigma (j^{\prime })=(i,t^{\prime })$ such that . We say that a job $j$ is early in a feasible schedule $\sigma$ if $\sigma (j)=(i,t)$ and $t+p\le d_j$, otherwise we say that job $j$ is tardy. We say that machine $i$ is idle at time $t$ in a feasible schedule $\sigma$ if there is no job $j$ with $\sigma (j)=(i,t^{\prime })$ and $t^{\prime }\le t\le t^{\prime }+p$. The goal is to find a feasible schedule that minimizes the weighted number of tardy jobs or, equivalently, maximizes the weighted number of early jobs $W={\sum }_{j\mid \sigma (j)=(i,t)\wedge t+p\le d_j}{w}_j$. We call a feasible schedule that maximizes the weighted number of early jobs optimal. Formally, the problem is defined as follows.

We use $P\mid r_j,p_j=p\mid \sum U_j$ to denote the unweighted (or, equivalently, uniformly weighted) version of $P\mid r_j,p_j=p\mid \sum w_j{U}_j$, that is, the case where $w_j=w_{j^{\prime }}$ for every two jobs $j$ and $j^{\prime }$, or equivalently, $w_{\mathrm{\#}}=1$.

Note that given any feasible schedule of the early jobs, one can easily extend this to a feasible schedule of all jobs as tardy jobs can be scheduled arbitrarily late. Thus, when describing a schedule, we will only describe how the early jobs are scheduled.

Given an instance $I$ of $P\mid r_j,p_j=p\mid \sum w_j{U}_j$, we can make the following observation, essentially implying that one can switch the roles of release dates and due dates.

To see that 1 is true note that a feasible schedule $\sigma$ for $I$ can be transformed into a feasible schedule ${\sigma }^{\prime }$ for $I^{\prime }$ (with the same weighted number of early jobs) by setting ${\sigma }^{\prime }(j)=(i,d_{\max }-t-p)$, where $\sigma (j)=(i,t)$.

We now show that we can restrict ourselves to schedules where jobs may start only at “few” different points in time, which will be useful in our proofs. In order to do so, we define a set $𝒯$ of relevant starting time points.

It is known that there always exists an optimal schedule where the starting times of all jobs are in $𝒯$.

We use the following standard concepts from parameterized complexity theory [7, 11, 13]. A parameterized problem $L\subseteq {\mathrm{\Sigma }}^{\ast }\times \mathbb{N}$ is a subset of all instances $(x,k)$ from ${\mathrm{\Sigma }}^{\ast }\times \mathbb{N}$, where $k$ denotes the parameter. A parameterized problem $L$ is in the class FPT (or fixed-parameter tractable) if there is an algorithm that decides every instance $(x,k)$ for $L$ in $f(k)\cdot {|x|}^{O(1)}$ time for some computable function $f$ that depends only on the parameter. A parameterized problem $L$ is in the class XP if there is an algorithm that decides every instance $(x,k)$ for $L$ in ${|x|}^{f(k)}$ time for some computable function $f$ that depends only on the parameter. If a parameterized problem $L$ is W[1]-hard or W[2]-hard, then it is presumably not contained in FPT [7, 11, 13].

Let $X=\{u_{i_1},\mathrm{\dots },u_{i_k}\}$ be a hitting set of size $k$ for $I$. We construct a schedule for $I^{\prime }$ as follows. On machine $q$, for each $\mathrm{\ell }\in \{0,\mathrm{\dots },k\cdot (n-1)\}$ and $j\in \{0,\mathrm{\dots },m-1\}$, we schedule one job to start at time $(\mathrm{\ell }\cdot m+j)\cdot p+i_q$. This job is $J_{A_j,u_{i_q}}^{\mathrm{\ell }}$ if $u_{i_q}\in A_j$, and $D_{A_j}^{\mathrm{\ell }}$ otherwise. Because $X$ is a hitting set, we have that $u_{i_q}\in A_j$ for some $q\in \{1,\mathrm{\dots },k\}$ and hence we schedule each dummy job $D_{A_j}^{\mathrm{\ell }}$ at most $k-1$ times, that is, at most its multiplicity times.

We can observe that all jobs scheduled so far are early. For each job $J_{A_j,u_{i_q}}^{\mathrm{\ell }}$ that is scheduled on machine $q$, we have set its starting time to $(\mathrm{\ell }\cdot m+j)\cdot p+i_q$ which equals this job’s release date (cf. Table 1). Furthermore, job $J_{A_j,u_{i_q}}^{\mathrm{\ell }}$ finishes at $(\mathrm{\ell }\cdot m+j+1)\cdot p+i_q$, its deadline. Each dummy job $D_{A_j}^{\mathrm{\ell }}$ is early as well, since their release times are smaller or equal to the release time of $J_{A_j,u_{i_q}}^{\mathrm{\ell }}$, and their due dates are larger or equal to the due date of $J_{A_j,u_{i_q}}^{\mathrm{\ell }}$. Furthermore, we can observe that there is no overlap in the processing times between any two jobs scheduled on machine $q$.

It follows that we have feasibly scheduled $(k\cdot (n-1)+1)\cdot m\cdot k$ such that they finish early. We schedule the remaining jobs in some arbitrary way such that the schedule remains feasible. $◀$

Next, we continue with the backward direction.

Let $\sigma$ be a feasible schedule for $I^{\prime }$ with $(k\cdot (n-1)+1)\cdot m\cdot k$ early jobs. Since the largest due date is $(k\cdot (n-1)\cdot m+m)\cdot p+n$ and $p=2n$, it follows that on each machine, at most $k\cdot (n-1)\cdot m+m$ jobs can be scheduled in a feasible way such that they finish early. Consequently, on each machine, there are exactly $(k\cdot (n-1)+1)\cdot m$ early jobs.

More specifically, for each machine, each $\mathrm{\ell }\in \{0,\mathrm{\dots },k\cdot (n-1)\}$ and $j\in \{0,\mathrm{\dots },m-1\}$, there must be one job which starts in the interval $[(\mathrm{\ell }\cdot m+j)\cdot p,(\mathrm{\ell }\cdot m+j)\cdot p+n]$. Otherwise, there would be less than $(k\cdot (n-1)+1)\cdot m$ early jobs on that machine. For machine $q$, let $x_{\mathrm{\ell }}^q\in \{1,\mathrm{\dots },n\}$ such that there is a job on machine $q$ which starts at time $\mathrm{\ell }\cdot m\cdot p+x_{\mathrm{\ell }}^q$ (the existence of such a job is guaranteed by the previous observation). Then we must have $1\le x_0^q\le x_1^q\le \mathrm{\dots }\le x_{k\cdot (n-1)}^q\le n$. This follows from the observation that if $x_{\mathrm{\ell }}^q>x_{\mathrm{\ell }+1}^q$, then the starting time of the job corresponding to $x_{\mathrm{\ell }+1}^q$ would be earlier than the completion time of the job corresponding to $x_{\mathrm{\ell }}^q$ and hence the schedule would be infeasible. Consequently, there are at most $n-1$ values of $\mathrm{\ell }$ such that $x_{\mathrm{\ell }}^q\ne x_{\mathrm{\ell }+1}^q$. As there are $k$ machines, this implies that there are at most $k\cdot (n-1)$ values such that $x_{\mathrm{\ell }}^q\ne x_{\mathrm{\ell }+1}^q$ for some machine $q$. We can conclude that there exists at least one $\mathrm{\ell }\in \{0,\mathrm{\dots },k\cdot (n-1)\}$ so that $x_{\mathrm{\ell }}^q=x_{\mathrm{\ell }+1}^q$ for every machine $q$. This implies that for each $j\in \{0,\mathrm{\dots },m-1\}$ and each machine $q$, there is one job starting at time $(\mathrm{\ell }\cdot m+j)\cdot p+x_{\mathrm{\ell }}^q$ on machine $q$. We fix such an $\mathrm{\ell }$ for the rest of the proof and claim that $X=\{u_{x_{\mathrm{\ell }}^1},\mathrm{\dots },u_{x_{\mathrm{\ell }}^k}\}$ is a hitting set of size at most $k$ for $I$.

Clearly, $X$ has size at most $k$. Consider some set $A_j\in 𝒜$ with $j\in \{0,\mathrm{\dots },m-1\}$. The only jobs which can start in the interval $[(\mathrm{\ell }\cdot m+j)\cdot p,(\mathrm{\ell }\cdot m+j)\cdot p+n]$ are the dummy jobs $D_{A_j}^{\mathrm{\ell }}$ and the jobs $J_{A_j,u_i}^{\mathrm{\ell }}$ for $u_i\in A_j$. Because there are only $k-1$ dummy jobs $D_{A_j}^{\mathrm{\ell }}$ but $k$ machines, this implies that there exists at least one machine $q$ such that job $J_{A_j,u_i}^{\mathrm{\ell }}$ is scheduled at machine $q$ for some $u_i\in A_j$. We know that on machine $q$ one job starts in the interval $[(\mathrm{\ell }\cdot m+j)\cdot p,(\mathrm{\ell }\cdot m+j)\cdot p+n]$ and has starting time $(\mathrm{\ell }\cdot m+j)\cdot p+x_{\mathrm{\ell }}^q$. By construction, this job must be $J_{A_j,u_i}^{\mathrm{\ell }}$ with $i=x_{\mathrm{\ell }}^q$ which implies that $u_i=u_{x_{\mathrm{\ell }}^q}\in X$. We can conclude that $X$ is a hitting set for $I$. $◀$

Now we have all the pieces to prove Theorem 3.

4 shows that the described reduction can be computed in polynomial time and produces an instance of $P\mid r_j,p_j=p\mid \sum U_j$ with $k$ machines. Lemmas 5 and 6 show that the described reduction is correct. Since Hitting Set is known to be NP-hard [21] and W[2]-hard when parameterized by $k$ [10], the result follows. $◀$

To prove Theorem 8 we give a different bound for the size of $𝒳$. Recall that for all resource profiles $x\in 𝒳$ we have that $x_m-x_1\le p$. It follows that there are $|𝒯|$ possibilities for the value of $x_1$, and then for $2\le i\le m$ we have that $x_1\le x_i\le x_1+p$. Hence, we get that $|𝒳|\in O(n^2\cdot p^{m-1})$. This together with Lemma 9 immediately gives us that $P\mid r_j,p_j=p\mid \sum w_j{U}_j$ can be solved in $p^{O(m)}\cdot n^{O(1)}$ time.

Furthermore, we have $x_1\le x_2\le \mathrm{\dots }\le x_m$. Hence, the resource profile $x$ can be characterized by counting how many times a value $t\in 𝒯$ appears in $x$. Again, we can exploit that $x_m-x_1\le p$. There are $|𝒯|$ possibilities for the value of $x_1$ and given $x_1$, each other entry $x_i$ of $x$ with $2\le i\le m$ can be characterized by the amount $0\le y_i=x_i-x_1\le p$ by which it is larger than $x_1$. Clearly, there are $p+1$ different possible values for the amount $y_i$. It follows that given $x_1$, we can characterize $x$ by counting how often a value $0\le t\le p$ appears as an amount. Hence, we get that $|𝒳|\in O(n^2\cdot m^{p+1})$. This together with Lemma 9 immediately gives us that $P\mid r_j,p_j=p\mid \sum w_j{U}_j$ can be solved in $m^{O(p)}\cdot n^{O(1)}$ time. $◀$

Lastly, we remark that with similar alternative running time analyses for the dynamic programming algorithm by Baptiste et al. [2, 3], one can show that $P\mid r_j,p_j=p\mid \sum w_j{U}_j$ is in XP when parameterized by the number of release dates or due dates, and that $P\mid r_j,p_j=p\mid \sum w_j{U}_j$ is in FPT when parameterized by the combination of the number of machines and the number of release dates or due dates. However, as we show in the next section, we can obtain fixed-parameter tractability by parameterizing only by the number of release dates or parameterizing only by the number of due dates.

Assume that there is a job $j$ such that $\sigma (j)=(i,t)$ for some $t>r_j$ and machine $i$ is idle at time $t-1$. Assume that job $j$ is the earliest such job, that is, the job with minimum $t$. Since machine $i$ is idle at time $t-1$ and , we can create a new schedule ${\sigma }^{\prime }$ that is the same as $\sigma$ except that ${\sigma }^{\prime }(j)=(i,t-1)$. Clearly, we have that ${\sigma }^{\prime }$ is feasible and has the same weighted number of early jobs as $\sigma$. By repeating this process, we obtain a feasible schedule ${\sigma }^{\prime \prime }$ with the same set of early jobs and such that for each job $j$ with ${\sigma }^{\prime \prime }(j)=(i,t)$ and machine $i$ is idle at time $t-1$, it holds that $t=r_j$. Furthermore, we have that each starting point in ${\sigma }^{\prime \prime }$ is a release date $r$ or a time $t$ with $t=r+\mathrm{\ell }\cdot p$ for some release date $r$ and some integer $\mathrm{\ell }$. Hence, all starting times of ${\sigma }^{\prime \prime }$ are in the set $𝒯$ of relevant starting time points. $◀$ We call a feasible schedule $\sigma$ release date aligned if the second condition of Lemma 13 holds, i.e., for each job $j$ with $\sigma (j)=(i,t)$ for some $t>r_j$, the machine $i$ is not idle at time $t-1$. Note that Lemma 13 is stronger than Lemma 2 and implies that there always exists an optimal feasible schedule that is release date aligned.

Given a feasible schedule $\sigma$ that is release date aligned, we say that a release date $r_j$ is active on machine $i$ if job $j$ is scheduled to start at this release date, that is, $\sigma (j)=(i,r_j)$, and machine $i$ is idle at time $r_j-1$. Let $T$ be a subset of all release dates, then we say that machine $i$ has type $T$ in $\sigma$ if $T$ is the set of active release dates on machine $i$.

Recall that $𝒯=\{t\mid \exists r_j\text{ and }\exists 0\le \mathrm{\ell }\le n\text{ s.t. }t=r_j+p\cdot \mathrm{\ell }\}$ denotes the set of relevant starting time points. We say that a starting time $t\in 𝒯$ is available on a machine with type $T$ if $t=r+\mathrm{\ell }\cdot p$ for some $r\in T$ and $t+p\le r^{\prime }$, where $r^{\prime }$ is the smallest release date in $T$ that is larger than $r$.

Given an instance $I$ of $P\mid r_j,p_j=p\mid \sum w_j{U}_j$, we create an instance $I^{\prime }$ of MILP as follows. For each type $T$ we create an integer variable $x_T$ that quantifies how many machines have type $T$ and create the constraint

For each starting time $t\in 𝒯$ we create a fractional variable $x_t$ that quantifies on how many machines the starting time $t$ is available and create the following set of constraints.

where $t_T=1$ if starting time $t$ is available on a machine with type $T$ and $t_T=0$ otherwise.

For each combination of a job $j$ and a starting time $t$, we create a fractional variable $x_{j,t}$ if job $j$ can be scheduled to start at time $t$ without violating $j$’s release date or due date. This variable indicates whether job $j$ is scheduled to start at starting time $t$ and is early. We create the following constraints.

Finally, we use the following function as the maximization objective.

This finishes the construction of the MILP instance $I^{\prime }$. We can observe the following.

In the following, we prove the correctness of the reduction to MILP. We start with showing that if the $P\mid r_j,p_j=p\mid \sum w_j{U}_j$ instance admits a feasible schedule where the weighted number of early jobs is $W$, then the constructed MILP instance admits a feasible solution that has objective value $W$.

Assume that we are given a feasible schedule $\sigma$ for $I$ such that the weighted number of early jobs is $W$. By Lemma 13 we can assume that $\sigma$ is release date aligned.

We construct a solution for $I^{\prime }$ as follows. Consider job $j$ and let $\sigma (j)=(i,t)$ such that $t+p\le d_j$, that is, job $j$ is early. We know that $t\in 𝒯$. We set $x_{j,t}=1$ and for all $t^{\prime }\in 𝒯$ with $t^{\prime }\ne t$, we set $x_{j,t^{\prime }}=0$. Note that this guarantees that Constraints (4) are fulfilled. Furthermore, assuming we can set the remaining variables to values such that the remaining constraints are fulfilled, we have that the objective value of the solution to $I^{\prime }$ is $W$.

In the remainder, we show how to set the remaining variables such that all constraints are fulfilled. Initially, we set all variables $x_T$ to zero. Next, we determine the type of each machine. Consider machine $i$. Then $T:=\{r\mid \exists j\text{ s.t. }\sigma (j)=(i,r_j)\}$ is the type of machine $i$. Then we increase $x_T$ by one. We do this for every machine. Clearly, afterwards Constraint (1) are fulfilled.

Next, we set $x_t:={\sum }_T{t}_T\cdot x_T$, where $t_T=1$ if starting time $t$ is available on a machine with type $T$ and $t_T=0$ otherwise. Clearly, this fulfills Constraints (2). It remains to show that Constraints (3) are fulfilled. So consider some time $t\in 𝒯$. For each job $j$ starting at time $t$ on some machine $i$, we increased $x_T$ by one for some $T$ with $t_T=1$ when processing machine $i$. Thus, we have ${\sum }_j{x}_{j,t}\le {\sum }_T{t}_T\cdot x_T=x_t$. $◀$

Before we continue with the other direction of the correctness, we prove that we can apply Lemma 12 to show that the MILP instance $I^{\prime }$ admits an optimal solution where all variables are set to integer values.

Notice that since the Constraints (2) are equality constraints, we have that in any feasible solution to $I^{\prime }$, all variables $x_t$ are set to integer values. Hence, $I^{\prime }$ is equivalent to the MILP $I^{\prime \prime }$ arising from $I^{\prime }$ by declaring $x_t$ to be integer variables for every $t\in 𝒯$ (in addition to the variables $x_T$), and it suffices to show that $I^{\prime \prime }$ has an integer solution.

We show that the constraint matrix for the fractional variables $x_{j,t}$ in $I^{\prime \prime }$ (i.e., the variables $x_{j,t}$) is totally unimodular. By Lemma 12 this implies that $I^{\prime \prime }$ and therefore also $I^{\prime }$ admits an optimal solution where all variables are set to integer values.

Note that the Constraints (3) partition the set of fractional variables $x_{j,t}$, that is, each fractional variable is part of exactly one of the Constraints (3). The same holds for the Constraints (4). Furthermore, the coefficients in the constraint matrix for each variable are either 1 (if they are part of a constraint) or 0. Hence, we have that the constraint matrix is a 0-1 matrix with exactly two 1’s in every column. Moreover, in each column, one of the two 1’s appears in a row corresponding to the Constraints (3) and the other 1 is in a row corresponding to the Constraints (4). This is a sufficient condition for the constraint matrix to be totally unimodular [9].

Finally, we argue that an optimal integer solution for $I^{\prime \prime }$ can be computed in the claimed running time upper-bound. We use the algorithm implicitly described by Chaudhary et al. [6] in their proof for Lemma 12. First, we compute an optimal solution for $I^{\prime }$. By the arguments at the beginning of this proof, this is also an optimal solution for $I^{\prime \prime }$. To transform this optimal solution into an optimal solution where every variable is set to an integer value, we fix all integer variables, resulting in an LP²²2Linear Program (LP) is the special case of MILP where no variables are considered integer variables (that is, the set $S$ in the definition of MILP is empty). instance $I^{\prime \prime \prime }$ whose variables are precisely the fractional variables from $I^{\prime \prime }$. Since the constraint matrix of this LP $I^{\prime \prime \prime }$ is totally unimodular (as argued above), it is well-known that an optimal solution for $I^{\prime \prime \prime }$ where all variables are set to integer values can be computed in polynomial time, see e.g. Korte and Vygen [24, Theorem 4.18]. Combining this integral optimal solution for $I^{\prime \prime \prime }$ with the integral variables from $I^{\prime \prime }$ then yields an optimal solution for $I^{\prime \prime }$. Now, with Theorem 11 and 14, we get the claimed overall running time upper-bound. $◀$

Now we proceed with showing that if the constructed MILP instance admits an optimal solution that has objective value $W$, then the original $P\mid r_j,p_j=p\mid \sum w_j{U}_j$ instance admits a feasible schedule where the weighted number of early jobs is $W$.

Assume we are given an optimal solution for $I^{\prime }$ where all variables are set to integer values and that has objective value $W$. We construct a feasible schedule $\sigma$ as follows.

First, we assign a type to every machine. Iterate through the types $T$ and, initially, set $i=1$. If $x_T>0$, then assign type $T$ to machines $i$ to $i+x_T-1$. Afterwards, increase $i$ by $x_T$. Since the solution to $I^{\prime }$ fulfills Constraint (1), we know that this procedure does not assign types to more than $m$ machines.

Now iterate through the relevant starting times $i\in 𝒯$. Let $J_t=\{j\mid x_{j,t}=1\}$ and let $M_t=\{i\mid \text{starting time }t\text{ is available on machine }i\}$. By Constraints (2) and (3) we know that $|J_t|\le |M_t|=x_t$. Hence, we can create a feasible schedule by setting $\sigma (j)=(i,t)$ for every job $j\in J_t$, where $i\in M_t$ and for all $j,j^{\prime }\in J_t$ with $j\ne j^{\prime }$ we have $\sigma (j)=(i,t)$ and $\sigma (j^{\prime })=(i^{\prime },t)$ with $i\ne i^{\prime }$. In other words, we schedule each job in $J_t$ to a distinct machine $i\in M_t$ with starting time $t$. The Constraints (4) ensure that we schedule each job at most once. For all jobs $j$ that are not contained in any set $J_t$ with $t\in 𝒯$, we schedule $j$ to an arbitrary machine $i$ to a starting time that is later than $r_j$ and later than the completion time of the last job scheduled on $i$. Clearly, we can compute $\sigma$ in time polynomial in $|I^{\prime }|$. By the definition of available starting times and the fact that we only create variable $x_{j,t}$ if $t\ge r_j$, this schedule is feasible.

It remains to show that the weighted number of early jobs is $W$. To this end, note that we only create variable $x_{j,t}$ if $r_j\le t$ and $t+p\le d_j$. Hence, for each job $j$ with $x_{j,t}=1$ for some $t\in 𝒯$, we know that this job is early in the constructed schedule $\sigma$. It follows that the weighted number of early jobs is ${\sum }_{j,t}{w}_j\cdot x_{j,t}$, which equals the maximization objective of $I$ and hence equals $W$. $◀$

Now we have all the pieces to prove Theorem 10.

Given an instance $I$ of $P\mid r_j,p_j=p\mid \sum w_j{U}_j$ we create an MILP instance $I^{\prime }$ as described above and use Lemma 16 to compute an optimal solution for $I$ where all variables are set to integer values. Lemmas 15 and 17 show that we can correctly compute an optimal schedule for $I$ from the solution to $I^{\prime }$ in polynomial time (in the size of $I^{\prime }$). 14 together with Lemma 16 show that this algorithm has the claimed running time upper-bound. $◀$