Scheduling with non-renewable resources: minimizing the sum of completion times

Scheduling problems with non-renewable resource constraints arise naturally in various areas where resources like raw materials, energy, or financial funding arrive at predetermined dates. In the general setting, we are given a set of jobs and a set of machines. Each job is equipped with a requirement vector that encodes the needs of the given job for the different types of resources. There is an initial stock for each resource, and some additional resource arrival times in the future are known together with the arriving quantities. The aim is to find a schedule of the jobs on the machines such that the necessary resources are available for each job when their processing begins.

We will use the standard \(\alpha |\beta |\gamma \) notation of Graham et al. (1979). Grigoriev et al. (2005) extended this notation by adding the restriction \(rm=r\) to the \(\beta \) field, meaning that there are r resources (rm stands for ‘raw materials’). In the present paper, we concentrate on problem with a single machine and a single resource, where the objective is to minimize the weighted sum of completion times, i.e., \(1|rm=1|\sum w_jC_j\). While there is an abundance of results on the approximability of the makespan objective, much less is known about the complexity and approximability of the total weighted completion time objective.

Related work Scheduling problems with resource restrictions (also called financial constraints, or raw material requirements) were introduced by Carlier and Kan (1982) and by Slowiński (1984). Carlier (1984) settled the computational complexity of several variants for the single machine case. In particular, he showed that \(1|rm=1|\sum w_jC_j\) is NP-hard in the strong sense. This was also proved independently by Gafarov et al. (2011). Kis (2015) showed that the problem remains weakly NP-hard even when the number of resource arrival times is 2. On the positive side, he gave an FPTAS for \(1|rm=1,q=2|\sum w_jC_j\). A variant of the problem where each job has processing time 1, there are \(q=n\) resource arrival times such that \(t_i=iM\) and \(b_i=M\) for \(i=1,\dots ,n\), and \(M=\sum _{j\in J} a_j/n\) is an integer, was considered in Gafarov et al. (2011). Györgyi and Kis (2019) gave polynomial time algorithms for several special cases, and also showed that the problem remains weakly NP-hard even under the very strong assumption that for each individual job, the processing time, the resource requirement and the weight are equal. They also provided a 2-approximation algorithm for this variant, and a polynomial-time approximation scheme (PTAS) for the variant where the number of resource arrival times is a constant and the processing time equals the weight for each job, while the resource requirements are arbitrary.

Independently of the present paper, Györgyi and Kis (2020) recently published an analysis of simple greedy algorithms for several variants of the problem. They also showed that minimizing the sum of completion times is NP-hard even for two resource arrival times and unit resource requirements, and provided a FPTAS for a variant in which the jobs have arbitrary weights, but the number of resource arrival times is bounded by a constant. None of our results are implied by their paper.

In comparison to total weighted completion time, much more is known about the maximum makespan and maximum lateness objectives. Slowiński (1984) studied the preemptive scheduling of independent jobs on parallel unrelated machines with the use of additional renewable and non-renewable resources under financial constraints. Toker et al. (1991) examined a single-machine scheduling problem under non-renewable resource constraint, using the makespan as a performance criterion. Xie (1997) generalized this result to the problem with multiple financial resource constraints. Grigoriev et al. (2005) presented polynomial time algorithms, approximations and complexity results for single-machine scheduling problems with unit or all-equal processing times and maximum lateness and makespan objectives. In a series of papers (Györgyi & Kis, 2014, 2015a, b, 2017, Györgyi, 2017), Györgyi and Kis presented approximation schemes and inapproximability results both for single and parallel machine problems with the makespan and the maximum lateness objectives. In Györgyi and Kis (2018), they proposed a branch-and-cut algorithm for minimizing the maximum lateness.

Our results We first consider the problem \(1|rm=1,a_j=1|\sum C_j\). The complexity of this problem was posed as an open question in Györgyi and Kis (2018). We show that the problem is NP-hard in the strong sense.

