Lin Chen
email: lchen@math.tu-berlin.de

Nicole Megow
email: nicole.megow@tum.de

Roman Rischke
email: rischke@math.tu-berlin.de

Leen Stougie
email: stougie@cwi.nl

José Verschae
email: jverschae@uc.cl

Optimal Algorithms and a PTAS for Cost-Aware Scheduling

We consider a natural generalization of classical scheduling problems in which using a time unit for processing a job causes some time-dependent cost which must be paid in addition to the standard scheduling cost. We study the scheduling objectives of minimizing the makespan and the sum of (weighted) completion times. It is not difficult to derive a polynomial-time algorithm for preemptive scheduling to minimize the makespan on unrelated machines. The problem of minimizing the total (weighted) completion time is considerably harder, even on a single machine. We present a polynomial-time algorithm that computes for any given sequence of jobs an optimal schedule, i.e., the optimal set of time-slots to be used for scheduling jobs according to the given sequence. This result is based on dynamic programming using a subtle analysis of the structure of optimal solutions and a potential function argument. With this algorithm, we solve the unweighted problem optimally in polynomial time. Furthermore, we argue that there is a (4+ε)-approximation algorithm for the strongly NP-hard problem with individual job weights. For this weighted version, we also give a PTAS based on a dual scheduling approach introduced for scheduling on a machine of varying speed.

Introduction

We consider a natural generalization of classical scheduling problems in which occupying a time slot incurs certain cost that may vary over time and which must be paid in addition to the actual scheduling cost. Such a framework has been proposed recently in [START_REF] Wan | Scheduling with variable time slot costs[END_REF] and [START_REF] Kulkarni | Algorithms for cost-aware scheduling[END_REF]. It models additional cost for operating servers or machines that vary over time such as, e.g., labor cost that may vary by the day of the week, or the hour of the day [START_REF] Wan | Scheduling with variable time slot costs[END_REF], or electricity cost fluctuating over day time [START_REF] Kulkarni | Algorithms for cost-aware scheduling[END_REF]. On the one hand, the latter have economically a huge impact on facilities with enormous power consumption such as large data centers, and on the other hand, these fluctuations reflect the imbalance between generation and consumption of electricity on a daily or weekly basis. Hence, cost aware scheduling is economically profitable and supports an eco-aware usage and generation of energy. Another motivation stems from cloud computing. Users of such services, e.g., Amazon EC2, are offered time-varying pricing schemes for processing jobs on a remote cloud server [START_REF]Amazon EC2 Pricing Options[END_REF]. It is a challenging task for them to optimize the tradeoff between resource provisioning cost and the scheduling quality.

Problem definition. We first describe the underlying classical scheduling problems. We are given a set of jobs J := {1, . . . , n} where every job j ∈ J has given a processing time p j ∈ N and possibly a weight w j ∈ Q ≥0 . The task is to find a preemptive schedule on a single machine such that the total (weighted) completion time, j∈J w j C j , is minimized. Here C j denotes the completion time of job j. In the standard scheduling notation, this problem is denoted as 1 | pmtn | (w j )C j . We also consider makespan minimization on unrelated machines, typically denoted as R | pmtn | C max . Here we are given a set of machines M , and each job j ∈ J has an individual processing time p ij ∈ N for running on machine i ∈ M . The task is to find a preemptive schedule that minimizes the makespan, that is, the completion time of the latest job.

In this paper, we consider a generalization of these scheduling problems within a time-varying reservation cost model. We are given a cost function e : N → R, where e(t) denotes the reservation cost for processing job(s) at time t. We assume that e is piecewise constant with given breakpoints at integral time points. We assume, more formally, that time is discretized into unit-size time slots, and the time horizon is partitioned into given intervals I k = [s k , d k ) with s k , d k ∈ N, k = 1, . . . , K, within which unit-size time slots have the same unit reservation cost e k . To ensure feasibility, let d K ≥ j∈J min i∈M p ij .

Given a schedule S, let y(t) be a binary variable indicating if any processing is assigned to time slot [t, t + 1). The reservation cost in S is E(S) = t e(t)y(t). That means, for any time unit that is used in S we pay the full unit reservation cost, even if the unit is only partially used. We also emphasize that in case of multiple machines, a reserved time slot can be used by all machines. This models applications in which reserving a time unit on a server gives access to all processors on this server.

