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

Bérczi, Kristóf; Király, Tamás; Omlor, Simon Article — Published Version Scheduling with non-renewable resources: minimizing the sum of completion times Journal of Scheduling Provided in Cooperation with: Springer Nature Suggested Citation: Bérczi, Kristóf; Király, Tamás; Omlor, Simon (2024) : Scheduling with nonrenewable resources: minimizing the sum of completion times, Journal of Scheduling, ISSN 1099-1425, Springer US, New York, NY, Vol. 27, Iss. 2, pp. 151-164, https://doi.org/10.1007/s10951-024-00807-y This Version is available at: https://hdl.handle.net/10419/315300 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. http://creativecommons.org/licenses/by/4.0/ Journal of Scheduling (2024) 27:151–164 https://doi.org/10.1007/s10951-024-00807-y Scheduling with non-renewable resources: minimizing the sum of completion times Kristóf Bérczi1·Tamás Király2·Simon Omlor3 Accepted: 5 February 2024 / Published online: 24 March 2024 © The Author(s) 2024 Abstract We consider single-machine scheduling with a non-renewable resource. In this setting, we are given a set of jobs, each characterized by a processing time, a weight, and a resource requirement. At fixed points in time, certain amounts of the resource are made available to be consumed by the jobs. The goal is to assign the jobs non-preemptively to time slots on the machine, so that each job has enough resource available at the start of its processing. The objective that we consider is the minimization of the sum of weighted completion times. The main contribution of the paper is a PTAS for the case of 0 processing times (1|rm =1,pj=0|wjCj). In addition, we show strong NP-hardness of the case of unit resource requirements and weights (1|rm =1,aj=1|Cj), thus answering an open question of Györgyi and Kis. We also prove that the schedule corresponding to the Shortest Processing Time First ordering provides a 3/2-approximation for the latter problem. Finally, we investigate a variant of the problem where processing times are 0 and the resource arrival times are unknown. We present a (4+)-approximation algorithm, together with a (4−ε)-inapproximability result, for any ε>0. Keywords Approximation algorithm ·Non-renewable resources ·Polynomial-time approximation scheme ·Strong NP-hardness ·Scheduling ·Weighted sum of completion times An extended abstract of this work appeared in the 6th International Symposium on Combinatorial Optimization (ISCO 2020). This research has been implemented with the support provided by the Lendület Programme of the Hungarian Academy of Sciences—Grant Number LP2021-1/2021, by the Ministry of Innovation and Technology of Hungary from the National Research, Development and Innovation Fund, financed under the ELTE TKP 2021-NKTA-62 funding scheme, and by Dynasnet European Research Council Synergy project (ERC-2018-SYG 810115). BKristóf Bérczi [email protected] Tamás Király [email protected] Simon Omlor [email protected] 1MTA-ELTE Matroid Optimization Research Group, HUN-REN-ELTE Egerváry Research Group, Department of Operations Research, Eötvös Loránd University, Budapest, Hungary 2HUN-REN-ELTE Egerváry Research Group, Department of Operations Research, Eötvös Loránd University, Budapest, Hungary 3Faculty of Statistics, TU Dortmund University, Dortmund, Germany 1 Introduction 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 α|β|γnotation of Graham et al. (1979). Grigoriev et al. (2005) extended this notation by adding the restriction rm =rto the βfield, meaning that there are rresources (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|wjCj. While there is an abundance of results on the approximability of the makespan objective, much less 123 152 Journal of Scheduling (2024) 27:151–164 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´nski (1984). Carlier (1984) settled the computational complexity of several variants for the single machine case. In particular, he showed that 1|rm =1|wjCjis 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|wjCj. A variant of the problem where each job has processing time 1, there are q=n resource arrival times such that ti=iM and bi=Mfor i=1,...,n, and M=j∈Jaj/nis 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´nski (1984) studied the preemptive scheduling of independent jobs on parallel unrelated machines with the use of additional renewable and nonrenewable 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,2015b,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,aj= 1|Cj. 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. Theorem 1 1|rm =1,aj=1|Cjis strongly NP-hard. 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 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. Theorem 2 The SPT schedule gives a 3 2-approximation for 1|rm =1,aj=1|Cj, and the approximation guarantee is tight. 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. Theorem 3 For 1|rm =1,pj=0|Cjwj, there exists a 6-approximation algorithm with running time O(nlog n). After the proof of Theorem 3, we give a slightly more complicated (4+ε)-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. Theorem 4 Consider the number of arrival times q to be constant. For any fixed positive integer k, there is a (1+q k)- approximation algorithm for 1|rm =1,pj=0|Cjwj with running time O(nqk+1). The main contribution of the paper is a PTAS for the same problem with an arbitrary number of resource arrival times. 123 Journal of Scheduling (2024) 27:151–164 153 Theorem 5 There exists a PTAS for 1|rm =1,pj= 0|Cjwj. Finally, we consider a variant of 1|rm =1,pj= 0|Cjwjwhere 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,pj=0,tiunknown|Cjwj. We observe that the greedy 6-approximation algorithm of Theorem 3is actually a 6-approximation for this problem, too. We can improve the approximation factor to get the following tight result. Theorem 6 For 1|rm =1,pj=0,tiunknown|Cjwj, there exists a (4+ε)-approximation with running time polynomial in 1/ε and the input length. Moreover, there is no (4−ε)-approximation algorithm for the problem for any ε>0. 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,aj=1|Cjare given in Sect.3. Results on problem 1|rm =1,pj=0|Cjare 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. 2 Preliminaries Throughout the paper, we will use the following notation. We are given a set Jof njobs. Each job j∈Jhas a non-negative integer processing time pj, a non-negative weight wj, and a resource requirement aj.Theresources arrive at time points t1,...,tq, and the amount of resource that arrives at tiis denoted by bi. We might assume that q i=1bi= n j=1ajholds. We will always assume that t1=0, as this does not affect the approximation ratio of our algorithms. We will use the notation Bk=i≥kbifor the amount of resource that arrives no earlier than tk. The jobs should be processed non-preemptively on a single machine. A schedule is an ordering of the jobs, that is, a mapping σ:J→[n], where σ(j)=imeans that job jis the ith job scheduled on the machine. The completion time of job jin schedule σis denoted by Cσ j. We will drop the index σif the schedule is clear from the context. In any reasonable schedule, there is an idle time before a job jonly if there is not enough resource left to start jafter finishing the last job before the idle period. Hence, the completion time of job jis determined by the ordering and by the resource arrival times, as jwill be scheduled at the first moment when the preceding jobs are already finished and the amount of available resource is at least aj. 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 π:J→[q], where π(j)denotes the index of the resource arrival time when job jis processed. 3 The problem 1|rm =1,aj=1|Cj 3.1 Strong NP-completeness The aim of this section is to prove Theorem 1. Theorem 1 1|rm =1,aj=1|Cjis strongly NP-hard. Proof Recall that all ajand wjvalues are 1, and each job has an integer processing time pj. The number of resource arrival times is part of the input. We prove NP-completeness by reduction from the 3Partition problem. The input contains numbers B∈N, n∈N, and xj∈N(j=1,...,3n)such that B/4<xj< B/2 and 3n j=1xj=nB (note that we will not use the upper bound xj<B/2 in the proof). A feasible solution is a partition J1,...,Jnof [3n]such that |Ji|=3 and j∈Jixj=B for every i∈[n]. In contrast to the Partition problem, the 3partition problem remains NP-complete even when the integers xjare bounded above by a polynomial in n. That is, the problem remains NP-complete even when the numbers in the input are represented as unary numbers (Garey & Johnson, 1979, Pages 96–105 and 224). We assume without loss of generality that Bis divisible by 4, so xj≥B/4+1≥2 for every j.LetK=4nB.The reduction to 1|rm =1,aj=1|Cjinvolves three types of jobs. Normal jobs These correspond to the numbers xjin the 3Partition instance, so there are 3nof them and the processing time pjof the jth normal job is xj. Small jobs Their processing time is 1 and there are nK of them. Large jobs Their processing time is Kand there are nK of them. There are also three types of resource arrivals (see Fig. 1): Type 1 Three resources arrive at times i(B+K)(i= 0,...,n−1). Type 2 One resource arrives at i(B+K)+j(i=0,...,n−1, j=B,...,B+K−1). Type 3 One resource arrives at n(B+K)+iK (i= 0,...,nK −1). 123 154 Journal of Scheduling (2024) 27:151–164 Fig. 1 Resource arrivals in the reduction of 3Partition Suppose that the 3Partition instance has a feasible solution J1,...,Jn. We consider the following schedule σ: resources of Type 1 are used by normal jobs, such that jobs in Jiare scheduled between (i−1)(B+K)and iB+(i−1)K (in spt order). Type 2 resources are used by small jobs that start immediately. Type 3 resources are used by the large jobs that also start immediately at the resource arrival times (see Fig.2). Instead of Cj, we consider the equivalent shifted objective function (Cj−t(j)−pj), where t(j)is the arrival time of the resource used by job jand pjis the processing time of j—we assume without loss of generality that resources are used by jobs in order of arrival. Note that all terms of (Cj−t(j)−pj)are nonnegative. As small jobs and large jobs start immediately at the arrival of the corresponding resource in schedule σ, their contribution to the shifted objective function is 0. The jobs in Jihave total processing time B, and their contribution to the shifted objective function is twice the processing time of the shortest job, plus the processing time of the second shortest job, which is at most B. Hence the schedule σhas objective value at most nB. We claim that if the 3Partition instance has no feasible solution, then the objective value of any schedule is strictly larger than nB. First, notice that if a large job is scheduled to start before time n(B+K), then (Cj−t(j)−pj)has a term strictly larger than nB as there is a resource that arrives while the large job is processed and is not used for more than nB time units. Similarly, if the first large job starts at n(B+K)but uses a resource that arrived earlier, then the resource that arrives at n(B+K)is not used for more than nB time units. We can conclude that the first large job uses the resource arriving at n(B+K). If the first large job does not start at n(B+K), then all large jobs have positive contribution to the objective value, so again, the objective value is larger than nB. We can therefore assume that the large jobs start exactly at n(B+K)+iK (i=0,...,nK −1)and that there is no idle time before (B+K)n. In particular, this means that all other jobs are already completed at time (B+K)n. Consider Type 2 resources arriving at i(B+K)+j (j=B,...,B+K−1) for some fixed i≤n−1. If the first resource or the second resource in this interval is not used immediately, then none of the subsequent ones are, so the objective value is at least K−1>nB. Hence, we may assume that both the first and the second resources are used immediately. This means that first resource is used immediately by a small job, since normal jobs have processing time at least 2. Thus, the resource arriving at i(B+K)+Bis immediately used by a small job, for every i≤n−1. Suppose that some other resource in the interval i(B+ K)+j(j=B+1,...,B+K−1) is used by a normal job. If it is followed by a small job, then we may improve the objective value by exchanging the two. Thus, in this case, we can assume that the last resource of the interval is used by a normal job (this already implies i≤n−2, because a large job starts at n(B+K)), and also the Type 1 resources arriving at (i+1)(B+K)are used by normal jobs. But this is impossible, because normal jobs have processing time at least B/4+1, and a small job starts at time (i+1)(B+K)+B by. To sum up, we can assume that all resources of Type 2 are used immediately by small jobs. This means that normal jobs have to use resources of Type 1, and must exactly fill the gaps of length Bbetween the arrival of resources of Type 2. This is only possible if the 3-partition instance has a feasible solution, concluding the proof of Theorem 1. 3.2 Shortest processing time first for unit resource requirements In the previous section, we have seen that scheduling with a non-renewable resource is strongly NP-hard already for unit resource requirements. Now we show that scheduling the jobs according to an spt ordering provides a 3/2-approximation for the problem with unit weight and unit resource requirements, thus proving Theorem 2. Theorem 2 The SPT schedule gives a 3 2-approximation for 1|rm =1,aj=1|Cj, and the approximation guarantee is tight. Proof Consider an instance Iof the problem. Let σspt and σopt denote the SPT and the optimal schedule, and let spt and opt denote the sum of the completion times in these two schedules, respectively. We will use the notation jspt(i), pspt(i),Sspt(i), and Cspt(i)for the ith job in the SPT schedule, its processing time, its starting time, and its completion time, respectively. We also use similar notation with subscript opt for the optimal schedule. Our strategy is to simplify the instance by revealing its structural properties while not decreasing spt opt . This way we get an upper bound for the approximation factor. We first consider the resource arrival times. Claim 1 We may assume that the ith resource arrives at Sopt(i)for i =1,...,n. 123 Journal of Scheduling (2024) 27:151–164 155 Fig. 2 The schedule corresponding to a feasible solution of 3Partition Proof As the ith resource is used by job jopt(i), the arrival time of that resource is at most Sopt(i). If we move the arrival time of the resource to exactly Sopt(i), then opt does not change and spt cannot decrease.  The next claim shows that we can get rid of the idle times in the optimal schedule. Claim 2 We may assume that there is no idle time in schedule opt, that is, Sopt(i)=Copt(i−1)for i =2,...,n. Proof Suppose that there is some isuch that ti>Copt(i−1). We reduce tiby Δ=ti−Copt(i−1)for all i≥i. Then for each i≥i, the completion time Copt(i)decreases by Δ. For each i≥i, the completion time Cspt(i)decreases by at most Δ. This follows from the fact that the resource arrival times decrease by Δand the completion time of the previous job can decrease by at most Δ(which can be shown by induction). Hence opt decreases by at least as much as spt. Since spt ≥opt, the ratio spt opt will not decrease by this change.  Next, we modify the processing times. Claim 3 We may assume that popt(1)>pspt(1)and that pspt(1)=0. Proof If both schedules start with the same job, then we can remove the job from the instance and decrease b1by 1. Then opt decreases by the same amount as spt. We can repeat this until the schedules start with jobs of different processing times. Now popt(1)>pspt(1), since spt starts with the shortest job. Decreasing the processing time of job jspt(1) to 0 (without changing any arrival time) decreases spt by pspt(1)and opt by at least pspt(1). We can eliminate idle times in the new optimal schedule as in the proof of Claim 2. Claim 4 We may assume that pj∈{0,1}for all j ∈J. Proof Let pmax =maxj∈Jpjbe the maximum processing time. Scaling the processing times by dividing all processing and arrival times by pmax has no effect on spt opt , hence we may assume that pmax =1. Now assume that there is a job jwith p=pj∈(0,1).Letp=min{pj|j∈J,pj>p}and p=max{pj|j∈J,pj<p}.LetJp={j∈J|pj=p} be the set of jobs with processing time p. We will show that we can either increase the processing time of all jobs in Jp to por decrease the processing time of all jobs in Jpto p without decreasing spt opt . For j∈J,lethjdenote the number of jobs processed after jin σopt plus 1, i.e. hj=n−σopt(j)+1. We consider the effect of increasing the processing times of all jobs in Jp by some Δ∈[p−p,p−p]and appropriately modifying the arrival times of the resources to match the new starting times (note that Δmay be negative, in which case we decrease the processing times and starting times). This will increase opt by Δj∈Jphj. Indeed, every time we change the processing time of one job j, the completion time of jand of all jobs after jwill be increased by Δ. Notice that the order of the jobs in the SPT schedule does not change. Consider the SPT schedule before the change. Let job j∈Jbe any job, let j0be the the first job that is processed after the last idle time before the starting time of j, and let i=σspt(j0)(if there is no idle time before j,leti=1). Let fjbe the number of jobs j∈Jpwith σopt(j)<i; notice that these are exactly the jobs whose modification affects ti. Thus, the arrival time tiis changed by Δfor each of those jobs, so the new arrival time is ti+Δfj. This means that the starting time of job j0in the changed SPT schedule is at least Sspt j0+Δfj.Nowletgjbe the number of jobs j∈Jpthat are processed in the time interval [ti,Cspt j)before the change. For each of those jobs, the processing time is changed by Δ and the job is started at or after ti+Δfj, since the SPT order does not change. Thus, the new completion time of jis at least Cspt j+Δfj+Δgj. Consequently, spt will increase by at least j∈J(fj+gj)Δ if Δ>0, and decrease by at most j∈J(fj+gj)|Δ|if Δ<0. If j∈J(fj+gj) j∈Jphj≥spt opt , then increasing the processing times in Jpto pwill not decrease spt opt . Otherwise, decreasing the processing times in Jpto pwill not decrease spt opt . Each time we apply this operation, the number of distinct processing times decreases by 1. Finally, we get an instance where the only processing times are pmin =0 and pmax =1.  Finally, we modify the order of the jobs in the optimal solution. If σopt and σspt process a job of length 0 at the same time, then we can remove the job from the instance and reduce the number of resources that arrive at this time by 1. This will reduce opt and spt by the same amount. Let tbe the time at which schedule σspt first starts to process a job of length 1. On one hand, σopt does not process jobs of length 0 before tby the above argument. On the other 123 156 Journal of Scheduling (2024) 27:151–164 hand, there is no idle time after tin σspt, because that would mean idle time in σopt. Thus, if we move all jobs of length 0 and their corresponding resource arrivals in σopt to time t, then spt does not change but opt decreases. We may thus assume that schedule σopt processes every job of length 0 at t. Let k1be the number of jobs of length 0 after the transformations. These are processed at time tin σopt, and these are exactly the jobs processed before time tin σspt. Thus, there are k1arrival times before t, where σopt processes jobs of length 1. Let k1+k2be the total number of jobs of length 1. We conclude that σopt first processes k1jobs of length 1, then k1jobs of length 0 and then k2jobs of length 1, while σspt starts with the jobs of length 0 having a lot of idle time in the beginning and then consecutively processes all jobs of length 1 (see Fig.3). The weighted sums of completion times are then given by opt =k1(k1+1) 2+k2 1+k2k1+k2(k2+1) 2 and spt =k1(k1−1) 2+k2k1+k1(k1+1) 2 +(k1+k2)k1+k2(k2+1) 2. We get 3 2opt −spt =k2 1 4+k2 2 4−k1k2 2+3k1+k2 4 ≥(k1−k2)2 4≥0, showing that the approximation factor is at most 3 2. Setting k2=k1and letting k1go to infinity gives us a sequence of instances such that spt opt converges to 3 2as we have spt =9 2k2 1+O(k1)and opt =3k2 1+O(k1).This concludes the proof of Theorem 2. 4 The problem 1|rm =1,pj=0|Cjwj In this section we consider the problem 1|rm =1,pj= 0|Cjwj, another special case of 1|rm =1|Cjwj. 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|Cjwjwhen 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+ε)-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 π:J→[q], where π(j)denotes the index of the resource arrival time when job jis processed. A schedule is feasible if the resource requirements are met, that is, if  j:π(j)≤k aj≤ i≤k bi(1) for all 1 ≤k≤q. As we assume that ibi=jajholds, this is equivalent to  j:π(j)≥k aj≥Bk(2) for all 1 ≤k≤q, where Bk=i≥kbi. Consider the set of jobs that are not processed before a given time point tk. Then (2) says that if the resource requirements of these jobs add up to at least Bk, 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 kon the total weight W≥kof jobs that are processed at time point tkor 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.For1≤k≤q,let mk=min{w(J):J⊆J, j∈J aj≥Bk}, and let Mkbe the set of jobs where the minimum is achieved. Lemma 1 Let πbe a feasible schedule, and let W≥k= j:π(j)≥kwj.IfW ≥k≤α·mkfor every 1≤k≤q, then π is an α-approximation. Proof Let πopt be the optimal schedule, and let Wopt ≥k= j:πopt(j)≥kwj. We can bound the objective value of πby  j∈J wjCj=q k=1(tk−tk−1)W≥k≤αq k=1(tk−tk−1)mk ≤αq k=1(tk−tk−1)Wopt ≥k=αj∈JwjCopt j, which is αtimes the objective value of πopt. 123 Journal of Scheduling (2024) 27:151–164 157 Fig. 3 Schedules σopt and σspt after the reductions. The jobs of length 0 are scheduled in σopt at the first resource arrival time when multiple resources arrive 4.1 A greedy 6-approximation for arbitrary q The idea of our first algorithm is to have a balance between adding jobs that have small weights and jobs that have high resource requirements. More precisely, we will assign jobs to the time points in reverse order. When we add a job to the set of jobs scheduled after a given time point, we will choose the most inefficient job, i.e. the job minimizing wj/ajamong all jobs that have weight at most the weight Wof all jobs that have already been chosen up to this point. If there is no job with weight at most W, then we simply choose a job with minimal weight. Intuitively, this rule guarantees that the jobs we choose are not too efficient but their total weight is not too large either. Algorithm 1 Greedy algorithm for 1|rm =1,pj= 0|Cjwj. Input: Jobs Jwith |J|=n, resource requirements aj, weights wj, resource arrival times t1≤... ≤tqand resource quantities b1,...bq. Output: A feasible schedule π. 1: Set A=0. 2: Set W=0. 3: for ifrom 0 to q−1do 4: while A<Bq−ido 5: if there is an unassigned job jwith wj≤Wthen 6: Let jbe an unassigned job with wj≤Wminimizing wj/aj. 7: else 8: Let jbe an unassigned job minimizing wj. 9: W←W+wj 10: A←A+aj 11: Set π(j)=q−i. 12: return π Theorem 3 For 1|rm =1,pj=0|Cjwj, there exists a 6-approximation algorithm with running time O(nlog n). Proof It is clear that the schedule πreturned by Algorithm 1 satisfies (2), so it is feasible. We claim that πsatisfies the requirements of Lemma 1with α=6, i.e., W≥k≤6mkfor every k.LetMkdenote the set of jobs where the minimum mkis achieved. To bound W≥kfor a given k, we consider the algorithm up until the last step where q−i≥k, and divide it into 3 phases (some of these may be empty): – Phase 1: until the first iteration where Wbecomes at least mk – Phase 2: until the last iteration where A<Bk – Phase 3: the last step, where Abecomes at least Bk. At the end of phase 1, we have W≤2mk, because at the beginning of the last step of phase 1, we either add a job of weight at most W(which is less than mkat that point), or we add a job of minimum weight, which is again at most mk because some job in Mkis still unassigned. In phase 2, the total weight added is at most mk. Indeed, throughout phase 2, some job in Mkis still unassigned, but W≥mk, so we always pick an unassigned job jwith wj≤ Wminimizing wj/aj. Thus, the job selected is at least as inefficient as any unassigned job in Mk, so the total weight of the selected jobs cannot be larger than mk. At the beginning of phase 3, we have A<Bkand mk≤ W≤3mk. At this point, there is still an unassigned job in Mk, so the selected job has weight at most W≤3mk. Thus, the total weight is at most 6mk. The running time bound follows by ordering the jobs according to their weight and by using AVL trees for picking jin the while loop.  The following example shows that the bound is tight. We have 5 jobs with weights w1=w2=1−2ε,w3=1−ε, w4=1 and w5=3. The resource requirements are a1= a2=ε/5, a3=1−ε/2, a4=1 and a5=4. The resource arrival times are t1=0 and t2=1, with resource quantities b1=5−ε/10 and b2=1. Here the optimum solution is to schedule the job with weight 1 to time point t2and all the remaining jobs to time point t1. However, our algorithm will schedule the job with weight 1 to time point t1and all the remaining jobs to t2. 123 158 Journal of Scheduling (2024) 27:151–164 4.2 A (4+")-approximation for arbitrary q Now we give a slightly better approximation for the problem. The algorithm is a bit more complicated than the one presented in Sect.4.1, but the proof illustrates one of the important ideas of the general PTAS. The idea of the algorithm is as follows. We may assume without loss of generality that resource arrival times are integer, because multiplying all arrival times by a large integer does not change the problem. First we shift all resource arrival times to powers of 2. For each arrival time tiin the shifted instance, we apply the FPTAS by Kis (2015) to the instance which has only two resource arrival times t1and ti, and the resource quantity for tiis Bi. Denote the set of jobs assigned to tithis way by Li. Then, we schedule each job jat the latest time point tiwhere j∈Li, i.e. π(j)=max{i:j∈Li}. More formally, let Ibe an instance of 1|rm =1,pj= 0|jCjwj. We assume t1=0 and t2=1 (the latter assumption is without loss of generality because we can add an arrival time with 0 resource arrival). We define a new instance Iof 1|rm =1,pj=0|jCjwjwith shifted resource arrival times as follows. Set t i=0ifi=1, 2i−2for i=2,...,log2(tq)+2, and b i=biif i=1,2, [b:t∈(2i−3,2i−2]] for i=3,...,log2(tq)+2. Claim 5 A solution to Iwith weighted sum of completion times W can be transformed into a solution of Iwith weighted sum of completion times at most 2W. Furthermore, any feasible schedule for Iis also feasible for I. Proof Let us define t∗ i=min{t :ti≤t }for i=1,...,q. Let πbe the solution for I. Then assigning all jobs that are assigned to time point tito t∗ igives us a feasible solution to I. By this change, the completion of any job is at most doubled (recall that each tiis assumed to be integer). Since the available amount of resources at each time in I is at most as much as in I, a feasible schedule for Iis also a feasible schedule for I. Claim 6 There exists a polynomial time (2+ε)-approximation algorithm for constant εfor all instances Iwhere the resource arrival times are integer powers of 2. Proof We use the procedure that we described above, i.e., for each i>1 we solve the instance with Biresource arriving at tiand the rest at t1, using the FPTAS provided by Kis (2015). As defined above, Liis the set of jobs assigned to tiby the FPTAS, and π(j)=max{i:j∈Li}. Let α=1+ε.Letπopt be an optimum solution and let Jopt kbe the set of jobs jwith πopt(j)=k.Wehave w(Li)≤α q  k=i w(Jopt k) for i=1,...,q. Then we get 2α j∈J wjCπopt j= q  i=2 (2α) ·2i−2w(Jopt i) = q  i=2 α·2i−2w(Jopt i)⎛ ⎝1+ ∞  j=1 2−j⎞ ⎠ ≥ q  i=2 α2i−2 q  k=i w(Jopt k) ≥ q  i=2 2i−2w(Li), thus the approximation ratio follows.  The two claims show that this approach leads to a (4+ε)- approximation with running time polynomial in 1/ε and the input length. 4.3 PTAS for constant q TheaimofthissectionistogiveaPTASforthecasewhenthe number of resource arrival times is a constant. The algorithm is a generalization of a well known PTAS for the knapsack problem, and will be used later as a subroutine in the PTAS for an arbitrary number of resource arrival times. The idea is to choose a number k∈Z+, guess the kheaviest jobs that are processed at each resource arrival time ti, and then determine the remaining jobs that are scheduled at tiin a greedy manner. Since we go over all possible sets containing at most kjobs for each resource arrival time, there is an exponential dependence on the number qof resource arrival times in the running time. Theorem 4 Consider the number of arrival times q to be constant. For any fixed positive integer k, there is a (1+q k)- approximation algorithm for 1|rm =1,pj=0|Cjwj with running time O(nqk+1). Proof We claim that Algorithm 2satisfies the requirements of the theorem. Let πopt be an optimal schedule and define Jopt i={j∈J:πopt(j)=i}.LetHopt ibe the set of the kheaviest jobs in Jopt iif |Jopt i|≥k, otherwise let Hopt i= Jopt i.LetJi={j∈J:π(j)=i}denote the set of jobs 123