In the light of Theorem 1, one might be interested in finding an approximation algorithm for the problem. Given any scheduling problem on a single machine, the Shortest Processing Time First (SPT) schedule orders the jobs by increasing order of processing times. We prove that \(\textsf{spt}\) provides a 3/2-approximation. Although the algorithm is very simple as it is merely scheduling according to the SPT order, the analysis of the approximation factor is rather involved.

The second problem considered is the special case when the processing time is 0 for every job. This setting is relevant to situations where processing times are negligible compared to the gaps between resource arrival times, and the bottleneck is resource availability. Examples include financial scheduling problems where the jobs are not time consuming but the availability of funding varies in time, or production problems where products are shipped at fixed time intervals and production time is negligible compared to these intervals. Note that the number of machines is irrelevant if processing times are 0. First we describe a fast and simple greedy approximation algorithm for the problem.

After the proof of Theorem 3, we give a slightly more complicated \((4+\varepsilon )\)-approximation that illustrates one of the important ideas of the general PTAS.

As a next step toward the main result, we present a PTAS for the case of a constant number of resource arrival times. This procedure will be used as a subroutine in our algorithm for the general case.

The main contribution of the paper is a PTAS for the same problem with an arbitrary number of resource arrival times.

Finally, we consider a variant of \(1|rm=1,p_j=0|\sum C_jw_j\) where the number of resource arrival times and the arriving quantities (in the order of the arrivals) are known, but the arrival times are unknown. We denote this problem by \(1|rm=1, p_j=0, t_i\ \text {unknown}|\sum C_jw_j\). We observe that the greedy 6-approximation algorithm of Theorem 3 is actually a 6-approximation for this problem, too. We can improve the approximation factor to get the following tight result.

Organization The rest of the paper is organized as follows. Basic notation and terminology are introduced in Sect. 2. A strong NP-hardness proof and a 3/2-approximation algorithm for problem \(1|rm=1,a_j=1|\sum C_j\) are given in Sect. 3. Results on problem \(1|rm=1,p_j=0|\sum C_j\) are discussed in Sect. 4, where a greedy 6-approximation, a PTAS for the case of constant resource arrival times, and a PTAS for the general case are presented. We close the paper in Sect. 5 by analyzing the variant where the resource arrival times are unknown.

Throughout the paper, we will use the following notation. We are given a set J of n jobs. Each job \(j\in J\) has a non-negative integer processing time \(p_j\), a non-negative weight \(w_j\), and a resource requirement \(a_j\). The resources arrive at time points \(t_1,\dots ,t_q\), and the amount of resource that arrives at \(t_i\) is denoted by \(b_i\). We might assume that \(\sum _{i=1}^q b_i = \sum _{j=1}^n a_j\) holds. We will always assume that \(t_1=0\), as this does not affect the approximation ratio of our algorithms. We will use the notation \(B_k=\sum _{i \ge k} b_i\) for the amount of resource that arrives no earlier than \(t_k\).

The jobs should be processed non-preemptively on a single machine. A schedule is an ordering of the jobs, that is, a mapping \(\sigma : J \rightarrow [n]\), where \(\sigma (j)=i\) means that job j is the ith job scheduled on the machine. The completion time of job j in schedule \(\sigma \) is denoted by \(C^\sigma _j\). We will drop the index \(\sigma \) if the schedule is clear from the context. In any reasonable schedule, there is an idle time before a job j only if there is not enough resource left to start j after finishing the last job before the idle period. Hence, the completion time of job j is determined by the ordering and by the resource arrival times, as j will be scheduled at the first moment when the preceding jobs are already finished and the amount of available resource is at least \(a_j\).

A different representation of schedules will be used in Sect. 4, where the processing times are assumed to be 0. In this case, every job is processed at one of the resource arrival times in any reasonable schedule. Hence, a schedule can be represented by a mapping \(\pi : J \rightarrow [q]\), where \(\pi (j)\) denotes the index of the resource arrival time when job j is processed.