The overall objective now is to find a schedule that minimizes the scheduling objective, C max resp. j∈J w j C j , plus the reservation cost E. We refer to the resulting problems as

R | pmtn | C max + E and 1 | pmtn | w j C j + E.

Related work.

Scheduling with time-varying reservation cost (aka variable time slot cost) has been studied explicitly in [START_REF] Wan | Scheduling with variable time slot costs[END_REF] and [START_REF] Kulkarni | Algorithms for cost-aware scheduling[END_REF]. The seminal paper [START_REF] Wan | Scheduling with variable time slot costs[END_REF] is concerned with several non-preemptive single machine problems, which are polynomial-time solvable in the classical setting, such as minimizing the total completion time, lateness, and total tardiness, or maximizing the weighted number of on-time jobs. These problems are shown to be strongly NP-hard when taking reservation cost into account, while efficient algorithms exist for restricted reservation cost functions. In particular, the problem 1 | | C j + E is strongly NP-hard, and it is efficiently solvable when the reservation cost is increasing or convex non-increasing [START_REF] Wan | Scheduling with variable time slot costs[END_REF]. The research focus in [START_REF] Kulkarni | Algorithms for cost-aware scheduling[END_REF] is on online flow-time mini-mization using resource augmentation. Their main result is a scalable algorithm that obtains a constant performance guarantee when the machine speed is increased by a constant factor and there are only K = 2 distinct unit reservation cost. They also show that, in this online setting, for arbitrary K there is no constant speedup-factor that allows for a constant approximate solution.

In this paper, we study the simpler-but not yet well understood-offline problem without release dates. For this problem, the authors in [START_REF] Kulkarni | Algorithms for cost-aware scheduling[END_REF] announce the following results: a pseudo-polynomial (4 + ε)-approximation for 1 | pmtn | w j C j + E, which gives an optimal solution in case that all weights are equal, and a constant approximation in quasi-polynomial time for a constant number of distinct reservation costs or when using a machine that is processing jobs faster by a constant factor.

The general concept of taking into consideration additional (time-dependent) cost for resource utilization when scheduling has been implemented differently in other models. We mention the area of energy-aware scheduling, where the energy consumption is taken into account (see [START_REF] Albers | Energy-efficient algorithms[END_REF] for an overview), or scheduling with generalized non-decreasing (completion-) time dependent cost functions, such as minimizing j w j f (C j ), e.g. [START_REF] Epstein | Universal sequencing on an unreliable machine[END_REF][START_REF] Höhn | On the performance of Smith's rule in single-machine scheduling with nonlinear cost[END_REF][START_REF] Megow | Dual techniques for scheduling on a machine with varying speed[END_REF], or even more general job-individual cost functions j f j (C j ), e.g. [START_REF] Bansal | The geometry of scheduling[END_REF]. Our model differs fundamentally since our cost function may decrease with time, because delaying the processing in favor of cheaper time slots may decrease the overall cost. This is not the case in the above-mentioned models. Thus, in our framework we have the additional dimension in decision-making of choosing the time slots to be reserved.

There is also some similarity between our model and scheduling on a machine of varying speed. Notice that the latter problem (with j w j C j as objective function) can be reformulated as minimizing j w j f (C j ) on a single machine with constant speed. Interestingly, the independently studied problem of scheduling with non-availability periods, see e.g. the survey [START_REF] Lee | Machine scheduling with availability constraints[END_REF], is a special case of both, the time-varying speed and the time-varying reservation cost model. Indeed, machine non/availability can be expressed either by 0/1-speed or equivalently by ∞/0 unit reservation cost. Results shown in this context imply that our problem 1 | pmtn | j w j C j + E is strongly NP-hard, even if there are only two distinct unit reservation costs [START_REF] Wang | Preemptive scheduling with availability constraints to minimize total weighted completion times[END_REF].

Our contribution. We present new optimal algorithms and best-possible approximation results for a generalization of standard scheduling problems to a framework with time-varying reservation cost.

