Throughput Maximization in a Scheduling Environment with Machine-Dependent Due-Dates

We reduce the problem to a weighted maximum matching problem in a bipartite graph. Given an instance $⟨J,M,{\{r_j\}}_{j\in J},{\{d_j\}}_{j\in J},\omega ⟩$, of our scheduling problem, construct a weighted bipartite graph $(V\cup U,E)$. The set $V$ includes $n$ job-vertices, $\{v_j\}$ for every job $1\le j\le n$. The set $U$ includes $mn$ slot-vertices, $\{u_i^{\mathrm{\ell }}\}$, for each $1\le \mathrm{\ell }\le n$ and machine $i\in M$. The set of edges is . That is, every job-vertex is connected to all the slot-vertices corresponding to a feasible assignment of $j$ with regards to release time and due-date. The weight of an edge $(v_j,u_i^{\mathrm{\ell }})$ is ${\omega }_{j,i}$.

It is easy to see that every schedule with total reward $W$ corresponds to a matching of total weight $W$. Also, every feasible matching of weight $W$ induces a valid schedule. All jobs in this schedule are scheduled after their release time and before their due-date, and their total reward is $W$. As a maximum weight matching can be found efficiently, and the reduction is polynomial, the whole algorithm is polynomial.

Note that machines may have idle slots in the produced schedule. The number of idle blocks can be minimized by shifting earlier jobs with early release times. Some idles may be unavoidable due to the release times. $◀$

In order to prove APX-hardness, we use an $L$-reduction [16], defined as follows:

Our $L$-reduction is from $3$-bounded $3$-dimensional matching ($3$DM$3$). The input to the problem is a set of triplets $T\subseteq X\times Y\times Z$, where $|X|=|Y|=|Z|=k$. The number of occurrences of every element of $X\cup Y\cup Z$ in $T$ is at most $3$. The number of triplets is $|T|=m$. The goal is to find a maximal subset $T^{\prime }\subseteq T$, such that every element in $X\cup Y\cup Z$ appears at most once in $T^{\prime }$. This problem is known to be APX-hard [9]. Moreover, a stronger hardness result shows the problem has an hardness gap even on instances with a matching of size $k$ [17], namely instances where there is a solution with $k$ triplets.

Given an instance $T$ of $3$DM$3$, we construct an instance $f(T)$ of SMDD. For each triplet containing element $x\in X$, we say it is a triplet of type $x$. Let $t_x$ be the number of triplets of type $x$. For each triplet, there is a corresponding machine $i$ for a total of $m$ machines.

There are $2k$ element jobs, one for each element $y\in Y$, and one for each element $z\in Z$. A job $j_y$ corresponding to an element $y\in Y$ has $d_{i,j_y}=1$ if $y\in T_i$ where $T_i$ is the triplet corresponding to machine $i$, and $d_{i,j_y}=0$, otherwise. A job $j_z$ corresponding to an element $z\in Z$ has $d_{i,j_z}=2$ if $z\in T_i$ where $T_i$ is the triplet corresponding to machine $i$, and $d_{i,j_z}=0$ otherwise. For every such element job $j$, $p_j=1$.

For every $x\in X$, there are $t_x-1$ dummy jobs $j_x$ such that $d_{i,j_x}=2$ if $x\in T_i$ where $T_i$ is the triplet corresponding to machine $i$, and $d_{i,j_x}=0$ otherwise. Note that there is one dummy job for all but one of the $t_x$ machines corresponding to triplets of type $x\in X$, for a total of $m-k$ dummy jobs. For every dummy job $j$, $p_j=2$.

In order to complete the $L$-reduction, we prove the conditions of Definition 3 are met. As a preliminary, we show that if $T$ has a matching $T^{\prime }$ of size $k$, then $OPT(f(T))=m+k$. For a schedule $s$, let $sat(s)={\sum }_j(1-U_j)$ be its throughput.