In this section we consider the problem \(1|rm=1,p_j=0|\sum C_jw_j\), another special case of \(1|rm=1|\sum C_jw_j\). The problem clearly is NP-hard even for \(q=2\) as the knapsack problem can be reduced to it. Indeed, maximizing the weight of the items in the knapsack is equivalent to the task of maximizing the weight of jobs that are scheduled at the first resource arrival time. Recall that Kis (2015) gave a FPTAS for \(1|rm=1|\sum C_jw_j\) when there are two resource arrival times.

First we give a 6-approximation for the problem based on a greedy approach. We also describe a more complicated \((4+\varepsilon )\)-approximation that illustrates one of the important ideas of the more general PTAS. Then we provide a PTAS for the case when q, the number of resource arrival times is a constant. This algorithm will be used as a subroutine in the PTAS for the general case. Finally, we prove the main result of the paper which is a PTAS for the case of an arbitrary number of resource arrival times.

Since the processing times are 0, every job is processed at one of the arrival times in any optimal schedule. Thus, a schedule can be represented by a mapping \(\pi : J \rightarrow [q]\), where \(\pi (j)\) denotes the index of the resource arrival time when job j is processed. A schedule is feasible if the resource requirements are met, that is, iffor all \(1\le k\le q\). As we assume that \(\sum _i b_i = \sum _j a_j\) holds, this is equivalent tofor all \(1\le k\le q\), where \(B_k=\sum _{i \ge k} b_i\). Consider the set of jobs that are not processed before a given time point \(t_k\). Then (2) says that if the resource requirements of these jobs add up to at least \(B_k\), then our schedule is feasible. We will mostly use this latter characterization of feasibility, as our algorithms assign the jobs to later time points first. The intuition is that we can bound the approximation ratio by giving sufficiently good upper bounds for every k on the total weight \(W_{\ge k}\) of jobs that are processed at time point \(t_k\) or later. We present here one such upper bound, that will be used in the first result of the next section, as well as in Sect. 5. For \(1\le k \le q\), letand let \(M_k\) be the set of jobs where the minimum is achieved.

In this section, we consider a variant of the problem where it is known that the arriving resource quantities will be \(b_1,\dots ,b_q\) in this order, but the resource arrival times \(t_j\) are unknown. A solution (schedule) consists of an ordering of the jobs, which determines the completion times for any fixed sequence of resource arrival times; this is then compared to the optimum for those arrival times. The problem is denoted by \(1|rm=1, p_j=0, t_i\ \text {unknown}|\sum C_jw_j\).

Consider an instance of the problem. Recall that \(B_k=\sum _{i \ge k}b_i\), \(M_k\) denotes the minimum weight job set consuming at least \(B_k\) resources, and \(m_k=w(M_k)\). Let \(\pi \) be a feasible schedule, and let \(W_{\ge k}=\sum _{j: \pi (j)\ge k} w_j\). Lemma 1 stated that if \(W_{\ge k}\le \alpha \cdot m_k\) for every \(1\le k \le q\), then \(\pi \) is an \(\alpha \)-approximation for given arrival times. However, the condition does not depend on the arrival times, so a schedule \(\pi \) satisfying the condition is actually an \(\alpha \)-approximation for this instance of \(1|rm=1, p_j=0, t_i\ \text {unknown}|\sum C_jw_j\).

Conversely, the smallest \(\alpha \) for which a feasible schedule satisfying the condition of Lemma 1 exists is the best approximation ratio possible; this can be seen by choosing the k for which \(W_{\ge k}\) is the worst approximation, and setting the arrival time \(t_i\) to 0 if \(i<k\) and to 1 if \(i \ge k\).