Firstly, we give an optimal polynomial-time algorithm for the problem R | pmtn | C max + E (Sec. 2). It relies on a known algorithm for the problem without reservation cost [START_REF] Lawler | On preemptive scheduling of unrelated parallel processors by linear programming[END_REF] to determine the optimal number of time slots to be reserved, together with a procedure for choosing the time slots to be reserved.

Our main results concern single-machine scheduling to minimize the total (weighted) completion time (Sec. 3). We present an algorithm that computes for a given ordered set of jobs an optimal choice of time slots to be used for scheduling. We derive this by first showing structural properties of an optimal schedule, which we then exploit together with a properly chosen potential func-tion in a dynamic program yielding polynomial running time. Based on this algorithm, we show that the unweighted problem 1 | pmtn | C j + E can be solved in polynomial time and that there is a (4 + ε)-approximation algorithm for the weighted version 1 | pmtn | w j C j + E. A pseudo-polynomial (4 + ε)approximation has been known before [START_REF] Kulkarni | Algorithms for cost-aware scheduling[END_REF]. While pseudo-polynomial time algorithms are rather easy to derive, it is quite remarkable that our DP's running time is polynomial in the input, in particular, independent of d K .

Finally, we design for the strongly NP-hard weighted problem variant (Sec. 4) a pseudo-polynomial algorithm that computes for any fixed ε a (1 + ε)approximate schedule for 1 | pmtn | w j C j + E. If d K is polynomially bounded, then the algorithm runs in polynomial time for any ε, i.e., it is a polynomialtime approximation scheme (PTAS). In terms of approximation, our algorithm is best possible since the problem is strongly NP-hard even if there are only two different reservation costs [START_REF] Wang | Preemptive scheduling with availability constraints to minimize total weighted completion times[END_REF].

Our approach is inspired by a recent PTAS for scheduling on a machine of varying speed [START_REF] Megow | Dual techniques for scheduling on a machine with varying speed[END_REF] and it uses some of its properties. As discussed above, there is no formal mathematical relation known between these two seemingly related problems which allows to directly apply the result from [START_REF] Megow | Dual techniques for scheduling on a machine with varying speed[END_REF]. The key is a dual view on scheduling: instead of directly constructing a schedule in the time-dimension, we first construct a dual scheduling solution in the weightdimension which has a one-to-one correspondence to a true schedule. We design an exponential-time dynamic programming algorithm which can be trimmed to polynomial time using techniques known for scheduling with varying speed [START_REF] Megow | Dual techniques for scheduling on a machine with varying speed[END_REF].

For both the makespan and the min-sum problem, job preemption is crucial for obtaining worst-case bounds. For non-preemptive scheduling, a reduction from 2-Partition shows that no approximation within a polynomial ratio is possible, unless P=NP, even if there are only two different reservation costs, 0 and ∞.

Finally, we remark that in general it is not clear that a schedule can be encoded polynomially in the input. However, for our completion-time based minimization objective, it is easy to observe that if an algorithm reserves p unit-size time slots in an interval of equal cost, then it reserves the first p slots within this interval, which simplifies the structure and output of an optimal solution.

Minimizing the makespan on unrelated machines

The standard scheduling problem without reservation R | pmtn | C max can be solved optimally in polynomial time [START_REF] Lawler | On preemptive scheduling of unrelated parallel processors by linear programming[END_REF]. We show that taking into account timevarying reservation cost does not significantly increase the problem complexity.

Consider the generalized preemptive makespan minimization problem with reservation cost. Recall that we can use every machine in a reserved time slot and pay only once. By [START_REF] Lawler | On preemptive scheduling of unrelated parallel processors by linear programming[END_REF] it is sufficient to find an optimal reservation decision.

Observation 1 Given the set of time slots reserved in an optimal solution, we can compute an optimal schedule in polynomial time.

Given an instance of our problem, let Z be the optimal makespan of the relaxed problem without reservation cost. Notice that Z is not necessarily integral. To determine an optimal reservation decision, we use the following observation.

Observation 2 Given an optimal makespan C * max for R | pmtn | C max + E, an optimal schedule reserves the Z cheapest slots before C * max . Note that we must pay full reservation cost for a used time slot, no matter how much it is utilized, and so does an optimal solution. In particular, this holds for the last reserved slot. Hence, it remains to design a procedure for computing an optimal value C * := C * max . We compute for every interval