Let $T^{\prime }$ be a matching of size $k$. For each triplet $(x,y,z)\in T^{\prime }$, we can schedule the jobs corresponding to $y,z$ on the machine corresponding to the triplet. Note that both jobs are satisfied. This leaves $t_x-1$ idle machines to which dummy jobs corresponding to $x$ can be assigned with completion time $2$. Thus, we have a schedule in which $m-k$ dummy jobs are satisfied, and $2k$ element jobs are satisfied for a total of $m+k$ satisfied jobs, proving $sat(OPT(f(T))\ge m+k$. As there are no additional jobs, $sat(OPT(f(T))=m+k$.

Given a schedule $s$, let $g(s)$ be the set of triplets corresponding to machines on which two jobs are assigned. The theorem follow from the following claims, showing that Definition 3 is satisfied for $\alpha =4$ and $\beta =1$.

Since every element of $X\cup Y\cup Z$ appears at most $3$ times in $T$, $m\le 3k$. Thus, $OPT(f(T))=m+k\le 3k+k=4k$. $\mathrm{⊲}$

Since we assume that $T$ has a perfect matching, we have that $OPT(T)=k$. Since we proved that $value(OPT(f(T))=m+k$, it is sufficient to prove that $k-g(s)\le m+k-value(s)$. Consider a schedule $s$ of $f(T)$. Recall that every machine has $0,1$ or $2$ jobs assigned to it. Thus, $sat(s)\le 2g(s)+(m-g(s))=m+g(s)$. Therefore, $k-g(s)\le m+k-sat(s)\le m+k-(m+g(s))=k-g(s)$ as needed. $\mathrm{⊲}$ $◀$

Consider $5$ jobs $\{j_1,\mathrm{\dots },j_5\}$, such that $p_1=p_2=1$, $p_3=p_4=p_5=2$, $d_1=d_2=2$, and $d_3=d_4=d_5=4$. There are $2$ machines. In an optimal schedule all jobs are satisfied, for example by assigning $j_1,j_2,j_3$ to one machine, and $j_4,j_5$ to the other. However if the jobs are assigned to lightly loaded machines in EDD order, $j_1$ and $j_2$ are assigned to different machines, and only $4$ jobs are assigned in the resulting schedule.

The next example demonstrates that a greedy approach in which the jobs are considered in EDD order and each job is assigned to a most loaded machine on which it is non-tardy, is sub-optimal. Consider $4$ jobs $\{j_1,\mathrm{\dots },j_4\}$, such that $p_1=p_2=1$, $p_3=p_4=2$, $d_1=d_2=2$, and $d_3=d_4=3$. There are $2$ machines. In an optimal schedule all jobs are satisfied, for example by assigning $j_1,j_3$ to one machine, and $j_2,j_4$ to the other. However if the jobs are assigned to a most loaded feasible machine in EDD order, $j_1$ and $j_2$ are assigned to one machine, and only one of the longer jobs can be satisfied.

Note that the above examples are valid regardless of tie breaking between jobs having the same due-date.

Instead, in our algorithm, if there are multiple machines to which $j$ can be assigned without being late, we maintain all possibilities for the loads of the machines after its assignment. In order to maintain a polynomial runtime, we only consider assignments to machines such that the difference in loads between any two machines is at most $2$. Formally, we assume that after a job is assigned, for every machine $i$, its load is in $\{L,L-1,L-2\}$ for some value $L$. We can then store all possibilities of machine loads using a dynamic programming approach, with an $n\times n\times (n^3)$ table $S$ for all possible load options after a job is considered.

Formally, the DP table includes boolean values such that $S[j;L;x_0,x_1,x_2]=True$ if and only if there exists a schedule of the first $j$ jobs in the EDD order such that, for $z\in \{0,1,2\}$, exactly $x_z$ machines have load $L-z$, where $L$ is the only integer for which ${\sum }_{\mathrm{\ell }=1}^j{p}_{\mathrm{\ell }}=x_{0}L+x_1(L-1)+x_2(L-2)$, such that $x_0,x_1,x_2$ are integers, and $x_0>0$ (that is, the most loaded machine has load $L$). No machine has load higher than $L$ or lower than $L-2$. Note that for every choice of $j,x_0>0,x_1,x_2$, there is a unique value of $L$ for which $S[j;L;x_0,x_1,x_2]$ may be true. Thus, the table can be constructed without the $L$-dimension, resulting in a $n\times (n^3)$ table. In the sequel, we include the value of $L$ in the table $S$ for clarity.

Initially, $S[0;0;m,0,0]=True$, and for every other value of $x_0,x_1,x_2$, $S[0;0;x_0,x_1,x_2]=False$. That is, before any jobs are considered, the only possible schedule is of $m$ machines with load $0$.

For $j>0$, consider first the case $p_j=1$. The table $S$ is updated as follows:

1. 1.

   If $x_2>0$ and $S[j-1;L;x_0,x_1,x_2]=True$, then $S[j;L;x_0,x_1+1,x_2-1]=True$. This corresponds to adding $j$ to a machine with load $L-2$. Note that since the jobs are sorted in EDD order, it must be that $d_j\ge L>L-1$, so $j$ is satisfied.

2. 2.

   If $x_1>0$ and $S[j-1;L;x_0,x_1,x_2]=True$, then $S[j;L;x_0+1,x_1-1,x_2]=True$. This corresponds to adding $j$ to a machine with load $L-1$. Note that since the jobs are sorted in EDD order, it must be that $d_j\ge L$, so $j$ is satisfied.

3. 3.

   If $d_j\ge L+1$, $x_0>0$, and $S[j-1;L;x_0,x_1,0]=True$, then $S[j;L+1;1,x_0-1,x_1]=True$. This corresponds to adding $j$ to a machine with load $L$. Note that we only consider this if no machines have load $L-2$ when $j$ is considered, thus maintaining a maximum difference of $2$ between the loads of different machine.

For $j>0$, and $p_j=2$, the table $S$ is updated as follows:

1. 1.

   If $x_2>0$ and $S[j-1;L;x_0,x_1,x_2]=True$, then $S[j;L;x_0+1,x_1,x_2-1]=True$. This corresponds to adding $j$ to a machine with load $L-2$. Note that since the jobs are sorted in EDD order, $d_j\ge L$, so $j$ is satisfied.

2. 2.

   If $d_j\ge L+1$, $x_1>0$, and $S[j-1;L;x_0,x_1,0]=True$, then $S[j;L+1;1,x_0,x_1-1]=True$. This corresponds to adding $j$ to a machine with load $L-1$. Note that we only consider this if no machines have load $L-2$ when $j$ is considered, thus maintaining a maximum difference of $2$ between the loads of different machines.

3. 3.

   If $d_j\ge L+2$, $x_0>0$, and $S[j-1;L;x_0,0,0]=True$, then $S[j;L+2;1,0,x_0-1]=True$. This corresponds to adding $j$ to a machine with load $L$. Note that we only consider this if no machines have load $L-2$ or $L-1$ when $j$ is considered, thus maintaining a maximum difference of $2$ between the loads of different machines.

We are now ready to describe the algorithm for $P|p_j\in \{1,2\}|{\sum }_j(1-U_j)$.

We first justify the fact that the table $S$ considers only partial assignments of jobs in EDD order, in which the maximal gap in the loads of different machines is $2$.

Consider an optimal schedule $O$. Simple exchange argument implies the first property in the claim, that is, the jobs assigned to each machine in $O$ are sorted in EDD order. Therefore, we can assume $O$ is constructed by iterating over jobs in EDD order, and assigning the jobs one after the other with no intended idle. Assume by contradiction that there is some job such that after it is assigned to machine $i$, there is a machine $i^{\prime }$ such that $L_i-L_{i^{\prime }}>2$. Let $j_0$ be the first job for which this occurs.

Let $A$ be the set of jobs considered after $j_0$ that are assigned to $i$, and let $B$ be the set of jobs considered after $j_0$ that are assigned to $i^{\prime }$. If $B\ne \mathrm{\varnothing }$, let $j_1$ be the first job in $B$. We describe how to convert $O$ to another schedule, $O^{\prime }$, in which all the jobs are satisfied and the gap between $i$ and $i^{\prime }$ reduces to at most $2$.

For jobs considered before $j_0$, they are assigned to the same machine as in $O$. $j_0$ is assigned to $i^{\prime }$ instead of $i$, and since the jobs are sorted in EDD order, it remains satisfied. We prove there is a valid assignment of the remaining jobs. For a job assigned to a machine other than $i$ or $i^{\prime }$ in $O$, it is assigned to the same machine in $O^{\prime }$, and is clearly satisfied. For jobs in $A\cup B$, we divide into cases. A visual description of the constructed assignment is given in Figure 1.

1. 1.

   If $B=\mathrm{\varnothing }$, we assign all jobs in $A$ to $i$. They are clearly satisfied as the load on $i$ in $O^{\prime }$ after a job is considered, is lower than the load on $i$ in $O$ after the same job is considered.

2. 2.

   If $p_{j_0}=p_{j_1}$, assign $j_1$ to $i$, all jobs in $A$ to $i$, and all jobs in $B\setminus \{j_1\}$ to $i^{\prime }$. $j_1$ is satisfied since the jobs are sorted in EDD order. All remaining jobs are satisfied as they are processed at the same time in $O$ and $O^{\prime }$.

3. 3.

   If $p_{j_0}=2$ and $p_{j_1}=1$. If $B=\{j_1\}$, assign $j_1$ to $i$ and all jobs in $A$ to $i$, and clearly all jobs are satisfied. Otherwise, let $j_2$ be the second job in $B$.

   If $p_{j_2}=1$, assign $j_1$ and $j_2$ to $i$, and all jobs in $A$, $B\setminus \{j_1,j_2\}$ to $i$, $i^{\prime }$ respectively. If $p_{j_2}=2$, assign $j_1$ to $i^{\prime }$, $j_2$ to $i$, and all jobs in $A$, $B\setminus \{j_1,j_2\}$ to $i$, $i^{\prime }$ respectively. $j_1,j_2$ are satisfied since the jobs are sorted in EDD order, and the remaining jobs are satisfied as they are processed at the same time in $O$, $O^{\prime }$.

4. 4.

   If $p_{j_0}=1$ and $p_{j_1}=2$, since $j_0$ is the first job such that $L_i-L_{i^{\prime }}>2$ after its assignment, we have $L_i-L_{i^{\prime }}=3$. Thus, when $j_0$ is assigned to $i^{\prime }$ instead of $i$, $L_i-L_{i^{\prime }}=1$. We assign $j_1$ to $i^{\prime }$, all jobs in $A$ to $i^{\prime }$, and all jobs in $B\setminus \{j_1\}$ to $i$.

   $j_1$ is satisfied as the jobs are sorted in EDD order. Since the due-dates are not machine-dependent, and all jobs in $A$, $B\setminus \{j_1\}$ are processed at the same time in $O$ and $O^{\prime }$, they are also satisfied in $O^{\prime }$.

Note that $O^{\prime }$ is an optimal schedule with the same assigned jobs as $O$. Additionally, after $j_0$ is assigned the difference in loads between machines is at most $2$. Therefore, by repeating this procedure we arrive at an optimal schedule such that the gap between machine loads is at most $2$ after each job is assigned. $\mathrm{⊲}$

Let $O$ be an optimal schedule fulfilling the conditions specified in Claim 7. Assume that for each $p\in \{1,2\}$, there are $k_p^{\star }$ satisfied $p$-jobs in $O$. Recall that we can assume these jobs are the $k_p^{\star }$ $p$-jobs with maximal due-date.

Consider Algorithm 1 for a guess of $k_1^{\star },k_2^{\star }$ jobs with length $1,2$, respectively. The jobs in Algorithm 1 are assigned in EDD order, and by the definition of $S$, a valid assignment of $k_1^{\star }+k_2^{\star }$ jobs will be constructed. $◀$

Algorithm 1 is for the specific case $p_j\in 𝒫=\{1,2\}$ for every $j$. For other integer values of $𝒫$, it is possible to generalize Algorithm 1 to an algorithm for $P|p_j\in 𝒫|{\sum }_j(1-U_j)$ that has a running time of $n^{O(|𝒫|lcm(𝒫))}$.

The generalization is based on the fact that regardless of $𝒫$, every instance has an optimal schedule in which the internal order of jobs on any machine is EDD, and the fact that if we can bound the maximal gap between the loads of different machines, then it is simple to extend the dynamic programming table $S$ to consider all partial schedules.

We generalize Claim 7 and show that for any $𝒫$, there exists an optimal assignment in which the maximal gap between any two machines is $lcm(𝒫)\cdot (|𝒫|+1)$. The idea is to consider $j_0$, the first job such that after it is placed, $L_i-L_{i^{\prime }}>lcm(𝒫)\cdot (|𝒫|+1)$. Consider the set $A$ of jobs of total processing time at least $lcm(𝒫)\cdot |𝒫|$ most recently processed on $i$ when $j_0$ is assigned. Note that $j_0\in A$. As there are only $|𝒫|$ different job sizes and they all divide $lcm(𝒫)$, there must be a subset of jobs $A^{\prime }\subseteq A$ with total length exactly $lcm(𝒫)$ in $A$.

Let $B$ be the minimal set of jobs with total processing time at least $lcm(𝒫)\cdot |𝒫|$ assigned to $i^{\prime }$ after $j_0$ is considered. As there are only $|𝒫|$ different job sizes and they all divide $lcm(𝒫)$, there must be a subset of jobs $B^{\prime }\subseteq B$ with total processing time exactly $lcm(𝒫)$. We assign the jobs in $A^{\prime }$ to $i^{\prime }$, and the jobs in $B^{\prime }$ to $i$.

As the jobs are considered in EDD order, they are all satisfied. All jobs assigned later are assigned to the same time slot, so they remain satisfied. By repeating this procedure, we are left with a schedule with a maximal gap of $lcm(𝒫)\cdot (|𝒫|+1)$.

Thus, we can conclude the following.