Minimizing total weighted completion time on a single machine subject to non-renewable resource constraints

All of the following special cases can be solved optimally by list scheduling:

The proof of optimality is left to the reader, except in the last case, that we can verify as follows. Consider any instance of \(1|nr=1,a_j={\bar{a}}\), \(w_j = \lambda p_j |\sum w_j C_j\), and let \(S^*\) be an optimal schedule in which the number of job pairs violating the LPT order is the smallest. Define \(C^*_j := S^*_j + p_j\) for each job j. Suppose that there are at least two jobs that are not in LPT order. Consider the first two such consecutive jobs, say \(j_1\) and \(j_2\), where \(j_1\) is scheduled before \(j_2\), and \(p_{j_1}+K=p_{j_2}\) for some \(K>0\). Let \(S'\) be the schedule where we swap the order of \(j_1\) and \(j_2\). We distinguish two cases.

If \(C^*_{j_1}=S^*_{j_2}\), then \(S'_{j_1} = S^*_{j_1} + p_{j_2}\), \(S'_{j_2} = S^*_{j_1}\), and \(S'_j = S^*_j\) for all \(j \notin \{j_1,j_2\}\). It is easy to verify that \(w_{j_1}(S^*_{j_1}+p_{j_1}) + w_{j_2}(S^*_{j_2} + p_{j_2}) = w_{j_2}(S'_{j_2}+p_{j_2}) + w_{j_1}(S'_{j_1} + p_{j_1})\), and the objective function does not change. Since \(S'\) is feasible, as each job has the same resource requirement, we reached a contradiction with the choice of \(S^*\).

Now suppose \(C^*_{j_1}<S^*_{j_2}\). Hence, there is an \(\ell \) such that \(S^*_{j_2}=u_\ell \). Note that we have \(S'_{j_2}=S^*_{j_1}\), \(S'_{j_1}=\max \{C'_{j_2},u_\ell \}\). Further on we have \(S'_j=S^*_{j}\) for each job j with \(S^*_j<S^*_{j_1}\), and \(S'_j\le S^*_j\) for each job j with \(S^*_j\ge S^*_{j_2}\), see Fig. 1. Notice that only the start time of job \(j_1\) increases after swapping job \(j_1\) and job \(j_2\). To reach a contradiction with the choice of \(S^*\), it is enough to prove that \(w_{j_1}C^*_{j_1}+w_{j_2}C^*_{j_2} \ge w_{j_1} C'_{j_1} +w_{j_2} C'_{j_2}\). Suppose that we have \(u_\ell =S^*_{j_1}+p_{j_1}+L\) where \(L>0\). We haveandThus, \(w_{j_1}C^*_{j_1}+w_{j_2}C^*_{j_2}-(w_{j_1}C'_{j_1}+w_{j_2}C'_{j_2})=\lambda (p_{j_1}S^*_{j_1}+(p_{j_1}+K)\cdot (p_{j_1}+L)- p_{j_1}\max \{C'_{j_2},u_\ell \})\). Since \(\max \{C'_{j_2},u_\ell \}=\max \{S^*_{j_1}+p_{j_1}+K,S^*_{j_1}+p_{j_1}+L\}\), thus \(w_{j_1}C^*_{j_1}+w_{j_2}C^*_{j_2} > w_{j_1}C'_{j_1}+w_{j_2}C'_{j_2}\) follows. \(\square \)

For any \(\lambda > 0\), the problem \(1|nr=1,p_j=1, {w_j = \lambda a_j} | \sum w_j C_j\) is weakly NP-hard even for \(q=2\).

We reduce the NP-hard PARTITION problem to our scheduling problem. An instance of the former problem is given by a natural number n, and the sizes of n items, \(s_1,\ldots , s_n\), which are nonnegative integer numbers. One has to decide whether the items can be partitioned into two subsets, \(Q_1\) and \(Q_2\), such that \(\sum _{i \in Q_1} s_i = \sum _{i\in Q_2} s_i\). Since all item sizes are integer numbers, the answer is “NO”, unless \(\sum _{i=1}^n s_i =2A\) for some integer A. Therefore, we assume that \(\sum _{i=1}^n s_i\) is an even integer, and let \(A := \sum _{i=1}^n s_i/2\). Let I be an instance of PARTITION, the corresponding instance \(I'\) of \(1|nr=1,p_j=1, {w_j = \lambda a_j} | \sum w_j C_j\) consists of n jobs, and for each item j, the corresponding job has a processing time \(p_j = 1\), \(a_j := s_j\) and \(w_j := \lambda s_j\), where \(\lambda > 0\) is fixed arbitrarily. In addition, there is a single resource with an initial stock of \(\tilde{b}_1 := A\), available at time \(u_1 := 0\), and with one more supply \(\tilde{b}_2 := A\) at time \(u_2 := n^2 A^2\).

We claim that I has a “YES” answer if and only if \(I'\) has a feasible schedule of objective function value at most \(\lambda (n^2 A^3 + 2nA)\). First suppose that I has a partitioning of the items \(Q_1, Q_2\) of equal size. Schedule the jobs corresponding to the items in \(Q_1\) from time 0 on consecutively in decreasing \(w_j\) order, and those in \(Q_2\) from \(u_2\) consecutively in decreasing \(w_j\) order. This schedule is clearly feasible. Suppose \(Q_1 = \{j_1,\ldots ,j_k\}\), and \(w_{j_i} \ge w_{j_{i+1}}\) for \(i=1,\ldots , k-1\), and \(Q_2 = \{j_{k+1},\ldots ,j_n\}\), and \(w_{j_i} \ge w_{j_{i+1}}\) for \(i=k+1,\ldots , n-1\). Then, we computeConversely, suppose the scheduling problem admits a feasible schedule S of objective function value at most \(\lambda (n^2 A^3 + 2nA)\). Let \(C_j := S_j+1\) for each job j. Let \(Q_1 = \{ j \ |\ S_j < u_2\}\) and \(Q_2 = \{ j\ |\ S_j \ge u_2\}\). Since S is feasible, the total resource consumption of those jobs in \(Q_1\) is at most A. Indirectly, suppose it is less than A. Then, the total weight of those jobs in \(Q_2\) is at least \({\lambda }(A+1)\). But then we havewhich is a contradiction.

Finally, notice that the transformation is of polynomial time complexity, which shows that there is a polynomial reduction from PARTITION to a decision version of the scheduling problem \(1|nr=1,p_j=1, {w_j = \lambda a_j} | \sum w_j C_j\). \(\square \)

If \(p_j = w_j\) for each job j, then the objective function value of any feasible schedule S can be expressed as

Consider any working period \(B=[u_\ell , t]\) in the schedule S, that is, the machine is idle right before \(u_\ell \) and right after t, and is working contiguously throughout B. Suppose \(t \in (u_{\ell '}, u_{\ell '+1}]\), where \(\ell ' \ge \ell \). Let k be an arbitrary job that is processed in B, see Fig. 2b. We have \(C_k=\sum _{C_j\le C_k}p_j+G_{\ell -1}\); thus, the total weighted completion time of the jobs processed in B iswhere the first equation follows from \(\sum _{k : C_k \in B} p_k = \sum _{\nu =\ell }^{\ell '} P_\mu \), and the second from \(G_\nu = G_{\ell -1}\) for each \(\ell \le \mu < \ell '\), since the machine is not idle in the interval B. Since the schedule can be partitioned into working and idle periods, we deriveFinally, the second equation of the statement of the lemma can be derived by using the definition of \(G_\ell \) and by rearranging terms. \(\square \)

The problem \(1|nr=1, q=2, p_j=a_j=w_j|\sum w_jC_j\) is weakly NP-hard, and \(1|nr=1, p_j=a_j=w_j|\sum w_jC_j\) is strongly NP-hard.

Recall the definition of the PARTITION problem from the proof of Theorem 2. For proving the weak NP-hardness of \(1|nr=1, q=2, p_j=a_j=w_j|\sum w_jC_j\), we reduce the PARTITION problem to this scheduling problem. For any instance of PARTITION, the corresponding instance of \(1|nr=1, q=2, p_j=a_j=w_j|\sum w_jC_j\) consists of n jobs, one job for each item, and \(p_i = a_i = w_i = s_i\) for each item \(i = 1,\ldots ,n\). There are two supplies, one at \(u_1 = 0\) and the supplied quantity from the single resource is A, and another at \(u_2 = A\) with supplied quantity A. We claim that the PARTITION problem instance has a solution if and only if the corresponding scheduling problem instance has a feasible solution of value at most \(\sum _{j\le k} p_j p_k\). Using Lemma 1, the latter holds if and only if the schedule has no idle time. So, it suffices to prove that the PARTITION problem instance has a solution if and only if the corresponding scheduling problem instance admits a feasible schedule without any idle time. First suppose that the PARTITION problem instance has a “yes” answer, i.e., there is a subset Q of items with \(\sum _{i\in Q} s_i = A\). Schedule the corresponding jobs contiguously in any order in the interval [0, A]. Since \(p_j = a_j\), and the supply at \(u_1 = 0\) is A, this is feasible. Now, schedule the remaining jobs without idle times from \(u_2 = A\). The result is a feasible schedule without idle times. Conversely, suppose there is a feasible schedule without idle times. Then, the machine is working throughout the interval [0, A]. Since the supply at \(u_1 = 0\) is A, the total processing time of the jobs starting before \(u_2 = A\) is A. Let the set Q consist of the items corresponding to these jobs. This yields a feasible solution for the PARTITION problem instance.

For proving the strong NP-hardness of \(1|nr=1, p_j=a_j=w_j|\sum w_jC_j\), we reduce the 3-PARTITION problem to this scheduling problem. Recall that an instance of 3-PARTITION consists of an positive integer t, and 3t items, each having a size \(s_i\), \(i \in \{1,\ldots ,3t\}\), where the item sizes are bounded by polynomial in the input length. It is assumed that \(\sum _{i=1}^{3t} s_i\) is divisible by t, and \(B/4< s_i < B/2\) for each i, where \(B = \sum _{i=1}^{3t} s_i / t\). The question is whether the set of items can be partitioned into t groups \(Q_1,\ldots , Q_t\) such that \(\sum _{i\in Q_\ell } s_i = B\) for \(\ell =1,\ldots ,t\). The corresponding instance of the scheduling problem \(1|nr=1, p_j=a_j=w_j|\sum w_jC_j\) has 3t jobs corresponding to the 3t items with \(p_i = a_i = w_i = s_i\), and \(q = t\) supplies at supply dates \(u_\ell = (\ell -1)B\) with supplied quantities \(b_\ell = B\) for \(\ell =1,\ldots ,q\). The rest of the proof goes along the same lines as in the first part, i.e., we argue that 3-PARTITION has a feasible solution if and only if the corresponding scheduling problem instance has a solution of objective function value \(\sum _{j\le k} p_j p_k\) if and only if there is a feasible schedule without any idle times. \(\square \)

Scheduling the jobs in LPT order is a 2-approximation algorithm for \(1|nr=1,p_j=a_j=w_j|\sum w_jC_j\).

The main idea of the following proof is that first we transform the problem data such that the resource supplies are deferred until they are used in a selected optimal schedule, and then we bound the approximation ratio of the LPT schedule. Finally, we observe that the LPT order yields at least as good a schedule with the original problem data as the same job order for the modified problem data.

Let I be any instance of the scheduling problem and fix an optimal schedule \(S^*\) for I. Let \(\mathcal {J}_\ell ^*\) be the set of jobs that start in \([u_\ell ,u_{\ell +1})\) in \(S^*\). Let \(I'\) be a new problem instance derived from I by modifying the supplied quantities (the other problem data do not change): \(b'_1:=\sum _{j\in \mathcal {J}_1^*}a_j\) and for each \(\ell \ge 2\), \(b'_\ell :=\sum _{\nu =1}^\ell \sum _{j\in \mathcal {J}_\nu ^*}a_j-\sum _{\nu =1}^{\ell -1}b'_{\nu }\). \(\square \)

\(I'\) has the following properties:

The first two claims are straightforward consequences of the definitions, while (iii) and (iv) both follow from the fact that in \(I'\) the resource supplies are deferred with respect to I. \(\square \)

If \(\tilde{P}^{LPT}_\ell > 0\), i.e., the machine is idle just before \(u_\ell \), and a job \(j(\ell )\) is started at \(u_\ell \) in \(S^{LPT}\), then

If \(\sum _{\nu =1}^{\ell -1} \tilde{P}^{LPT}_\nu + p_{j(\ell )}\le \sum _{\nu =1}^{\ell -1}b_\nu \) were true, then \(j(\ell )\) could be scheduled earlier in \(S^{LPT}\). Thus, we have \(\sum _{\nu =1}^{\ell -1} \tilde{P}^{LPT}_\nu + p_{j(\ell )}> \sum _{\nu =1}^{\ell -1}b_\nu \). Since we have \(\sum _{\nu =1}^{\ell -1} P^*_\nu \le \sum _{\nu =1}^{\ell -1}b_\nu \), (i) follows. The second inequality of (i) follows from \(\sum _{\nu =1}^q \tilde{P}^{LPT}_\nu =\sum _{\nu =1}^q P^*_\nu \). Finally, (ii) follows from \(\sum _{\nu =1}^{\ell -1}\tilde{P}^{LPT}_{\nu }+ G^{LPT}_{\ell -1}=u_\ell =\sum _{\nu =1}^{\ell -1} P_\nu ^*+G^*_{\ell -1}\). \(\square \)

First we prove the claim for each \(\ell \) such that \(\tilde{P}^{LPT}_\ell \ne 0\). Consider such an \(\ell \). If \(\sum _{\mu =\ell }^q P^*_\mu \) were less than \(p_{j(\ell )}\), then each job with a processing time at least \(p_{j(\ell )}\) would be scheduled before \(u_\ell \) in \(S^*\); thus, \(\sum _{\nu =1}^{\ell -1}b'_\nu \) would be at least the total processing time of these jobs. However, this would mean that \(j(\ell )\) could be scheduled earlier (recall that the machine is idle just before \(u_\ell \) in \(S^{LPT}\)); thus, we have \(\sum _{\mu =\ell }^q P^*_\mu \ge p_{j(\ell )}\). Since \(\tilde{P}^{LPT}_\ell \ne 0\), we can use Claim 2 (i) and we haveNow suppose that \(\tilde{P}^{LPT}_\ell =0\). If \(\sum _{\mu =\ell }^{q} \tilde{P}^{LPT}_{\mu }=0\), then the claim is trivial. Otherwise, let \(\ell '>\ell \) be the smallest index such that \(\tilde{P}^{LPT}_{\ell '}\ne 0\). Since we know that the claim is true for \(\ell '\), we haveand we are ready. \(\square \)

The above algorithm is a PTAS for \(1|nr=1, p_j = w_j, q= const|\sum w_j C_j\).

Let I be any instance of the scheduling problem and \(S^*\) an optimal solution for I. Let \({\hat{P}}^*_\ell \) be the total processing time of those jobs starting after \(u_\ell \) in \(S^*\). Clearly, \({\hat{P}}^*_\ell \ge {\hat{P}}^*_{\ell +1}\) for \(\ell =1,\ldots ,q-1\). Consider the guess \(P^g_2,\ldots ,P^g_q\) in Step 1 of our algorithm such that \({\hat{P}}^*_\ell \le P^g_{\ell } < \varDelta {\hat{P}}^*_\ell \) for each \(\ell =2,\ldots ,q\). Such a guess must exist by the definition of guesses.

For each \(\ell =1,\ldots ,q\), let us partition the set of jobs that start in the interval \([u_\ell , u_\ell +1)\) in the schedule \(S^*\) into subsets \(T^*_\ell \subseteq \mathcal{M}_\ell \) and \(K^*_\ell \subseteq \mathcal{S}_\ell \). Clearly, the sets \(T^*_\ell \) are disjoint, and the cardinality of each \(T^*_\ell \) is at most \(1/(\varDelta -1)\), since \(P^g_\ell \ge P^*_\ell \), and thus each job in \(T^*_\ell \) is of size at least \((\varDelta -1)P^g_\ell \ge (\varDelta -1){\hat{P}}^*_\ell \), while the total size of all the jobs starting after \(u_\ell \) in \(S^*\) is \({\hat{P}}^*_\ell \) by definition. Therefore, the algorithm will enumerate and process the choice \((T^*_1,\ldots ,T^*_q)\) in Step 2. In the rest of the proof, we fix this choice of large jobs. After scheduling them in Step 3, the resulting schedule is like \(S^*\), except that some jobs may be yet unscheduled. Thus, we perform Step 4, and let \(S^A\) be the resulting schedule. In Step 4, the algorithm will find sets of jobs \(K_1,\ldots ,K_q\), and it may well be the case that \(K^*_\ell \ne K_\ell \) for some \(\ell \), but we know that \(\bigcup _{\ell =1}^q K_\ell = \bigcup _{\ell =1}^q K^*_\ell \), since in \(S^*\) and \(S^A\), for each \(\ell \), the same subset \(T^*_\ell \) of \(\mathcal{M}_\ell \) is chosen. We will prove that \(S^A\) is a feasible schedule and that its objective function value is at most \(1+O(\varepsilon )\) times the optimum.

The total processing time of those jobs that start after \(u_\ell \) in \(S^*\) and in \(S^A\), respectively, satisfies the inequalities

First notice that for each \(\ell = 2,\ldots ,q\), we have \(\cup _{\ell '=\ell }^q K^*_{\ell '} \subseteq \mathcal{S}_\ell \backslash \left( \bigcup _{\ell '=\ell +1}^q T^*_{\ell '} \right) \), since \(K^*_{\ell '} \subseteq \mathcal{S}_{\ell '} \subseteq \mathcal{S}_\ell \) and \(T^*_{\ell '}\cap K^*_{\ell '} = \emptyset \) for \(\ell '\ge \ell \), and similarly, \(\cup _{\ell '=\ell }^q K_{\ell '} \subseteq \mathcal{S}_\ell \backslash \left( \bigcup _{\ell '=\ell +1}^q T^*_{\ell '} \right) \). We prove (3) by induction. Along with (3), we will also provewhere we define \(P^g_{q+1} := 0\). The base case is for \(\ell =q+1\), when all the inequalities trivially hold (we define \({\hat{P}}^*_{q+1} := 0\)). Now suppose that (3) and (4) hold for \(\ell +1\) for some \(\ell \ge 2\), and we verify them for \(\ell \).

First suppose that \(p(K_\ell ) + p(T^*_\ell ) \ge P^g_\ell - (1/\varDelta )P^g_{\ell +1}\). Since \({\hat{P}}^*_\ell - {\hat{P}}^*_{\ell +1}\) equals the total processing time of those jobs that start in the interval \([u_\ell , u_{\ell +1})\) in \(S^*\), and \({\hat{P}}^*_{\ell } \le P^g_\ell < \varDelta {\hat{P}}^*_\ell \), we haveSo, the induction hypothesis implies the first inequality in (3). To verify the second one, recall that in Step 4 we stop selecting jobs as soon as \(p(T^*_\ell ) + p(K_\ell )\) exceeds \(P^g_\ell - (1/\varDelta ) P^g_{\ell +1}\), and the processing time of all jobs in \(\mathcal{S}_\ell \) is bounded by \((\varDelta -1) P^g_\ell \), which implies (4) for \(\ell \), sinceUsing the induction hypothesis, we obtainA simple calculation shows that \(\varDelta ^2< 1+3(\varepsilon /q^2) < 1+(\varepsilon / q)\) (since \(q \ge 3\) by assumption); therefore, the right-hand side of (6) is less than \((1+(\varepsilon /q)) P^g_\ell + 3(\varepsilon /q^2)\sum _{\ell '=\ell +1}^q P^g_{\ell '} \le (1+ 4 (\varepsilon /q))P^g_\ell \). Since \(P^g_\ell < \varDelta {\hat{P}}^*_\ell \), and \((1+ 4 (\varepsilon /q)) \varDelta < 1+6 (\varepsilon /q)\) (since \(q\ge 3\) by assumption), the second inequality in (3) follows.

Now suppose \(K_\ell = \mathcal {J}^u_{q-\ell } \cap \mathcal{S}_\ell \) and \(p(K_\ell ) + p(T^*_\ell ) < P^g_\ell - (1/\varDelta )P^g_{\ell +1}\) in Step 4 of the algorithm at iteration \(\ell \). Then, we deduce that in \(S^A\), all the small jobs in \(\mathcal{S}_\ell \backslash \left( \bigcup _{\ell '=\ell +1}^q T^*_{\ell '} \right) \) are scheduled after \(u_\ell \) in the iterations \(\ell ,\ldots ,q\), while in \(S^*\), some jobs of \(\mathcal{S}_\ell \backslash \left( \bigcup _{\ell '=\ell +1}^q T^*_{\ell '} \right) \) may be started before \(u_\ell \). Therefore, the first inequality in (3) holds in this case as well. To verify the second inequality in (3), note that since \(p(K_\ell ) + p(T^*_\ell ) < P^g_\ell - (1/\varDelta )P^g_{\ell +1}\) by assumption, (4) follows immediately. Then, using the induction hypothesis, we obtain (6), and then the same argument applies as above. \(\square \)

There exists a unique \(t \in \{0,\ldots ,n_1\}\) such that

If \(\bigcup _{\ell '=\ell }^q K_{\ell '}\) is the empty set, then \(t = 0\) will do. Otherwise, let t be the maximum element in \(\bigcup _{\ell '=\ell }^q K_{\ell '}\). Indirectly, suppose there exists some \(t'<t\) such that \(t' \not \in \bigcup _{\ell '=\ell }^q K_{\ell '}\), but \(t'\in \mathcal{S}_\ell \backslash \bigcup _{\ell '=\ell }^q T^*_{\ell '}\). Then, at some iteration in Step 4 of the algorithm, t would be chosen in place of \(t' < t\), which is a contradiction. \(\square \)

For the job index t defined in Claim 5,

For each \(t=1,\ldots ,n_1\), and \(2\le \ell \le q\), we have

We proceed by induction, the base case being for \(\ell =q\). Then, \(K_q, K^*_q \subseteq \mathcal{S}_q\). If \(K_q\) is a proper subset of \(\mathcal{S}_q\), then we have \(p(K^*_q) \le p(K_q)\) by (5). Otherwise, \(K_q = \mathcal{S}_q \supseteq K^*_q\), and we have \(p(K^*_q) \le p(K_q)\) in this case, too. For the sake of a contradiction, suppose there exists \(1\le t\le n_1\) such that (8) does not hold. Let t be the smallest such job index. Then, job \(t \in K^*_q \backslash K_q\); otherwise, t could be decreased. Then, \(K_q\) does not contain any job v with \(v > t\); otherwise, before picking v, the algorithm would have picked t. But thenwhich is a contradiction.

Now assume by induction that (8) holds for \(\ell = k+1\), with \(k\ge 2\), and for all \(1\le t\le n_1\), and we check it for \(\ell =k\). We distinguish two cases.

For each \(\ell = 2,\ldots ,q\), we have

\(H^A_{\ell } \le H^*_\ell + (6\varepsilon /q) {\hat{P}}^*_{\ell +1}\).

Observe that in \(S^A\) at most \((6\varepsilon /q) {\hat{P}}^*_{\ell +1}\) more work is scheduled after \(u_{\ell +1}\) than in \(S^*\) by inequality (3). Therefore, the total gap in \(S^A\) before \(u_{\ell +1}\) is at most \((6\varepsilon /q) {\hat{P}}^*_{\ell +1}\) more than in \(S^*\), i.e.,On the other hand, \(G^*_{\ell -1} \le G^A_{\ell -1}\), since in \(S^A\), \(\sum _{\ell '=\ell }^q (p(T^*_{\ell '})+p(K_{\ell '})) \ge {\hat{P}}^*_\ell \) by (3). Now, using the fact that \(G^A_\ell = G^A_{\ell -1} + H^A_\ell \), we obtain\(\square \)