I k = [s k , d k ), k = 1, . . . , K, an optimal point in time for C * assuming that C * ∈ I k . Start from the value C * = s k , if feasible,
with the corresponding cheapest Z reserved time slots. Notice that any of these reserved time slots that has cost e such that e > e k + 1 can be replaced by a time slot from I k leading to a solution with less total cost. Thus, if such a time slot does not exist, then s k is the best choice for C * in I k . Otherwise, let R ⊆ {1, . . . , k -1} be the index set of intervals that contain at least one reserved slot. We define I to be the interval with e = max h∈R e h and denote by r h the number of reserved time slots in I h . Replace min{r , d k -s k -r k } reserved slots from I by slots from I k and update R, I and r k . This continues until e ≤ e k + 1 or the interval I k is completely reserved, i.e., r k = d k -s k . This operation takes at most O(K) computer operations per interval to compute the best C * -value in that interval. It yields the following theorem. 3 Minimizing j (w j )C j on a single machine In this section, we consider the problem 1 | pmtn | (w j )C j +E. We design an algorithm that computes, for a given (not necessarily optimal) scheduling sequence σ, an optimal reservation decision for σ. We firstly identify structural properties of an optimal schedule, which we then exploit in a dynamic program. Based on this algorithm, we show that the unweighted problem 1 | pmtn | C j + E can be solved optimally in polynomial time and that there is a (4 + ε)-approximation algorithm for the weighted problem 1 | pmtn | w j C j + E. In principle, an optimal schedule may preempt jobs at fractional time points. However, since time slots can only be reserved entirely, any reasonable schedule uses the reserved slots entirely as long as there are unprocessed jobs. The following lemma shows that this is also true if we omit the requirement that time slots must be reserved entirely. (For the makespan problem considered in Sec. 2 this is not true.) Lemma 1. There is an optimal schedule S * in which all reserved time slots are entirely reserved and jobs are preempted only at integral points in time.

In the following, we assume that we are given a (not necessarily optimal) sequence of jobs, σ = (1, . . . , n), in which the jobs must be processed. We want to characterize an optimal schedule S * for σ, that is, in particular the optimal choice of time slots for scheduling σ. We first split S * into smaller sub-schedules, for which we introduce the concept of a split point.

Definition 1 (Split Point). Consider an optimal schedule S * and the set of potential split points P := K k=1 {s k , s k + 1} ∪ {d K }. Let S j and C j denote the start time and completion time of job j, respectively. We call a time point t ∈ P a split point for S * if all jobs that start before t also finish their processing not later than t, i.e., if {j ∈ J : S j < t} = {j ∈ J : C j ≤ t}.

Given an optimal schedule S * , let 0 = τ 1 < τ 2 < • • • < τ = d K be the maximal sequence of split points of S * , i.e. the sequence containing all split points of S * . We denote the interval between two consecutive split points τ x and τ x+1 as region R S *

x := [τ x , τ x+1 ), for x = 1, . . . , -1. Consider now any region R S * x for an optimal schedule S * with x ∈ {1, . . . , -1} and let J S *

x := j ∈ J : S j ∈ R S *

x . Note that J S * x might be empty. Among all optimal schedules we shall consider an optimal solution S * that minimizes the value

d K -1 t=0 t • y(t)
, where y(t) is a binary variable that indicates if time slot [t, t + 1) is reserved or not.

Observation 3 There is no job j ∈ J S *

x with C j ∈ R S * x ∩ P.

Namely, every

C j with C j = s k ∈ R S * x or C j = s k + 1 ∈ R S * x would make s k or s k + 1 a split point, whereas R S *
x is defined as the interval between two consecutive split points.

We say that an interval I k is partially reserved if at least one slot in I k is reserved, but not all. Lemma 2. There exists an optimal schedule S * in which at most one interval is partially reserved in R S *

x .

We are now ready to bound the unit reservation cost spent for jobs in J S * x . Let e j max be the maximum unit reservation cost spent for job j in S * . Furthermore, let ∆ x := max j∈J S *

x (e j max + j <j w j ) and let j x be the last job (according to sequence σ) that achieves ∆ x . Suppose, there are b ≥ 0 jobs before and a ≥ 0 jobs after job j x in J S *