The proof of Theorem 3 implies that Algorithm 1 is a 6-approximation algorithm for \(1|rm=1, p_j=0, t_i\ \text {unknown}|\sum C_jw_j\). In the following, we show that for any instance, there is a schedule which gives a 4-approximation, while for \(\alpha <4\) there are instances where no such schedule exists. We also show that a \((4+\varepsilon )\)-approximation can be found efficiently for any \(\varepsilon \); it remains open whether 4-approximation is possible in polynomial time.

It is not difficult to see that \(\pi \) is a feasible schedule. We prove by induction that \(W_{\ge i} = w(L_i)\le 4w(M_i)\) holds for \(i=1,\dots ,q\). As \(L_q=M_{f(q)}\), the inequality \(w(L_q)\le 4w(M_q)\) clearly holds. Assume now that \(i\le q-1\). If no jobs are assigned to \(t_i\), then \(w(L_i)=w(L_{i+1})\le 4w(M_{i+1}) \le 4w(M_i)\). Otherwise \(i=f(i')-1\), where \(i'\) is the index considered in the previous iteration of the while loop in Step 2. Observe that no jobs are assigned to time points between the ith and the \(i'\)th ones. By induction, we getHere the second inequality holds by induction and by the definition of f, while the last inequality follows from the fact that \(i<f(i')\) which implies \(w(M_{i}) > 2w(M_{i'}) \). \(\square \)

Now we show how Algorithm 4 provides a \((4+\varepsilon )\)-approximation for the problem \(1|rm=1, p_j=0, t_i\) unkown\(|\sum C_jw_j\) which has running time polynomial in the input size and \(\frac{1}{\varepsilon }\). Using either an FPTAS for the knapsack problem or the FPTAS of Kis (2015), we determine an approximation of the sets \(M_i\). Then we apply Algorithm 4 with these approximations in place of the sets \(M_i\) to schedule the jobs. This concludes the proof of the first part of the theorem.

The following set of instances shows that \(\alpha \) is at least 4. We are given \((n-1)m\) jobs denoted by \(1, 2, \dots , (n-1)m\) with weights \(w_i=n-\frac{i}{m}\) and \(a_i=2^{-i}\). Furthermore, we have \((n-1)m\) resource arrival times that are unknown. The resource quantities are given by \(b_q=2^{-q}\) and \(b_i=2^{-i}-B_{i+1}=2^{-i-1}\) for \(1<i<q\); \(b_1\) equals the remaining resource requirement.

In order to fulfill the resource requirements, the set of jobs scheduled at or after time \(t_i\) has to contain at least one of the jobs \(j\le i\). Observe that the optimal solution of finding a minimum weight job set \(M_i\) consuming at least \(B_i\) resources consists of the single job i.

Let \(j_1\) be a job processed at time \(t_q\). We may assume that \(w_{j_1} \le 4 w_q=4\), because otherwise this schedule is not a 4-approximation if \(t_q=1\) and all other arrival times are set to 0.

We create a sequence starting with \(j_1\). Since the jobs with indices greater or equal to \(j_1\) have total resource requirement less than \(B_{j_1-1}\), we have to schedule at least one job \(j_2<j_1\) at or after \(t_{j_1-1}\). This argument can be iterated to find a job \(j_3 < j_2\) which is scheduled at or after \(t_{j_2-1}\), and so on, until \(j_N=1\) for some N.

The following claim shows that for n, m large enough, there must be an index i such that the jobs in this sequence that are scheduled at or after \(t_{j_i-1}\) have large total weight compared to \(w_{j_i-1}=w(J_{j_i-1})\).

By Claim 9, there exists a time point \(t_i\) with \(\sum _{j:\pi (j)\ge i} w_j>\beta w(J_i)\). By setting \(t_{i'}=0\) (or very close to 0) for \(i'<i\) and \(t_{i'}=1\) (or very close to 1) for \(i'\ge i\), the schedule can only be a \((\beta - \varepsilon )\)-approximation if we do not know the resource arrival times in advance. \(\square \)