x . The following lemma gives for every job j ∈ J S * x \ {j x } an upper bound on the unit reservation cost spent in the interval [S j , C j ). Lemma 3. Consider an optimal schedule S * . For any job j ∈ J Proof. Consider any job j := j x -with 0 < ≤ b. Suppose there is a job j for which a slot is reserved with cost e j max > e jx max + jx-1 j =j w j . Then e j max + j <j w j > e jx max + j <jx w j , which is a contradiction to the definition of job j x . Thus, e j max ≤ e jx max + jx-1 j =j w j . Now suppose, there is a slot [t, t + 1) ∈ [S j , C j ) with cost e(t) ≤ e jx max + jx-1 j =j w j that is not reserved. There must be a slot [t , t + 1) ∈ [S jx , C jx ) with cost exactly e jx max . If we reserve slot [t, t + 1) instead of [t , t + 1), then the difference in cost is non-positive, because the completion times of at least jobs (j = j x -, . . . , j x -1 and maybe also j x ) decrease by one. This contradicts either the optimality of S * or our assumption that S * minimizes

S * x \ {j x } a slot [t, t + 1) ∈ [S j , C j ) is
d K -1 t=0 t • y(t).
The proof of the statement for any job j x + with 0 < ≤ a follows a similar argument, but now using the fact that for every job j j x + we have e j max < e jx max -j-1 j =jx w j , because j x was the last job with e j max + j <j w j = ∆ x .

To construct an optimal sub-schedule, we need the following two lemmas.

Lemma 4. Let [t , t + 1) ∈ [S jx , C jx ) be the last time slot with cost e jx max that is used by job j x . If there is a partially reserved interval I k in R S * x , then either (i) I k is not the last interval of R S *

x and I k contains [t , t + 1) as its last reserved time slot or (ii) I k is the last interval of R S *

x .

Lemma 5. Let [t , t + 1) ∈ [S jx , C jx ) be the last time slot with cost e jx max that is used by job j x . There exists an optimal solution S * such that if there is a partially reserved interval

I k in R S *
x and it is the last one in R S * x , then there is no slot [t, t + 1) ∈ [S jx , C jx ) with cost at most e jx max that is not reserved.

We now show how to construct an optimal partial schedule for a given ordered job set in a given region in polynomial time. Lemma 6. Given a region R x and an ordered job set J x , we can construct in polynomial time an optimal schedule for J x within the region R x , which does not contain any other split point than τ x and τ x+1 , the boundaries of R x .

Proof. Given R x and J x , we guess the optimal combination j x , e jx max , i.e., we enumerate over all nK combinations and choose eventually the best solution.

We firstly assume that a partially reserved interval exists and it is the last one in R x (case (ii) in Lemma 4). Based on the characterization in Lemma 3 we find in polynomial time the slots to be reserved for the jobs j x -b, . . . , j x -1. This defines C jx-b , . . . , C jx-1 . Then starting job j x at time C jx-1 , we check intervals in the order given and reserve as much as needed of each next interval I h if and only if e h ≤ e jx max , until a total of p jx time slots have been reserved for processing j x . Lemma 5 justifies to do that. This yields a completion time C jx . Starting at C jx , we use again Lemma 3 to find in polynomial time the slots to be reserved for processing the jobs j x + 1, . . . , j x + a. This gives C jx+1 , . . . , C jx+a . Now we assume that there is no partially reserved interval or we are in case (i) of Lemma 4. Similar to the case above, we find in polynomial time the slots that S * reserves for the jobs j x -b, . . . , j x -1 based on Lemma 3. This defines C jx-b , . . . , C jx-1 . To find the slots to be reserved for the jobs j x + 1, . . . , j x + a, in this case, we start at the end of R x and go backwards in time. We can start at the end of R x because in this case the last interval of R x is fully reserved. This gives C jx+1 , . . . , C jx+a . Job j x is thus to be scheduled in [C jx-1 , S jx+1 ). In order to find the right slots for j x we solve a makespan problem in the interval [C jx-1 , S jx+1 ), which can be done in polynomial time (Theorem 1) and gives a solution that cannot be worse than what an optimal schedule S * does.

If anywhere in both cases the reserved intervals can not be made sufficient for processing the job(s) for which they are intended, or if scheduling the jobs in the reserved intervals creates any intermediate split point, then this j x , e jx maxcombination is rejected. Hence, we have computed the optimal schedules over all nK combinations of j x , e jx max and over both cases of Lemma 4 concerning the position of the partially reserved interval. We choose the schedule with minimum total cost and return it with its value. This completes the proof. Now we are ready to prove our main theorem.

Theorem 2. Given an instance of 1 | pmtn |

w j C j + E and an arbitrary processing sequence of jobs σ, we can compute an optimal reservation decision for σ in polynomial time.

Proof. We give a dynamic program. We define a state for every possible potential split point t ∈ P. By definition, there are 2K + 1 of them. A state also includes the set of jobs processed until time t. Given the sequence σ, this job set can be uniquely identified by the index of the last job, say j, that finished by time t. By relabeling the job set J, we can assume w.l.o.g. that σ = (1, . . . , n).

For each state (j, t) we compute and store recursively the optimal scheduling cost plus reservation cost Z(j, t) by Z(j, t) = min Z(j , t ) + z j + 1, . . . , j , [t , t) : t , t ∈ P, t < t,j , j ∈ J, j < j , where z j + 1, . . . , j , [t , t) denotes the value of an optimal partial schedule for job set {j +1, j +2, . . . , j in the region [t , t), or ∞ if no such schedule exists. This value can be computed in polynomial time, by Lemma 6. Hence, we compute Z(j, t) for all O(nK) states in polynomial time, which concludes the proof.

The following observation follows from a standard interchange argument.

Observation 4

In an optimal schedule S * for the problem 1 | pmtn | C j + E, jobs are processed according to the Shortest Processing Time First (SPT) policy.

Combining this observation with Theorem 2 gives the following corollary.

Corollary 1. There is a polynomial-time algorithm for

1 | pmtn | C j + E.
For the weighted problem 1 | pmtn | w j C j + E, there is no sequence that is universally optimal for all reservation decisions [START_REF] Epstein | Universal sequencing on an unreliable machine[END_REF]. However, in the context of scheduling on an unreliable machine there has been shown a polynomial-time algorithm that computes a universal (4 + ε)-approximation [START_REF] Epstein | Universal sequencing on an unreliable machine[END_REF]. More precisely, the algorithm constructs a sequence of jobs which approximates the scheduling cost for any reservation decision with a factor at most 4 + ε.

Consider an instance of problem 1 | pmtn | w j C j + E and compute such a universally (4 + ε)-approximate sequence. Applying Theorem 2 to σ, we obtain a schedule S with an optimal reservation decision for σ. Let S denote the schedule which we obtain by changing the reservation decision of S to the reservation in an optimal schedule S * (but keeping the scheduling sequence σ). The schedule S has cost no less than the original cost of S. Furthermore, given the reservation decision in the optimal solution S * , the sequence σ approximates the scheduling cost of S * within a factor of 4 + ε. This gives the following result.

Corollary 2. There is a (4 + ε)-approx. algorithm for 1 | pmtn | w j C j + E.

A PTAS for minimizing total weighted completion time

The main result of this section is an approximation scheme for minimizing the total weighted completion time with time-varying reservation cost.

Theorem 3. For any fixed ε > 0, there is a pseudo-polynomial time algorithm that computes a (1 + ε)-approximation for the problem 1 | pmtn | j w j C j + E. This algorithm runs in polynomial time if d K is polynomially bounded.

In the remainder of this section we describe some preliminaries, present a dynamic programming (DP) algorithm with exponential running time, and then we argue that it can be trimmed down to (pseudo-)polynomial size. As noted in the introduction, our approach is inspired by a PTAS for scheduling on a machine of varying speed [START_REF] Megow | Dual techniques for scheduling on a machine with varying speed[END_REF], but a direct application does not seem possible.

Preliminaries and scheduling in the weight-dimension

We describe a schedule S not in terms of completion times C j (S), but in terms of the remaining weight function W S (t) which, for a given schedule S, is defined as the total weight of all jobs not completed by time t. Based on the remaining weight function we can express the cost for any schedule S as

∞ 0 W S (t) = j∈J w j C j (S) .
This has a natural interpretation in the standard 2D-Gantt chart, which was originally introduced in [START_REF] Eastman | Bounds for the optimal scheduling of n jobs on m processors[END_REF].

For a given reservation decision, we follow the idea of [START_REF] Megow | Dual techniques for scheduling on a machine with varying speed[END_REF] and implicitly describe the completion time of a job j by the value of the function W at the time that j completes. This value is referred to as the starting weight S w j of job j. In analogy to the time-dimension, the value C w j := S w j + w j is called completion weight of job j. When we specify a schedule in terms of the remaining weight function, then we call it a weight-schedule, otherwise a time-schedule. Other terminologies, such as feasibility and idle time, also translate from the timedimension to the weight-dimension. A weight-schedule is called feasible if no two jobs overlap and the machine is called idle in weight-dimension if there exists a point w in the weight-dimension with w / ∈ S w j , C w j for all jobs j ∈ J. A weight-schedule together with a reservation decision can be translated into a time-schedule by ordering the job in decreasing order of completion weights and scheduling them in this order in the time-dimension in the reserved time slots. For a given reservation decision, consider a weight-schedule S with completion weights C w 1 > • • • > C w n > C w n+1 := 0 and the corresponding completion times 0 =: C 0 < C 1 < • • • < C n for the jobs j = 1, . . . , n. We define the (scheduling) cost of a weight schedule S as n j=1 C w j+1 -C w j C j . This value equals n j=1 π S j C w j , where π S j := C j -S j , if and only if there is no idle weight. If there is idle weight, then the cost of a weight-schedule can only be greater, and we can safely remove idle weight without increasing the scheduling cost [START_REF] Megow | Dual techniques for scheduling on a machine with varying speed[END_REF].

Dynamic programming algorithm

Let ε > 0. Firstly, we apply standard geometric rounding to the weights to gain more structure on the input, i.e, we round the weights of all jobs up to the next integer power of (1 + ε), by losing at most a factor (1 + ε) in the objective value. Furthermore, we discretize the weight-space into intervals of exponentially increasing size: we define intervals

WI u := [(1 + ε) u-1 , (1 + ε) u ) for u = 1, . . . , ν with ν := log 1+ε j∈J w j .
Consider a subset of jobs J ⊆ J and a partial weight-schedule of J . In the dynamic program, the set J represents the set of jobs at the beginning of a corresponding weight-schedule, i.e., if j ∈ J and k ∈ J \ J , then C w j < C w k . As discussed in Sec. 4.1, a partial weight-schedule S for the jobs in J together with a reservation decision for all jobs in J can be translated into a time-schedule. Note that the makespan of this time-schedule is completely defined by the reservation decision and the total processing volume j∈J p j . Moreover, knowing the last p(J ) := j∈J p j reserved slots is sufficient for scheduling the jobs in J in the time-dimension, since we know that the first job in the weight-schedule finishes last in the time-schedule, i.e., at the makespan. This gives a unique completion time C j and a unique execution time π S j := C j -S j for each job j ∈ J . The total scheduling and reservation cost of this partial schedule is j∈J π S j C w j + E. Let F u := {J u ⊆ J : j∈Ju w j ≤ (1 + ε) u }. The set F u contains all the possible job sets J u that can be scheduled in WI u or before. With every possible pair (J u , t), J u ∈ F u and t ∈ [0, d K ), we associate a recursively constructed weight-schedule together with a reservation decision starting at time t so that the current scheduling and reservation cost is a good approximation of the optimal total cost for processing the set J u starting at t. More precisely, given a u ∈ {1, . . . , ν}, a set J u ∈ F u , and a time point t ∈ [0, d K ), we create a table entry Z(u, J u , t) that represents a (1 + O(ε))-approximation of the scheduling and reservation cost of an optimal weight-schedule of J u subject to C w j ≤ (1 + ε) u for all j ∈ J u and S j ≥ t for all j ∈ J u . Initially, we create table entries Z(0, ∅, t) := 0 for all t = 0, . . . , d K and we define F 0 = {∅}. With this, basically, we control the makespan of our time-schedule.

The table entries in iteration u are created based on the table entries from iteration u -1 in the following way. Consider candidate sets J u ∈ F u and J u-1 ∈ F u-1 , a partial weight-schedule S of J u , in which the set of jobs with completion weight in WI u is exactly J u \ J u-1 , and two integer time points t, t with t < t .

We let AP X u (J u \ J u-1 , [t, t )) denote a (1 + ε)-approximation of the minimum total cost (for reservation and scheduling) when scheduling job set J u \J u-1 in the time interval [t, t ), i.e.,

AP X u (J u \ J u-1 , [t, t )) := (1 + ε) u • (t -t) + RES(J u \ J u-1 , [t, t )) ,
where

RES(J u \ J u-1 , [t, t )) denotes the cost of the p(J u \ J u-1 ) cheapest slots in the interval [t, t ). If p(J u \ J u-1 ) > t -t, then we set RES(J u \ J u-1 , [t, t ))
to infinity to express that we cannot schedule all jobs in J u \ J u-1 within [t, t ).

Based on this, we compute the table entry Z(u, J u , t) with J u ∈ F u according to the following recursive formula

Z(u, J u , t) := min {Z(u -1, J u-1 , t ) + AP X u (J u \ J u-1 , [t, t )) : J u-1 ∈ F u-1 , J u-1 ⊆ J u , t ≤ t } .
We return Z(ν, J, 0) after iteration ν. From Z(ν, J, 0) we can construct a schedule and its reservation decision by backtracking.

Notice that the values AP X u (J u \ J u-1 , [t, t )) do not depend on the entire schedule, but only on the time interval [t, t ) and the total processing volume of jobs in J u \ J u-1 . Since we approximate the scheduling cost by a factor 1 + ε and determine the minimum reservation cost, the dynamic programming algorithm obtains the following result.

Lemma 7. The DP computes a (1 + O(ε))-approximate solution.

Trimming the state space

The set F u , containing all possible job sets J u , is of exponential size, and so is the DP state space. In the context of scheduling with variable machine speed, it has been shown in [START_REF] Megow | Dual techniques for scheduling on a machine with varying speed[END_REF] how to reduce the set F u for a similar DP (without reservation decision, though) to one of polynomial size at only a small loss in the objective value. In general, such a procedure is not necessarily applicable to our setting because of the different objective involving additional reservation cost and the different decision space. However, the compactification in [START_REF] Megow | Dual techniques for scheduling on a machine with varying speed[END_REF] holds independently of the speed of the machine and, thus, independently of the reservation decision of the DP (interpret non/reservation as speed 0/1). Hence, we can apply it to our cost aware scheduling framework and obtain a PTAS. For more details on the procedure we refer to the full version.

Open problems

Our PTAS for the weighted problem runs in polynomial time when d K is polynomially bounded. Otherwise, the scheme is a "PseuPTAS". The question is if, by a careful analysis of the structure of optimal solutions, we can avoid the dependence of the running time on d K , as in our dynamic program from Sec. 3.

Furthermore, it would be interesting to algorithmically understand other scheduling problems in the model of time-varying reservation cost. An immediate open question concerns the problems considered in this paper when there are release dates present. In the full version we show that the makespan problem 1 | r j , pmtn | C max + E can be solved in polynomial time. We can also solve R | pmtn, r j | C max optimally if we allow fractional reservation. The seemingly most simple open problem in our (integral) model is 1 | r j , pmtn | j C j + E. While the problem without reservation cost can be solved optimally in polynomial time, the complexity status in the time-varying cost model is unclear, even with only two different unit reservation costs.

Machine-individual time-slot reservation opens a different stream of research. While a standard LP can be adapted for optimally solving R | pmtn, r j | C max with fractional reservation cost, the integrality gap is unbounded for our model.

Theorem 1 .

 1 The scheduling problem R | pmtn | C max + E can be solved in polynomial time equal to the running time required to solve an LP for R | pmtn | C max without reservation cost plus O(K 2 ).

  reserved if and only if the cost of [t, t + 1) satisfies the upper bound given in the table below.

	jx -b	. . .	jx -1	jx + 1	. . .	jx + a
	≤ e jx max + jx-1 j =jx-b w j . . . ≤ e jx max + wj x -1	< e jx max -wj x . . . < e jx max -jx+a-1 j =jx	w j