# Approximation results on resource leveling problems

Pascale Bendotti, Luca Brunod Indrigo, Philippe Chrétienne, Bruno Escoffier

► To cite this version:

Pascale Bendotti, Luca Brunod Indrigo, Philippe Chrétienne, Bruno Escoffier. Approximation results on resource leveling problems. Theoretical Computer Science, 2025, 1053, pp.115430. 10.1016/j.tcs.2025.115430. hal-05154972

HAL Id: hal-05154972

https://hal.science/hal-05154972v1

Submitted on 9 Jul 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_2.png" /></figure>

# Approximation results on resource leveling problems

Pascale Bendotti<sup>a,b, ID</sup>, Luca Brunod-Indrigo<sup>a,b, ID, *</sup>, Philippe Chrétienne<sup>b</sup>,
Bruno Escoffier<sup>b, ID</sup>

<figure><img src="image_3.png" /></figure>

## ARTICLE INFO

Section Editor: Pinyan Lu

Handling Editor: Vincenzo Bonifaci

**Keywords:**

Scheduling

Resource leveling

Approximation

## ABSTRACT

This work deals with resource leveling problems. A set of jobs is given as well as a resource level representing a capacity that may be exceeded at some cost. Jobs have integer processing times, must be scheduled non-preemptively and consume one unit of resource while processed. More precisely, the objective to be maximized is the resource use below the resource level, i.e., the complementary of the total overload cost.

Two main families of problems are investigated: either with or without precedence constraints. The case with no precedence constraints is shown to admit an EPTAS; a quasi-linear time approximation algorithm with constant ratio $\frac{7}{8}$ is also provided. The case with precedence constraints is shown to be significantly harder to solve as it does not admit a PTAS under some classical complexity assumption. Approximation algorithms with constant ratios are provided for special cases with in-tree precedence graph or with fixed resource level.

## 1. Introduction

A standard way to handle renewable resources in project scheduling is to assume that their availability is limited by a given capacity, which may correspond to a number of workers or machines for example. In practice however, it is often the case that this capacity can be exceeded in times of need, yet with an additional cost: extra workforce can be hired, more equipment can be rented, to name a few. Scheduling while aiming at reducing such additional costs is known as resource leveling. Due to its close links with the Resource Constrained Project Scheduling Problem (RCPSP), resource leveling has drawn a lot of attention in recent papers – see [1] for a survey. Instead of minimizing the makespan under hard resource capacity constraints, as it is the case in the RCPSP, a hard deadline constraint is typically imposed on the makespan and the resource leveling objective function depends on irregularities in the resource use.

The literature proposes multiple choices of resource leveling objective functions, the relevance of which is problem specific and very much depends on the resource that is modeled. The so-called total overload cost, used in [2–6], aims at minimizing the resource use exceeding a given resource level $L \in \mathbb{N}$. For a given schedule $x$, the quantity to be minimized is $\sum_{\tau} \max(0, r_{\tau}(x) - L)$, where $r_{\tau}(x)$ denotes the resource use at time step $\tau$ in $x$, as shown by the hatched part in Fig. 1. The resource level $L$ can be interpreted as a base resource capacity that should ideally not be exceeded. Other popular choices of resource leveling objectives include the weighted

<footnote><sup>a</sup> EDF R&D, 7 boulevard Gaspard Monge, Palaiseau, 91120, France</footnote>

<footnote><sup>b</sup> Sorbonne Université, CNRS, LIP6 UMR 7606, 4 place Jussieu, Paris, 75005, France</footnote>

<footnote>* Corresponding author.</footnote>
<figure><img src="image_4.png" /><figcaption>Fig. 1. Illustration of the total overload cost for a schedule with five jobs and resource level L = 2.</figcaption></figure>

square capacities [7–9,2,3,10–12], squared changes in resource request [10,8], absolute changes in resource request [13,8,3], resource availability cost [8,14–16] and squared deviation from a threshold [10].

As variants of resource constrained scheduling problems, resource leveling problems are notoriously hard to solve. Solution methods are provided for them in the literature, in the form of heuristics [17,7,16,5,18], metaheuristics [8,10,11,15,6] and exact methods [19,20,9,2,3,13,14,4,5,18] (mostly based on MIP).

In [21], complexity results are given for a whole range of resource leveling problems with total overload cost objective and under various classical scheduling constraints. Those results show that problems remain NP-hard even with very limiting parameter restrictions (unit processing times). The present work refines these previously established complexity boundaries by providing results on the approximation side. This includes approximation algorithms for problems that were shown to be strongly NP-hard and therefore provides a quality guarantee when dealing with more realistic resource leveling problems.

## 1.1. Problem definition

For all resource leveling problems considered in this work, a set of jobs J is given. Each job i ∈ J has processing time $p_i \in \mathbb{N}$ and must be scheduled non-preemptively. The standard three-field Graham notation $\alpha|\beta|\gamma$ introduced in [22] is adapted to the context of resource leveling, as in [21], and will be used to describe the considered scheduling problems.

The $\alpha$ field, usually describing a machine environment, specifies the resource level. Resource leveling problems with resource level L are denoted by $L|\cdot|$. in the general case or $Lk|\cdot|$. when L has fixed value $k \in \mathbb{N}$.

The $\beta$ field describes the constraints. It typically includes a deadline constraint on the makespan, denoted by $C_{max} \le M$. Precedence constraints, denoted by prec in the general case, are also part of the $\beta$ field, if any.

The $\gamma$ field specifies the objective function. Just as in [21] and [23], the resource leveling objective function considered in this work is the complementary of the total overload cost, i.e., the resource use that fits under the resource level, see the gray area in Fig. 1. The objective function to be maximized, denoted by F, then is:

$$F(x) = \sum_{\tau=0}^{M-1} \min(L, r_{\tau}(x))$$

In terms of exact solution, considering the total overload cost or F as objective function is equivalent. However, in terms of approximation, the two choices of objective function differ significantly. Indeed, the total overload cost may reach value zero for non-trivial instances, which makes it unsuitable for multiplicative approximation.

## 1.2. Contributions and outline

Two main problems are studied in the present work: $L|C_{max} \le M|F$, i.e., resource leveling with deadline constraint only, and $L|prec, C_{max} \le M|F$, with additional precedence constraints. Both problems were shown to be strongly NP-hard in [21].

We first deal with $L|C_{max} \le M|F$. The problem is shown to admit an Efficient Polynomial Time Approximation Scheme (EPTAS), i.e., a PTAS whose complexity can be expressed as $f(\epsilon)poly(|I|)$ for some function $f$. Note that there is no FPTAS if $P \ne NP$ since the problem is strongly NP-hard. As EPTAS are known to be hardly applicable in practice, a quasi-linear approximation algorithm is also proposed that yields a $\frac{7}{8}$ approximation ratio. As a side result, an equivalence is shown between $L|C_{max} \le M|F$ and an early work maximization problem studied in [23]: jobs must be scheduled on parallel machines so that the total duration processed before a common due date is maximized. Both the EPTAS and the approximation algorithm for $L|C_{max} \le M|F$ can therefore be applied to this early work maximization problem, thus improving the PTAS result from [23].

As for $L|prec, C_{max} \le M|F$, a negative approximation result is given for the case of an arbitrary precedence graph that excludes the existence of an approximation scheme, provided that $NP \notin \bigcap_{\epsilon>0} BPTIME(2^{n^c})$. It is shown that an adaptation of Hu's algorithm [24] yields a $\frac{1}{2}$ approximation ratio when the precedence graph is an in-tree. Noticing that $L|prec, C_{max} \le M|F$ can be trivially approximated with ratio $\frac{1}{L}$, it has constant approximation ratio for fixed L. Better non-trivial ratios are obtained for two special
<table><caption>**Table 1**
Summary of results.</caption><thead><tr><th>Problem</th><th>Hardness results</th><th>Approximation results</th></tr></thead><tbody><tr><td>L|C<sub>max</sub> ≤ M|F</td><td>Strongly NP-hard [21]</td><td>EPTAS (Section 2.1)<br>7/8 in O(|J| log(|J|)) time</td></tr><tr><td>L|prec, C<sub>max</sub> ≤ M|F</td><td>Strongly NP-hard [21]<br>No PTAS under<br>NP ⊈ ⋂<sub>i=0</sub><sup>L</sup> BPTIME(2<sup>n</sup>)<br>(Section 3.1)</td><td>1/2 if prec = in-tree (Section 3.2)<br>APX for fixed L<br>2/3 if L = 2, 1/2 if L = 3 (Section 3.3)</td></tr></tbody></table>

cases with fixed resource level: a list algorithm is shown to yield an approximation ratio of $2/3$ for $L2|prec, C_{max} ≤ M|F$ and $3/5$ for $L3|prec, C_{max} ≤ M|F$. An overview of the results presented in this work is given in Table 1.

Section 2 deals with $L|C_{max} ≤ M|F$. An EPTAS is provided in Section 2.1. A quasi-linear approximation algorithm is described in Section 2.2. An equivalence between $L|C_{max} ≤ M|F$ and an early work maximization problem from [23] is proved in Section 2.3. Section 3 deals with $L|prec, C_{max} ≤ M|F$. A negative approximation result is given in Section 3.1. An approximation algorithm for the special case of an in-tree precedence graph is described in Section 3.2. Special cases with fixed resource level are studied in Section 3.3.

## 2. $L|C_{max} ≤ M|F$

This section provides approximation results for $L|C_{max} ≤ M|F$, which was already shown to be strongly NP-hard in [21]. It is shown that the problem admits an EPTAS. Even though some works aim at actually implementing EPTASs for scheduling (see e.g., [25,26]) it is well known that such algorithms are hardly usable for realistic instances. A quasi-linear algorithm with $7/8$ approximation ratio is therefore provided to make up for this lack of practical applicability. An equivalence between $L|C_{max} ≤ M|F$ and an early work maximization problem is shown, which allows for an extension of both the EPTAS and the approximation algorithm to this other problem.

### 2.1. An EPTAS for $L|C_{max} ≤ M|F$

In order to show the existence of an EPTAS, $L|C_{max} ≤ M|F$ is first reformulated as a partitioning problem. The approximation scheme then consists in applying standard rounding techniques to problem data and solving the resulting rounded instance using a specific integer linear program whose size depends only on the approximation ratio.

#### 2.1.1. Problem reformulation

The following proposition allows for a reformulation of $L|C_{max} ≤ M|F$ as a job partitioning problem. Note that this reformulation is specific to the case where there are no precedence constraints and cannot be used in Section 3 to deal with $L|prec, C_{max} ≤ M|F$.

In the sequel, the sum of processing times $\sum_{i \in J'} p_i$ for some $J' \subseteq J$ will be denoted by $p(J')$. Let us also denote by $\mathcal{T}$ the set of tuples containing $L$ pairwise disjoint subsets of $J$, i.e., $\mathcal{T} = \{(J_1, J_2, \dots, J_L) \mid J_l \subseteq J \ \forall l \in \{1, \dots, L\}, J_l \cap J_{l'} = \emptyset \ \forall l \neq l'\}$

**Proposition 1.** Let $I = (J, p, L, M)$ be an instance of $L|C_{max} ≤ M|F$. Let $\mathcal{X}$ denote the set of feasible schedules for $I$.

Then the following equality holds:

$$ \max_{x \in \mathcal{X}} F(x) = \max_{(J_1, J_2, \dots, J_L) \in \mathcal{T}} \sum_{l=1}^{L} \min(M, p(J_l)) $$

Furthermore, if a tuple $T \in \mathcal{T}$ maximizes the right-hand side, a schedule $x_T$ can be built from it in polynomial time that maximizes $F$.

It follows from Proposition 1 that a solution for an instance $I = (J, p, L, M)$ of $L|C_{max} ≤ M|F$ can be represented as a tuple $T = (J_1, J_2, \dots, J_L)$ of disjoint subsets of $J$.

Proposition 1 is proved using two lemmas: it is shown that a schedule can be deduced from a tuple (Lemma 1) and conversely (Lemma 2).

**Lemma 1.** Let $I = (J, p, L, M)$ be an instance of $L|C_{max} ≤ M|F$. Let $T = (J_1, J_2, \dots, J_L)$ be a tuple of $L$ disjoint subsets of $J$.

A feasible schedule $x_T$ can be built from $T$ in polynomial time such that:

$$ F(x_T) \geq \sum_{l=1}^{L} \min(M, p(J_l)) $$

**Proof.** Let $<$ be an arbitrary total order on the jobs of $J$. Let us build a feasible schedule $x_T$ as follows:
<figure><img src="image_5.png" /><figcaption>Fig. 2. Scheduling of several job subsets. Subset $J_2$ is such that $p(J_2) \le M$ so its jobs are scheduled one after another. Subsets $J_1$ and $J_3$ are such that $p(J_1) > M$ and $p(J_3) > M$, some of their jobs are scheduled so that they end at $M$.</figcaption></figure>

- for each $l \in \{1, \dots, L\}$, schedule the jobs of $J_l$ one after the other following order $<$ while $M$ is not exceeded

- schedule every remaining job $i$ at $M - p_i$.

For every $l \in \{1, \dots, L\}$, two cases are possible:

- $J_l$ is such that $p(J_l) \le M$: the jobs of $J_l$ are simply scheduled one after the other and use one unit of resource constantly on $[0, p(J_l)]$;

- $J_l$ is such that $p(J_l) > M$: the jobs of $J_l$ are scheduled one after another while $M$ is not exceeded then the remaining jobs are scheduled so that they end at time $M$. Scheduling the jobs of $J_l$ in this way ensures that at least one unit of resource is used constantly on $[0, M]$.

This is illustrated in Fig. 2. ☐

**Lemma 2.** Let $I = (J, p, L, M)$ be an instance of $L|C_{max} \le M|F$ and let $x$ be a feasible schedule for $I$.

Then a tuple $T_x = (J_1, J_2, \dots, J_L)$ of $L$ disjoint subsets of $J$ can be built from $x$ in polynomial time such that:

$$F(x) \le \sum_{l=1}^{L} \min(M, p(J_l))$$

**Proof.** Consider the following procedure that builds a tuple $T_x = (J_1, J_2, \dots, J_L)$ of $L$ disjoint subsets of $J$ from a schedule $x$.

1: $J_l \leftarrow \emptyset \quad \forall l \in \{1, \dots, L\}$

2: $\tilde{J} \leftarrow J$

▷ Set of remaining jobs

3: **for all** $\tau \in \{0, \dots, M-1\}$ **do**

4: **for all** $l \in \{1, \dots, L\}$ **do**

5: **if** no job of $J_l$ is processed at $\tau$ and there exists $j \in \tilde{J}$ processed at $\tau$ **then**

6: $J_j = J_l \cup \{j\}$

7: $\tilde{J} = \tilde{J} \setminus \{j\}$

8: **end if**

9: **end for**

10: **end for**

11: **Return** $T_x = (J_1, J_2, \dots, J_L)$

Let $r_\tau(x)$ denote the number of jobs processed at time step $\tau$ in $x$ - so $F(x) = \sum_{\tau=0}^{M-1} \min(L, r_\tau(x))$. Let us consider the following booleans:

$$b_{\tau l} = \begin{cases} 1 & \text{if a job of } J_l \text{ is processed at time step } \tau \\ 0 & \text{otherwise} \end{cases} \quad \forall \tau \in \{0, M-1\}, \forall l \in \{1, \dots, L\}$$

Clearly, for any $\tau \in \{0, \dots, M-1\}$, $\sum_{l=1}^L b_{\tau l} \le \min(L, r_\tau(x))$. Suppose that $\sum_{l=1}^L b_{\tau l} < \min(L, r_\tau(x))$ for some $\tau \in \{0, M-1\}$, then there exists a job $i \in J \setminus \bigcup_{l=1}^L J_l$ that is being processed at time step $\tau$. This job $i$ should have been added to some $J_l$ following line 5, which is a contradiction. As a consequence, $\sum_{l=1}^L b_{\tau l} = \min(L, r_\tau(x))$ for any $\tau \in \{0, \dots, M-1\}$ and:
$$F(x) = \sum_{\tau=0}^{M-1} \min(L, r_{\tau}(x)) = \sum_{\tau=0}^{M-1} \sum_{l=1}^{L} b_{\tau l}$$

Moreover, it is also clear that for any $l \in \{1, ..., L\}$, $\sum_{\tau=0}^{M-1} b_{\tau l} \le \min(M, p(J_l))$ as the set of jobs $J_l$ cannot cover more time steps than the cumulated processing times. Then:

$$F(x) = \sum_{l=1}^{L} \sum_{\tau=0}^{M-1} b_{\tau l} \le \sum_{l=1}^{L} \min(M, p(J_l)) \quad \square$$

### 2.1.2. Efficient polynomial time approximation scheme

The following theorem states that $L|C_{max} \le M|F$ admits an EPTAS. Given a precision factor $\epsilon$, the idea of the approximation scheme is to leave apart the jobs whose processing time is smaller than $\epsilon M$ and to round the processing times of remaining jobs so that the number of distinct processing time values in the rounded instance depends only on $\epsilon$. This transformation is shown to introduce a multiplicative error of at most $\epsilon$. Solving the problem to optimality for the rounded instance then reduces to an integer linear program whose size depends only on $\epsilon$, known in bin packing and scheduling literature as configuration ILP (see e.g., [27]).

**Theorem 1.** There exists an EPTAS for $L|C_{max} \le M|F$ with running time $O(|J| \log(|J|)) + 2^{O(\frac{1}{\epsilon} \log^2(\frac{1}{\epsilon}))}$.

**Proof.** Let $I = (J, p, L, M)$ be an instance of $L|C_{max} \le M|F$ and let $\epsilon > 0$. Let $F^*$ denote the optimal objective value of $I$.

In this proof, the tuple representation of a solution of $L|C_{max} \le M|F$ will be used based on Proposition 1.

Let us define $J_{small}$ as the set of “small” jobs whose processing time is less than $\epsilon M$, i.e., $J_{small} = \{i \in J | p_i < \epsilon M\}$. Let $I_{big} = (J_{big} = J \setminus J_{small}, p, L, M)$ be an instance of $L|C_{max} \le M|F$ obtained from $I$ by removing the jobs of $J_{small}$ and let $F^*_{big}$ denote its optimal value. The claim is that an $\epsilon$-approximated solution of $I$ can be built from an $\epsilon$-approximated solution of $I_{big}$. Indeed, suppose that a solution $(J_1, J_2, ..., J_L)$ of $I_{big}$ is given, such that $\sum_{l=1}^{L} \min(M, p(J_l)) \ge (1 - \epsilon)F^*_{big}$. Let us add the jobs of $J_{small}$ according to the following procedure:

1. $J' \leftarrow J_{small}$

2. **while** there exists $j \in J'$ and $l \in \{1, ..., L\}$ such that $p_j + p(J_l) \le M$ **do**

3. $J_l = J_l \cup \{j\}$

4. $J' = J' \setminus \{j\}$

5. **end while**

6. $J_1 = J_1 \cup J'$

Two cases are possible:

- All the jobs of $J'$ can be added in the While loop, in which case

$$\sum_{l=1}^{L} \min(M, p(J_l)) \ge (1 - \epsilon)F^*_{big} + p(J_{small}) \ge (1 - \epsilon)F^*$$

- Not all jobs of $J'$ can be added in the While loop, in which case $p(J_l) \ge (1 - \epsilon)M$ for every $l \in \{1, ..., L\}$ so

$$\sum_{l=1}^{L} \min(M, p(J_l)) \ge (1 - \epsilon)LM \ge (1 - \epsilon)F^*$$

Suppose then w.l.o.g. that every job $i \in J$ is such that $p_i \ge \epsilon M$, i.e. $J_{big} = J$. Let us build an instance $\tilde{I} = (J, \tilde{p}, L, M)$ from $I$ by rounding processing times as follows:

$$\tilde{p}_i = (1 - \epsilon)^k M$$

where $k$ is such that $(1 - \epsilon)^{k+1} M < p_i \le (1 - \epsilon)^k M$. Using the assumption that $p_i \ge \epsilon M$ for every $i \in J$, there are at most $K = [\log_{1-\epsilon}(\epsilon)]$ distinct $\tilde{p}_i$ values. Furthermore, any solution $(J_1, J_2, ..., J_L)$ of $I$ satisfies the following inequalities:

$$(1 - \epsilon) \sum_{l=1}^{L} \min(M, \sum_{i \in J_l} \tilde{p}_i) \le \sum_{l=1}^{L} \min(M, p(J_l)) \le \sum_{l=1}^{L} \min(M, \sum_{i \in J_l} \tilde{p}_i)$$

In other words, an optimal solution of $\tilde{I}$ yields an $\epsilon$-approximation for instance $I$.

Using again the assumption that $p_i \ge \epsilon M$ for every $i \in J$, any subset $J' \subseteq J$ with $|J'| \ge \frac{1}{\epsilon}$ satisfies $\sum_{i \in J'} \tilde{p}_i \ge p(J') \ge M$. It then suffices to consider solutions of $\tilde{I}$ with job subsets of at most $\frac{1}{\epsilon}$ jobs, since adding more jobs cannot further improve the objective value. Due to the rounding of processing times, a job subset $J' \subseteq J$ can be described by a tuple $(n_1, n_2, ..., n_K) \in \mathbb{N}^K$, where $n_k$ is the number of jobs with rounded processing time $(1 - \epsilon)^{k-1} M$. The set $C$ of such tuples has cardinality $O(\frac{1}{\epsilon^K})$.
Finding an optimal solution for instance $\tilde{I}$ then reduces to solving a configuration Integer Linear Program. For each configuration, i.e., each element of $C$, an integer variable decides how many times it is used in an optimal solution of $\tilde{I}$. The integer linear program is as follows:

$$ \begin{array}{ll} \max_{y} & \displaystyle\sum_{c=(n_1,n_2,\dots,n_K) \in C} F_c y_c \\ \text{s.t.} & \displaystyle\sum_{c \in C} y_c \le L \end{array} \qquad (1) $$

$$ \begin{array}{ll} & \displaystyle\sum_{c=(n_1,n_2,\dots,n_K) \in C} n_k y_c \le N_k & \forall k \in \{1, \dots, K\} \\ y_c & \in \mathbb{N} \end{array} \qquad (2) $$

where $N_k = |\{i \in J | \tilde{p}_i = (1 - \epsilon)^{k-1} M\}|$ and $F_c = \max(M, \sum_{k \in \{0, \dots, K\}} n_k(1 - \epsilon)^{k-1} M)$.

Constraint (1) ensures that at most $L$ subsets of jobs are selected (one per resource unit). Constraint (2) ensures that, for each $k \in \{1, \dots, K\}$, the number of selected jobs with rounded processing time $\tilde{p}_i = (1 - \epsilon)^{k-1} M$ does not exceed the number of such jobs in the instance. Note that all coefficients in the constraint matrix and the right-hand-side of the configuration ILP are integer but the coefficients $F_c$ of the cost vector. Assuming that $\epsilon$ is a rational number, i.e., $\epsilon = \frac{a}{b}$ with $a, b \in \mathbb{N}$ and $b > a$, then the cost vector can be multiplied by $\frac{b^K}{M}$ so that all its coefficients become integer.

Using the result from [28], an integer linear program with integral data, $V$ variables, $R$ constraints and a constraint matrix whose coefficients have absolute value at most $\Delta$ can be solved to optimality in time $O(\sqrt{R\Delta})^{2R} + O(VR)$. Since in the present case $V = O(\frac{1}{\epsilon^K})$, $R = K$ and $\Delta = \frac{1}{\epsilon}$ with $K = \log_{1-\epsilon}(\epsilon) \sim \frac{1}{\epsilon} \log(\frac{1}{\epsilon})$, it follows that:

$$ O(\sqrt{R\Delta})^{2R} = 2^{O(K \log(\frac{K}{\epsilon}))} = 2^{O(K \log(K))} = 2^{O(\frac{1}{\epsilon} \log^2(\frac{1}{\epsilon}))} $$

as well as:

$$ O(VR) = 2^{O(\log(\frac{K}{\epsilon}))} = 2^{O(K \log(\frac{1}{\epsilon}) + \log(K))} = 2^{O(\frac{1}{\epsilon} \log^2(\frac{1}{\epsilon}))} $$

The computation time for the configuration ILP is therefore $2^{O(\frac{1}{\epsilon} \log^2(\frac{1}{\epsilon}))}$.<fnref n="1" /> The transformation and rounding steps prior to solving the ILP require a $O(|J| \log(|J|))$ computation time. This results in an overall time complexity of $O(|J| \log(|J|)) + 2^{O(\frac{1}{\epsilon} \log^2(\frac{1}{\epsilon}))}$. ☐

## 2.2. A quasi-linear time $\frac{7}{8}$-approximation algorithm for $L|C_{max} \le M|F$

As it is often the case for an EPTAS, the result presented in Section 2.1 is of little practical use due to prohibitive time complexity. An efficient approximation algorithm is therefore proposed for $L|C_{max} \le M|F$.

The following natural assumptions are made without loss of generality:

- $p_i \le M$ for every $i \in J$

- $L \le |J|$

The idea of the following algorithm is strongly inspired from best fit algorithms for one dimensional bin packing problem. In this algorithm, resource units are indexed from 1 to $L$ and each of them is seen as a bin of size $M$. Jobs are processed in LPT order and are placed in the least-loaded resource unit if they fit. Placing a job in a resource unit means that it is scheduled right after the other jobs previously placed in it. When a job does not fit in any resource unit, it is scheduled at the latest possible date so that it ends at the makespan bound $M$.

Sorting the jobs of $J$ in LPT order can be done in $O(|J| \log(|J|))$ time. If an appropriate heap structure is used, finding the least-loaded resource unit at each iteration can be done in $O(\log(L))$. With the assumption that $L \le |J|$, this results in a total computation time of $O(|J| \log(|J|))$.

**Proposition 2.** BestFitLeveling has an approximation ratio of at most $\frac{7}{8}$.

**Proof.** Let $\epsilon > 0$ and let $I = (J, p, L, M)$ be an instance of $L|C_{max} \le M|F$ with four jobs defined by $J = \{1, 2, 3, 4\}$, $p = (\frac{3}{4} + \epsilon, \frac{1}{2} + \epsilon, \frac{1}{2}, \frac{1}{4})$, $L = 2$ and $M = 1$. Note that the instance is with non-integral processing times for the sake of readability, but it can be assumed integral up to a scaling factor.

<footnote n="1">¹ Note that [28] assumes that elementary operations take unit time. The multiplication of $F_c$ to get integer coefficients involves coefficients that are at most $\frac{1}{\epsilon^K}$. This induces a multiplicative factor of $polylog(\frac{1}{\epsilon^K})$, which is fine with the given complexity.</footnote>
<caption>**Algorithm 1 BestFitLeveling(J, p, L, M).**</caption>

1: **for all** $k \in \{1, \dots, L\}$ **do**
2: &nbsp;&nbsp;&nbsp;&nbsp;`l_k` ← 0
3: **end for**
4: **for all** $i \in J$ **in LPT order** **do**
5: &nbsp;&nbsp;&nbsp;&nbsp;**if** $M - \min_{k \in \{1, \dots, L\}} l_k \ge p_i$ **then**
6: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`k*` = argmin{$l_k$ | $k \in \{1, \dots, L\}$}
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`x_i` ← `l_k`
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`l_k*` = `l_k` + $p_i$
9: **else**
10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`x_i` ← $M - p_i$
11: **end if**
12: **end for**
13: **Return** `x`

<figure><img src="image_6.png" /><figcaption>**Fig. 3.** First fit leveling approximation ratio example.</figcaption></figure>

Fig. 3 shows an optimal schedule for this instance as well as the schedule returned by BestFitLeveling. It can be seen that in this example, the optimal value is $v^* = 2$ while the value for the solution given by BestFitLeveling is $v^{FFL} = \frac{7}{4} + \epsilon$. The ratio $\frac{v^{FFL}}{v^*}$ for this instance is therefore $\frac{7}{8} + \frac{\epsilon}{2}$. This being true for arbitrarily small values of $\epsilon$ proves that the approximation ratio for BestFitLeveling cannot exceed $\frac{7}{8}$. ☐

**Proposition 3.** BestFitLeveling has an approximation ratio of at least $\frac{7}{8}$.

**Proof.** Let us first introduce a few notations. When BestFitLeveling is executed, the jobs of $J$ can be divided in two disjoint sets: those that fall under the `if` condition of line 5 – namely those that fit in the resource units – and those that do not and will be denoted by $\bar{J}$. Let us denote $\lambda = |\bar{J}|$. In this proof, it can be assumed that $1 \le \lambda \le L - 1$. Indeed, if $\lambda = 0$ then all jobs fit under resource level and the solution returned by the algorithm is optimal. Similarly, if $\lambda \ge L$ then the jobs of $\bar{J}$ fill the gaps from unfilled resource units so that the solution reaches the upper bound $LM$ of the objective value and is therefore optimal.

Up to a reordering of the resource units, the solution returned by BestFitLeveling may be given the form illustrated in Fig. 4. The grey rectangles represent the loads of the bins associated to resource units. The white rectangles represent the jobs that did not fit in any resource unit during the execution of the algorithm.

Let $t_\lambda$ denote the remaining time after the jobs of the $\lambda$-th least filled resource unit, i.e., the $\lambda$-th least filled resource unit is loaded up to $M - t_\lambda$. Let also $v^{FFL}$ denote the value of the solution returned by the algorithm and $v^*$ denote the optimal value.

In this proof, two lower bounds on $v^{FFL}$ will be deduced from the specific structure of BestFitLeveling solutions and a refined upper bound on $v^*$ will be introduced. Those three inequalities will then be combined to obtain that $\frac{7}{8}v^* \le v^{FFL}$.

As illustrated in Fig. 4, the $\lambda$ jobs of $\bar{J}$ fill the gaps for the $\lambda$ least filled resource units, so the following inequality holds:

$$LM - t_{\lambda}(L - \lambda) \le v^{FFL} \qquad (4)$$

Let us denote $E = \sum_{i \in \bar{J}} (p_i - \frac{M}{2})_+$, where $(p_i - \frac{M}{2})_+ = \max(0, p_i - \frac{M}{2})$. It is clear that the value of $E$ is large when there are many “big” jobs in $\bar{J}$ – with processing time greater than $\frac{M}{2}$ – and is 0 if there are none. The quantity $E$ will now be used to refine a natural upper bound on $v^*$. Let us prove the following inequality:

$$v^* \le p(J) - 2E \qquad (5)$$
<figure><img src="image_7.png" /><figcaption>Fig. 4. General form of a First Fit Leveling schedule.</figcaption></figure>

First, if the longest job of $\bar{J}$ denoted by $\hat{i}$ is such that $p_{\hat{i}} \le \frac{M}{2}$, the inequality naturally holds since $E = 0$ in that case. Then, according to BestFitLeveling, if $\hat{i}$ is such that $p_{\hat{i}} > \frac{M}{2}$, it must be preceded in the LPT order by $L$ jobs with processing time at least $p_{\hat{i}}$ that are in $J \setminus \bar{J}$ and scheduled at time 0. In any solution, those $L$ jobs of $J \setminus \bar{J}$ are executed on an interval that contains $[M - p_{\hat{i}}, p_{\hat{i}})$ thus reaching the resource level on this interval. In any solution, a job $i$ of $\bar{J}$ verifying $p_i > \frac{M}{2}$ is being executed on the time interval $[M - p_i, p_i)$, which is of size $2(p_i - \frac{M}{2})_+$ and is included in $[M - p_i, p_i)$, as $p_i \ge \frac{M}{2}$. As a consequence, in any solution, the resource level is exceeded by at least $2 \sum_{i \in \bar{J}} (p_i - \frac{M}{2})_+ = 2E$, which proves Inequality (5).

As it can be seen in Fig. 4 again:

$$ \begin{aligned} \sum_{i \in \bar{J}} p_i &\le v^{FFL} + \sum_{i \in \bar{J}} (p_i - t_{\lambda}) \\ &\le v^{FFL} + \sum_{i \in \bar{J}} \left(\frac{M}{2} - t_{\lambda}\right) + \sum_{i \in \bar{J}} \left(p_i - \frac{M}{2}\right)_+ \\ &= v^{FFL} + \lambda \left(\frac{M}{2} - t_{\lambda}\right) + E \end{aligned} \quad (6) $$

Combining Inequalities (5) and (6) yields:

$$ v^* \le v^{FFL} + \lambda \left(\frac{M}{2} - t_{\lambda}\right) - E \le v^{FFL} + \lambda \left(\frac{M}{2} - t_{\lambda}\right) \quad (7) $$

Applying a factor $(1 - \frac{\lambda}{L})$ on Inequality (7) now yields:

$$ (1 - \frac{\lambda}{L}) v^* \le (1 - \frac{\lambda}{L}) v^{FFL} + (1 - \frac{\lambda}{L}) \lambda \left(\frac{M}{2} - t_{\lambda}\right) $$

Using Inequality (4) to get an upper bound of $-\frac{\lambda}{L}v^{FFL}$ gives:

$$ \begin{aligned} & (1 - \frac{\lambda}{L}) v^* \le v^{FFL} - \frac{\lambda}{L} (LM - t_{\lambda}(L - \lambda)) + (1 - \frac{\lambda}{L}) \lambda \left(\frac{M}{2} - t_{\lambda}\right) \\ & \Leftrightarrow v^* \le v^{FFL} + \frac{\lambda}{L} \left(v^* - \frac{M}{2}(L + \lambda)\right) \end{aligned} \quad (8) $$

It now remains to prove that $\frac{\lambda}{L} (v^* - \frac{M}{2}(L + \lambda)) \le \frac{v^*}{8}$.
$$0 \leq LM \left( \lambda - \frac{L}{2} \right)^2 \Leftrightarrow 2\lambda L^2 M - \frac{1}{4}L^3 M \leq \lambda L^2 M + \lambda^2 LM$$

$$\Leftrightarrow LM \left( \frac{\lambda}{L} - \frac{1}{8} \right) \leq \frac{\lambda M}{2L} (L + \lambda)$$

$$\Rightarrow v^* \left( \frac{\lambda}{L} - \frac{1}{8} \right) \leq \frac{\lambda M}{2L} (L + \lambda)$$

(since $v^* \leq LM$)

$$\Leftrightarrow \frac{\lambda}{L} \left( v^* - \frac{M}{2} (L + \lambda) \right) \leq \frac{v^*}{8} \quad \square$$

Combining Proposition 2 and Proposition 3 leads to the following theorem that establishes the approximation ratio of BestFitLeveling.

**Theorem 2.** The approximation ratio of BestFitLeveling is $\frac{7}{8}$.

## 2.3. Link with early work maximization

The following early work maximization problem is studied in [23]:

### Problem 1.

**Input:** A set of jobs J with processing times $(p_i)_{i \in J} \in \mathbb{N}^J$, a number $m \in \mathbb{N}$ of machines and a common due date $d \in \mathbb{N}$.

**Question:** Find a schedule x on m machines in which $\sum_{i \in J} \max(0, \min(d, x_i + p_i) - x_i)$, i.e., the total amount of work processed before d, is maximized.

Problem 1 reduces to partitioning the jobs of J in m subsets $J_1, J_2, \dots, J_m$ (one for each machine) such that

$$\sum_{l=1}^{m} \min(d, p(J_l))$$

is maximized. The subset $J_l \subseteq J$ is the subset of jobs processed on machine $l \in \{1, \dots, m\}$ and the quantity $\min(d, p(J_l))$ is the early work on machine $l$ if the jobs of $J_l$ are scheduled without idle time.

This is exactly the reformulation of $L|C_{max} \leq M|F$ from Proposition 1. The resource level L is replaced with the number of machines m and the deadline M is replaced with the common due date d. It is then clear that $L|C_{max} \leq M|F$ and Problem 1 are equivalent.

A direct consequence of this equivalence is that the EPTAS from Section 2.1.2 and the approximation algorithm from Section 2.2 can be applied to Problem 1. This improves the result from [23] that provides a PTAS for Problem 1. Note however that, in [23], the PTAS also works for a generalization of Problem 1 where the number of jobs per machine is bounded.

An equivalence between early work maximization and resource leveling was already identified in [23]. Their resource leveling problem it is restricted to unit processing times and has an additional machine environment constraint. It is therefore significantly different from the ones studied in the present work.

## 3. $L|prec, C_{max} \leq M|F$

This section deals with $L|prec, C_{max} \leq M|F$ in which jobs are now subject to precedence constraints. Precedence constraints can be represented by a directed acyclic graph $G = (J, A)$ whose vertices are the jobs of J. An arc $(i, j) \in J^2$ in the precedence graph requires job i to be completed before job j starts. It is shown that, under some complexity assumption, there is no PTAS even for a special case with unit processing times and bipartite precedence graph, namely $L|bipartite, C_{max} \leq M, p_i = 1|F$ (Section 3.1). A first approximation result is obtained for a special case where the precedence graph is an in-tree, i.e., a directed tree with outdegrees at most one: an adaptation of Hu's algorithm is shown to yield a $\frac{1}{2}$-approximation (Section 3.2). Two additional results are given for fixed resource level $L=2$ and $L=3$: a list algorithm yields an approximation ratio of $\frac{2}{3}$ and $\frac{3}{5}$ respectively (Section 3.3).

### 3.1. Approximation hardness of $L|bipartite, C_{max} \leq M, p_i = 1|F$

A special case of $L|prec, C_{max} \leq M|F$ is considered where:

1. Jobs have unit processing time $p_i = 1$

2. The precedence graph is of the form $G = (J_1 \cup J_2, A)$ with $J_1 \cap J_2 = \emptyset$ and with $A \subseteq J_1 \times J_2$

In other words, the precedence graph is bipartite with every precedence arc going from a job of $J_1$ to a job of $J_2$.

One can connect $L|bipartite, C_{max} \leq M, p_i = 1|F$ to a classical graph problem known as Balanced Bipartite Independent Set, which formalizes as follows:
<figure><img src="image_8.png" /><figcaption>Fig. 5. Case $k^* \ge an$.</figcaption></figure>

**Problem 2 (Balanced Bipartite Independent Set).**

**Input:** A bipartite graph $\tilde{G} = (J_1 \cup J_2, E)$ with $|J_1| = |J_2| = n$.

**Question:** What is the maximum size of an independent set $S$ in $\tilde{G}$ satisfying $|S \cap J_1| = |S \cap J_2|$?

An inapproximability result is given for an equivalent problem called Bipartite Clique in [29]. The following proposition is shown in [29] (see Theorem 1.1 and Appendix C.3).

**Proposition 4 ([29]).** Let $\tilde{G} = (J_1 \cup J_2, E)$ be an instance of Problem 2 with $|J_1| = |J_2| = n$. Let $2k^*$ denote the solution of Problem 2 for $\tilde{G}$.

Assuming that $NP \not\subseteq \bigcap_{\epsilon>0} BPTIME(2^{n^\epsilon})$, there exist $a, b \in \mathbb{R}$, with $0 < b < a < 1$, such that it cannot be decided in polynomial time whether $k^* \le bn$ or $k^* \ge an$.

The class $BPTIME(2^{n^\epsilon})$ contains the decision problems for which there exists a probabilistic algorithm running in $O(2^{n^\epsilon})$ time that solves any instance with probability at least $\frac{1}{3^\epsilon}$. Note that $NP \subseteq BPTIME(2^{n^\epsilon})$ for some $\epsilon < 1$ would already contradict the assumption randomized ETH (see [30]). Hence the inclusion $NP \subseteq \bigcap_{\epsilon>0} BPTIME(2^{n^\epsilon})$, i.e., $NP \subseteq BPTIME(2^{n^\epsilon})$ for any $\epsilon > 0$, is considered as very unlikely.

The following proposition gives an inapproximability result for $L|bipartite, C_{max} \le M, p_i = 1|F$.

**Proposition 5.** There exists no PTAS for $L|bipartite, C_{max} \le M, p_i = 1|F$, unless $NP \subseteq \bigcap_{\epsilon>0} BPTIME(2^{n^\epsilon})$, even if $M = 3$.

**Proof.** Let $\tilde{G}$ be an instance of Problem 2 and let $2k^*$ be the maximum size of a balanced independent set in $\tilde{G}$. Using Proposition 4 there exist $a, b \in \mathbb{R}$, with $0 < b < a < 1$, such that it cannot be decided in polynomial time whether $k^* \le bn$ or $k^* \ge an$, unless $NP \subseteq \bigcap_{\epsilon>0} BPTIME(2^{n^\epsilon})$.

Up to an addition of $2n$ nodes in $J_1$ and $J_2$, each node added to $J_1$ (resp. $J_2$) being connected to all the nodes in $J_2$ (resp. $J_1$), the size of each subset of nodes can be increased to $n' = 3n$ without changing the optimal value $2k^*$. It can therefore be assumed without loss of generality that $0 < b < a \le \frac{1}{3}$.

Let us build an instance $I = (\tilde{G}, L, M)$ of $L|bipartite, C_{max} \le M, p_i = 1|F$ as follows:

$$- L = (1 - a)n$$

$$- M = 3$$

$$- G = (J_1 \cup J_2, A) \text{ with } A = \{(i, j) \in J_1 \times J_2 \mid \{i, j\} \in E\}$$

Suppose that $k^* \ge an$. Then there exists an independent set $S$ in $\tilde{G}$ such that $|S \cap J_1| = |S \cap J_2| = an$. A feasible schedule for $I$ can be built as shown in Fig. 5.

Note that $|S| = 2an \le (1 - a)n$ since $a \le \frac{1}{3}$. Given that there are at most $L$ jobs at each time step, the schedule corresponds to an objective value of $2n$ and is optimal.

Suppose now that $k^* \le bn$. Any feasible schedule can be transformed so that it satisfies:

- there are only jobs of $J_1$ on the first time step

- there are only jobs of $J_2$ on the third time step

- the jobs scheduled on the second time step form an independent set $S$

as illustrated in Fig. 6. Such a transformation can be done in polynomial time without decreasing the objective value. If a job of $J_1$
<figure><img src="image_9.png" /><figcaption>Fig. 6. Case $k^* \le bn$.</figcaption></figure>

starts strictly after a job of $J_2$, the starting times of those jobs can be swapped without violating precedence constraints. Then, if some jobs of $J_2$ are scheduled on the first time step, it implies that all the jobs of $J_1$ are also scheduled on the first time step (with $|J_1| = n \ge L$), so the jobs of $J_2$ can be postponed without decreasing the objective value. The same reasoning applies if some jobs of $J_1$ are scheduled on the third time step.

It is clear that since $k^* \le bn$, either $|J_1 \cap S| \le bn$ or $|J_2 \cap S| \le bn$. As a consequence, either $|J_1 \setminus S| \ge (1-b)n = L + (a-b)n$ or $|J_2 \setminus S| \ge (1-b)n = L + (a-b)n$. In other words, at least $(a-b)n$ jobs do not fit under resource level $L$. This holding for any schedule results in an optimal objective value of at most $2n - (a-b)n$.

The ratio of the optimal objective value in the case $k^* \le bn$ over the optimal objective value in the case $k^* \ge an$ is at most $\frac{2n-(a-b)n}{2n} = 1 - \frac{a-b}{2}$. This gives an inapproximability ratio of $1 - \frac{a-b}{2}$. $\square$

## 3.2. An approximation algorithm for $L|in-tree, C_{max} \le M|F$

Algorithm 2, called InTreeLeveling in the sequel, is inspired from Hu's algorithm [24] and uses the same priority rule. It is to be used when the precedence graph is an in-tree. In [21], an adaptation of Hu's algorithm to resource leveling is proposed and shown to yield optimal solutions in the case of unit processing times.

In [31], Hu's algorithm is shown to be an approximation for makespan minimization when processing times are arbitrary. The additive error is at most $(1 - \frac{1}{m})p_{max}$ where $m$ is the number of machines and $p_{max}$ is the largest processing time.

It will now be shown that an adaptation of Hu's algorithm is a $\frac{1}{2}$-approximation for $L|in-tree, C_{max} \le M|F$. The general idea of the algorithm is to reduce the size of the in-tree precedence graph by gradually removing and scheduling its leaves. When possible, the number of jobs to be scheduled is chosen so that at most $L$ jobs are processed in parallel (line 7), jobs that are the furthest from the root being selected in priority. Jobs that are not yet scheduled when their latest starting time is reached are systematically scheduled (line 8), which may cause to exceed $L$ but guarantees the feasibility of the resulting solution.

**Algorithm 2** InTreeLeveling($J, G, p, L, M$).

1: Compute $\tilde{r}_i$, the latest starting time of job $i$, for every $i \in J$

2: $\tau \leftarrow 0$

3: $S \leftarrow \emptyset$

4: $U \leftarrow \{i \in J \mid \delta^{-}(i) = \emptyset\}$

5: **while** $S \neq J$ **do**

6: &nbsp;&nbsp;&nbsp;&nbsp;Let $r_{\tau}$ be the number of jobs processed at time step $\tau$

7: &nbsp;&nbsp;&nbsp;&nbsp;Select up to $(L - r_{\tau})_+$ jobs in $U$ with minimal $\tilde{r}_i$, let this subset be $S_{\tau}$

8: &nbsp;&nbsp;&nbsp;&nbsp;$S_{\tau} = S_{\tau} \cup \{i \in U \mid \tilde{r}_i = \tau\}$

9: &nbsp;&nbsp;&nbsp;&nbsp;**for all** $i \in S_{\tau}$ **do**

10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$x_i \leftarrow \tau$

11: &nbsp;&nbsp;&nbsp;&nbsp;**end for**

12: $S = S \cup S_{\tau}$

13: $\tau = \min\{\tau' > \tau \mid \exists i \in S, \tau' = x_i + p_i \text{ or } \exists i \in J, \tau' = \tilde{r}_i\}$

14: $U = \{i \in J \setminus S \mid \delta^{-}(i) \subseteq S \text{ and } x_j + p_j \le \tau \forall j \in \delta^{-}(i)\}$

15: **end while**

16: **Return** $x$

▷ current time step

▷ set of scheduled jobs

▷ ready jobs, $\delta^{-}(i)$ denotes the predecessors of job $i$

▷ Note that the selected jobs may have different $\tilde{r}_i$ values

**Example 1.** Let $k \in \mathbb{N}^*$ and $L \in \mathbb{N}^*$. Consider the instance of $L|in-tree, C_{max} \le M|F$ built as follows:
<figure><img src="image_10.png" /><figcaption>Fig. 7. In-tree leveling example.</figcaption></figure>

$$- J = \{i_{2k-1}\} \cup J_1 \cup J_{2k+1}$$

- Job $i_{2k-1}$ has processing time $2k-1$

- $J_1$ has $(2k-1)L$ jobs with processing time 1 that precede job $i_{2k-1}$

- $J_{2k+1}$ has L jobs with processing time $2k+1$

$$- M = 4k$$

Fig. 7a shows the schedule obtained by running InTreeLeveling with this instance. The *L* jobs of $J_{2k+1}$ are scheduled first since their latest starting time is minimal. No other job is scheduled until time step 2k since *L* jobs are already being processed. At time step 2k, the jobs of $J_1$ reach their latest starting time so they must all be scheduled even though the *L* jobs of $J_{2k+1}$ are still being processed. Then, job $i_{2k-1}$ that follows the jobs of $J_1$ must be scheduled at time step 2k + 1, which is its latest starting time. The resulting schedule has value $(2k+1)L + 2k - 1$.

By contrast, Fig. 7b shows an optimal schedule of value $4kL$ for the same instance.

We note that Algorithm 2 runs in quasi-linear time $O(|J|\log(|J|) + |A|)$. Indeed, for the initialization, dates $\overline{\tau}_i$ and in-degrees can be computed in linear time. A priority queue of available jobs, sorted by $\overline{\tau}_i$, is used to select the jobs in $S_\tau$, inducing a global $O(|J|\log(|J|))$ time. The computation in line 13 can be done by maintaining an ordered list of times which contains $x_i + p_i$ for jobs in *S* and dates $\overline{\tau}_j$, with a global $O(|J|\log(|J|))$ time. For line 14, one can keep track of the number of already completed predecessors for each job. This number is updated at each $\tau$, allowing for the computation of available jobs *U*. Overall this step takes $O(|J| + |A|)$ time.

**Proposition 6.** *InTreeLeveling* has an approximation ratio of at most $\frac{1}{2}$.

**Proof.** In Example 1, the optimal schedule has value $4kL$ while the result of the algorithm has value $(2k+1)L + 2k - 1$. The ratio then is $\frac{1}{2} + \frac{1}{4k} + \frac{1}{2L} - \frac{1}{4kL}$, which can be made arbitrarily close to $\frac{1}{2}$ for large enough values of *k* and *L*. $\square$

The following lemma gives structural properties of schedules built using InTreeLeveling. Those properties will later be used to provide a lower bound on the approximation ratio of InTreeLeveling.

**Lemma 3.** Let *x* be an output schedule of InTreeLeveling(*J*, *G*, *p*, *L*, *M*). For every time step $\tau$, let $J_\tau = \{i \in J | x_i \le \tau < x_i + p_i\}$ be the subset of jobs processed at $\tau$ in *x*.

The two following assertions hold for any time step $\tau$:

i) If $|J_\tau| < L$ then $|J_\tau'| < L$ for every $\tau' \ge \tau$;

ii) At most *L* jobs in $J_\tau$ are not scheduled at their latest starting time.

**Proof.** i) Suppose that $|J_\tau| < L$ at a given time step $\tau$. If $\tau$ is not among the time steps considered in the algorithm, one can consider the closest such time step before $\tau$ instead. This is without loss of generality since the time step incrementation on line 13 of the algorithm ensures that no job ends in between. Having $|J_\tau| < L$ means that when time step $\tau$ is considered in the algorithm, the width of the in-tree formed by the unscheduled jobs is strictly less than *L*. As a consequence, the number of jobs scheduled in parallel in the sequel is always strictly less than *L*.

ii) Let us prove the required assertion by induction on the time steps considered in the algorithm. This is sufficient since jobs can neither start nor end on other time steps. For $\tau = 0$, the assertion holds due to line 7 of the algorithm. Suppose now that the assertion holds up to a certain time step $\tau'$. Let $\tau'$ be the next time step considered in the algorithm. Among the jobs of $J_{\tau'}$ that are not scheduled at their latest starting time, some jobs are scheduled at $\tau'$ and the others started before. Those jobs that started before were already being processed on the previous time step $\tau$, so using the induction hypothesis gives that there are at most *L* such jobs. Due to the condition of line 7 of the algorithm, the property still holds for time step $\tau'$. $\square$
<figure><img src="image_11.png" /><figcaption>Fig. 8. General form of an InTreeLeveling schedule.</figcaption></figure>

**Proposition 7.** *InTreeLeveling has an approximation ratio of at least $\frac{1}{2}$.*

**Proof.** Lemma 3 gives some structural properties resulting from the InTreeLeveling algorithm. First, using assertion i) of Lemma 3, it is clear that there exists a time step $\tau_0$ before which the level L is constantly saturated and after which the number of jobs processed at any time step is strictly below L. The amount of resource used before $\tau_0$ is $A+B$ where $A = \tau_0 L$ and B is the amount of resource exceeding level L. Similarly, let C be the amount of resource used after $\tau_0$. This is illustrated in Fig. 8. Note that $\tau_0$ can be 0. The value of the schedule is $F(x) = A + C$. Let $F^*$ denote the optimal value of the instance and distinguish two cases:

- If $B \le A$: Using the trivial bound $F^* \le A + B + C$ yields $F^* \le 2A + C \le 2(A + C) = 2F(x)$

- If $A \le B$: Using assertion ii) of Lemma 3, it can be assumed that only job portions that reached their latest starting time contribute to B. In other words, in any feasible schedule, every job portion contributing to B is scheduled before $\tau_0$. Since at most $A = \tau_0 L$ can fit under resource level L on $[0, \tau_0]$, the level is exceeded by at least $B - A$ in any feasible schedule. The optimal value is therefore such that $F^* \le A + B + C - (B - A) = 2A + C$. It is then possible to conclude as before with $F^* \le 2A + C \le 2(A + C) = 2F(x)$. $\square$

Combining Proposition 6 and Proposition 7 yields the following theorem that establishes the approximation ratio of InTreeLeveling.

**Theorem 3.** *The approximation ratio of InTreeLeveling is $\frac{1}{2}$.*

**3.3. An approximation algorithm for $L2|prec, C_{max} \le M|F$ and $L3|prec, C_{max} \le M|F$**

Let us first notice that $L1|prec, C_{max} \le M|F$, i.e., maximizing the resource use under resource level $L=1$ is polynomial time solvable [21]. This can be done by scheduling the jobs one after another in a topological order while possible and then scheduling remaining jobs at their latest starting time. In the resulting schedule, either all jobs fit under resource level 1, in which case it is optimal for any $L \in \mathbb{N}$, or the resource use is at least 1 from time 0 to time $M$, so the schedule has value at least $M$ for any $L \ge 1$. Since the optimal value for $L|prec, C_{max} \le M|F$ is at most $LM$, solving $L1|prec, C_{max} \le M|F$ for the same instance yields a $\frac{1}{L}$ approximation ratio. A direct consequence of the above is that $L|prec, C_{max} \le M|F$ is in APX for fixed $L$.

In this section, a list scheduling algorithm is proposed and shown to improve the trivial ratio by yielding a tight approximation ratio of $\frac{2}{3}$ when $L=2$ (Theorem 4) and a tight approximation ratio of $\frac{3}{5}$ when $L=3$ (Theorem 5). It is also shown however that the approximation ratio of this same algorithm can be arbitrarily close to zero for large values of $L$.

The procedure described in Algorithm 3, called ListLeveling, is a heuristic list scheduling algorithm. The algorithm considers relevant time steps incrementally and tries to fit up to $L$ jobs on each. When the latest starting time of unscheduled jobs is reached, those are scheduled anyway to ensure feasibility, possibly exceeding resource level $L$.

**Algorithm 3 ListLeveling(J, G, p, L, M).**

1: Compute $\bar{\tau}_i$, the latest starting time of job $i$, for every $i \in J$

2: **for all** $i \in J$ **do**

3: &nbsp;&nbsp;&nbsp;&nbsp; $x_i \leftarrow \bar{\tau}_i$

4: **end for**

5: $\tau \leftarrow 0$

6: **while** $\tau < \max_{i \in J} x_i + p_i$ **do**

7: &nbsp;&nbsp;&nbsp;&nbsp; $P_\tau \leftarrow \{i \in J | x_i \le \tau < x_i + p_i\}$

8: &nbsp;&nbsp;&nbsp;&nbsp; $U_\tau \leftarrow \{i \in J | x_i > \tau, x_j + p_j \le \tau \forall j \in \delta^{-}(i)\}$

9: &nbsp;&nbsp;&nbsp;&nbsp; Select up to $(L - |P_\tau|)_+$ jobs in $U_\tau$, let this subset be $S_\tau$

10: **for all** $i \in S_\tau$ **do**

11: &nbsp;&nbsp;&nbsp;&nbsp; $x_i \leftarrow \tau$

12: **end for**

13: $\tau = \min\{\tau' > \tau | \exists i \in J, \tau' = x_i + p_i\}$

14: **end while**

15: **Return** $x$

▷ All jobs are initially scheduled at their latest starting time

▷ current time step

▷ Set of jobs being processed at time step $\tau$

▷ Set of ready jobs at time step $\tau$

▷ Selected jobs are scheduled at $\tau$
<figure><img src="image_12.png" /></figure>

<figure><img src="image_13.png" /><figcaption>Fig. 9. ListLeveling approximation ratio example.</figcaption></figure>

Schedules built using the ListLeveling algorithm have structural properties, some of which are formalized in the following lemma.

**Lemma 4.** Let $I = (J, G, p, L, M)$ be an instance of $L|prec, C_{max} \le M|F$. A schedule $x$ built from $I$ using ListLeveling satisfies:

(a) Either $x$ has makespan $M$ with no idle time steps or it is optimal with resource use never exceeding $L$.

(b) If there are $k$ jobs, with $k < L$ scheduled on a time step $\tau$ in $x$, then every job starting strictly after $\tau$ is a successor of one of those $k$ jobs.

(c) If there are $k$ jobs, with $k > L$ scheduled on a time step in $x$, then at least $k - L$ of those jobs are scheduled at their latest starting time.

**Proof.** (a) First, it is clear that ListLeveling yields schedules with no idle time steps. If less than $L$ jobs are scheduled in parallel at any time step in $x$, then $x$ is optimal. If there are time steps with strictly more than $L$ jobs scheduled in parallel in $x$, let $\tau$ be the first such time step. The only case in which ListLeveling schedules more than $L$ jobs in parallel is when some jobs reach their latest starting time. Let then $i$ be one of those jobs. By definition of the latest starting time, there exists a chain of jobs starting with job $i$ along which the sum of processing times is $M - \tau$. The makespan of $x$ therefore reaches $M$.

(b) Suppose that $k$ jobs, with $k < L$ are scheduled on a time step. If there were available jobs, i.e. jobs independent from the $k$ jobs, yet to be scheduled, up to $L - k$ of those would have been selected and scheduled in parallel, following Line 7 of the algorithm.

(c) Following Line 7 of the algorithm, at most $L$ jobs that are not scheduled at their latest starting time can be processed in parallel on any time step. Thus, if there are $k$ jobs, with $k > L$ scheduled on a time step in $x$, at least $k - L$ of those jobs are scheduled at their latest starting time. $\square$

A consequence of Lemma 4 (a) is that any non-optimal schedule built with ListLeveling uses at least one unit of resource on each time step from 0 to $M - 1$. For problems in which resource level $L$ is fixed, this guarantees a constant approximation ratio of at least $\frac{1}{L}$. It will now be shown that the ListLeveling algorithm yields a constant approximation ratio of $\frac{2}{3}$ for $L2|prec, C_{max} \le M|F$ and $\frac{3}{5}$ for $L3|prec, C_{max} \le M|F$.

### 3.3.1. Analysis of ListLeveling for $L = 2$

**Proposition 8.** ListLeveling has approximation ratio at most $\frac{2}{3}$ for $L2|prec, C_{max} \le M|F$. This remains true when $p_i = 1$ for every $i \in J$.

**Proof.** Let $k \in \mathbb{N}^*$. Let us build an instance of $L2|prec, C_{max} \le M, p_i = 1|F$ as follows:

$$- J = J^{\text{2two chains}} \cup J^{\text{chain}} \cup J'$$

- $J^{\text{two chains}}$ has $2k$ jobs forming two independent chains of $k$ jobs

- $J^{\text{chain}}$ has $2k$ jobs forming a chain

- $J'$ has $2k + 2$ independent jobs that follow the jobs of $J^{\text{chain}}$

$$- M = 3k + 1$$

An optimal schedule for this instance can be built as shown in Fig. 9a. The jobs of $J^{\text{two chains}}$ are scheduled one after another from 0 to $2k$. The jobs of $J^{\text{chain}}$ are scheduled one after another from 0 to $2k$. Two jobs of $J'$ are scheduled on each of the remaining $k + 1$ time steps. All jobs fit under resource level $L = 2$, giving an optimal objective value of $|J| = 6k + 2$.

Using the ListLeveling algorithm for this instance can result in the schedule shown in Fig. 9b. The two chains of $J^{\text{two chains}}$ are scheduled in parallel from 0 to $k$. Then, the algorithm has no choice but to schedule the jobs of $J^{\text{chain}}$ and the jobs of $J'$ at their latest starting time. As a result, the jobs of $J^{\text{chain}}$ are scheduled from $k$ to $3k$ and all the jobs of $J'$ are scheduled on the last time step. The objective value of this schedule is $4k + 2$.

The ratio is $\frac{2k+1}{3k+1}$, which can be arbitrarily close to $\frac{2}{3}$ for large enough values of $k$. $\square$

<figure><img src="image_14.png" /></figure>

**Proposition 9.** ListLeveling has approximation ratio at least $\frac{2}{3}$ for $L2|prec, C_{max} \le M|F$.

**Proof.** Let $I = (J, G, p, M)$ be an instance of $L2|prec, C_{max} \le M|F$ and let $x$ be a feasible schedule for $I$ built using the ListLeveling algorithm. Using Lemma 4 (a), it can be assumed that $x$ is of makespan $M$ and without idle time step.
<figure><img src="image_15.png" /><figcaption>Fig. 10. Schedule decomposition for $L = 2$.</figcaption></figure>

Let us consider that each job of $J$ is composed of $p_i$ job portions of one time unit scheduled one after another. In this proof, the notion of job predecessor and successor is extended to job portions, as if the portions of a job were a chain of jobs with unit processing time. Let $P_1$ denote the portions of jobs that are scheduled alone on a time step. On each time step where at least two job portions are scheduled, choose two and let $P_2$ denote the resulting set. The remaining job portions are denoted by $P_3$. The decomposition of schedule $x$ is illustrated in Fig. 10. Since there are no idle time steps, $M = |P_1| + \frac{1}{2}|P_2|$ and $F(x) = |P_1| + |P_2| = 2M - |P_1|$. Using Lemma 4 (c), up to a reordering, it can be assumed that all job portions in $P_3$ belong to jobs scheduled at their latest starting time.

The claim is that job portions of $P_1$ cannot be scheduled in parallel with job portions in $P_3$. First, using Lemma 4 (b), if a job portion is in $P_1$, then it is a predecessor of all job portions scheduled after it in $x$. This implies in particular that the job portions of $P_1$ form a chain. Then, since job portions in $P_3$ belong to jobs scheduled at their latest starting time, each such job portion is on a critical path, i.e., a chain of job portions scheduled on each time step up to $M-1$. A critical path from a job portion necessarily goes through the job portions of $P_1$ scheduled afterwards. As a consequence, each job portion in $P_1$ is a successor of job portions of $P_3$ scheduled before it and a predecessor of job portions of $P_3$ scheduled after it. Therefore, a job portion in $P_1$ cannot be scheduled in parallel with any job portion in $P_3$ in any feasible schedule.

Since the job portions of $P_1$ form a chain, they cannot be scheduled in parallel of each other. Since the job portions of $P_1$ cannot be scheduled in parallel with job portions of $P_3$ either, only job portions of $P_2$ can be scheduled in parallel with them. In other words, the value of schedule $x$ can only be improved by scheduling job portions of $P_2$ in parallel with job portions of $P_1$, which means that $F(x)$ can at best be increased by $|P_2|$. Therefore, the value of an optimal schedule $x^*$ satisfies: $F(x^*) \le F(x) + |P_2| = 4M - 3|P_1|$. Moreover, it is clear that $F(x^*) \le 2M$. Summing both inequalities yields: $2F(x^*) \le 6M - 3|P_1|$. Using that $F(x) = 2M - |P_1|$, it holds that $2F(x^*) \le 3F(x)$, which is the expected result. $\square$

Combining Proposition 8 and Proposition 9 yields the following theorem that establishes the approximation ratio of ListLeveling for $L2|prec, C_{max} \le M|F$.

**Theorem 4.** *ListLeveling has approximation ratio $\frac{2}{3}$ for $L2|prec, C_{max} \le M|F$.*

### 3.3.2. Analysis of ListLeveling for $L = 3$

**Proposition 10.** *ListLeveling has approximation ratio at most $\frac{3}{5}$ for $L3|prec, C_{max} \le M|F$. This remains true when $p_i = 1$ for every $i \in J$.*

*Proof.* Let $k \in \mathbb{N}^*$. Let us build an instance of $L3|prec, C_{max} \le M, p_i = 1|F$ as follows:

- $J = J' \cup J^{\text{chain}} \cup J''$

- $J'$ has $6k$ independent jobs

- $J^{\text{chain}}$ has $3k$ jobs forming a chain

- $J''$ has $6k+3$ independent jobs that follow the jobs of $J^{\text{chain}}$

- $M = 5k+1$

An optimal schedule for this instance can be built as shown in Fig. 11a. One job of $J^{\text{chain}}$ and two jobs of $J'$ are scheduled on each of the first $3k$ time steps. Three jobs of $J''$ are scheduled on each of the remaining $2k+1$ time steps. All jobs fit under resource level $L=3$, giving an optimal objective value of $|J| = 15k+3$.

Using the ListLeveling algorithm for this instance can result in the schedule shown in Fig. 11b. Three jobs of $J'$ are scheduled on each of the first $2k$ time steps. Then, the algorithm has no choice but to schedule the jobs of $J^{\text{chain}}$ and $J''$ at their latest starting time. As a result, one job of $J^{\text{chain}}$ is scheduled on each of the following $3k$ time steps and all the jobs of $J''$ are scheduled on the last time step. The objective value of this schedule is $9k+3$.

The ratio is $\frac{3k+1}{5k+1}$, which can be arbitrarily close to $\frac{3}{5}$ for large enough values of $k$. $\square$

<figure><img src="image_16.png" /></figure>

**Proposition 11.** *ListLeveling has approximation ratio at least $\frac{3}{5}$ for $L3|prec, C_{max} \le M|F$.*
<figure><img src="image_17.png" /></figure>

<figure><img src="image_18.png" /><figcaption>Fig. 11. ListLeveling approximation ratio example.</figcaption></figure>

<figure><img src="image_19.png" /><figcaption>Fig. 12. Schedule decomposition for $L = 3$.</figcaption></figure>

**Proof.** Let $I = (J, G, p, M)$ be an instance of $L3|prec, C_{max} \le M|F$ and let $x$ be a feasible schedule for $I$ built using the ListLeveling algorithm. Using Lemma 4 (a), it can be assumed that $x$ is of makespan $M$ and without idle time step.

Let us consider that each job of $J$ is composed of $p_i$ job portions of one time unit scheduled one after another. In this proof, the notion of job predecessor and successor are extended to job portions, as if the portions of a job were a chain of jobs with unit processing time. The notion of job starting time is extended similarly, the starting time of a job portion $i$ in schedule $x$ being denoted by $x_i$. Let $P_1$ denote the portions of jobs that are scheduled on time steps where exactly one portion of job is scheduled. Similarly, let $P_2$ denote the portions of jobs scheduled on time steps where exactly two portions of jobs are scheduled. On each time step where at least three job portions are scheduled, choose three and let $P_3$ denote the resulting set. The remaining job portions are denoted by $P_4$. The decomposition of schedule $x$ is illustrated in Fig. 12. Since there are no idle time steps, $M = |P_1| + \frac{1}{2}|P_2| + \frac{1}{3}|P_3|$ and $F(x) = |P_1| + |P_2| + |P_3| = 3M - 2|P_1| - \frac{1}{2}|P_2|$. Using Lemma 4 (c), up to a reordering, it can be assumed that all job portions in $P_4$ belong to jobs scheduled at their latest starting time.

Let $x^*$ be an optimal schedule for $I$. The general idea of this proof is to build a set $S \subseteq P_2$ such that:

- the job portions of $P_1 \cup S$ form a chain;

- if $S'$ denotes the job portions of $P_2$ scheduled on the same time step as a job portion of $S$, only job portions in $P_3 \cup S'$ can be scheduled in parallel with job portions of $P_1 \cup S$ in $x^*$.

If such a set $S$ exists, it is shown that the objective value of an optimal schedule $x^*$ can be bounded as follows:

$$ F(x^*) \le \underbrace{|P_1| + |S|}_{\text{Job portions of } P_1 \cup S} + \underbrace{3 \left( M - |P_1| - \frac{1}{2}|P_2| \right)}_{\substack{\text{Job portions scheduled with } P_1 \cup S \\ P_3}} + \underbrace{|S|}_{S'} + \underbrace{3(M - |P_1| - |S|)}_{\text{Remaining time steps}} \\ \le 6M - 5|P_1| - \frac{3}{2}|P_2| - |S| \qquad (9) $$

Indeed, since the job portions of $P_1 \cup S$ form a chain, they are scheduled on $|P_1| + |S|$ distinct time steps in $x^*$. By hypothesis, only job portions of $P_3 \cup S'$ can be scheduled on the same time steps as job portions of $P_1 \cup S$. Given that $|P_3| = 3(M - |P_1| - \frac{1}{2}|P_2|)$ and $|S'| = |S|$, the contribution to the objective function of those time steps is at most $|P_1| + |S| + 3(M - |P_1| - \frac{1}{2}|P_2|) + |S|$. As for the $M - |P_1| - |S|$ remaining time steps, their contribution to the objective function is at most 3 each, so $3(M - |P_1| - |S|)$ in total. Using Inequality (9) as well as the natural upper bound $F(x^*) \le 3M$ yields the following result:

$$ \begin{aligned} \frac{3}{5} F(x^*) &= \frac{2}{5} F(x^*) + \frac{1}{5} F(x^*) \\ &\le \frac{2}{5} \left( 6M - 5|P_1| - \frac{3}{2}|P_2| - |S| \right) + \frac{3}{5} M \\ &= 3M - 2|P_1| - \frac{3}{5}|P_2| - \frac{2}{5}|S| \end{aligned} $$
$$ \begin{aligned} & \leq 3M - 2|P_1| - \frac{1}{2}|P_2| \\ &= F(x) \end{aligned} $$

which is the expected approximation ratio.

Let us then find the appropriate set S. First let us build a chain of job portions C that contains all job portions of P₁ and exactly half of the job portions in P₂ (on each time step with two job portions of P₂, one should be in C). Let l be the earliest job portion in P₁ ∪ P₂ to be scheduled at its latest starting time in x. By definition, there exists a chain of successors of l scheduled on each time step until the end of the schedule. Selecting the jobs of P₁ ∪ P₂ in this chain gives a chain with the required properties starting in l. Using Lemma 4 (b), if a job portion is in P₁, then it is a predecessor of all job portions scheduled after it in x. Similarly, two job portions of P₂ scheduled on the same time step are such that any job portion scheduled after is a successor of one of the two. The chain C is obtained from the previously built chain starting in l by extending it backwards recursively so that it includes all job portions of P₁ and half of the job portions of P₂. In the example of Fig. 12, the chain C is shown in gray.

Let l, l' ∈ P₂ be a pair of job portions such that xᵢ = xᵢ', with l ∈ C and l' ∉ C. Let S ⊆ P₂ denote the set of such l for which xᵢ* < xᵢ'.

and such that l' is not scheduled at its latest starting time in x. Let also S' denote the set of job portions of P₂ that are scheduled on the same step as a job portion of S. The claim is that S satisfies the conditions required in the previous part of the proof, i.e., only job portions of P₃ ∪ S' can be scheduled on the same time step as a job portion in P₁ ∪ S. This is proven with the following points:

1. If $l \in P_1 \cup S$ and a job portion $l''$ are such that $x_i < x_{i''}$, then $x_i^* < x_{i''}^*$:

Indeed, if $l \in P_1$, using Lemma 4 (b), it is a predecessor of any job portion scheduled after it in x, so l is a successor of l''. If $l \in S$, then by definition of S, there exists a job portion $l' \in S'$ such that $x_i = x_{i'}$ and $x_i^* < x_{i'}^*$. Since l'' is scheduled after l (and l') in x, it is a successor of either of the two. If l'' is a successor of l, then $x_i^* < x_{i''}^*$. If l'' is a successor of l', then $x_i^* < x_{i'}^* < x_{i''}^*$.

2. If $l \in P_1 \cup S$ and a job portion $l''$ are such that $x_{i'} < x_i$ and $l''$ is scheduled at its latest starting time, then $x_{i''}^* < x_i^*$:

Since l'' is scheduled at its latest starting time in x, there exists a chain of successors of l'' scheduled on each time step from $x_{i''} + 1$ to $M - 1$. Note that all the job portions of this chain are scheduled at their latest starting time. This chain necessarily contains l. It is clear if $l \in P_1$, as the chain must contain all jobs of P₁ scheduled after l''. If $l \in S$, the chain contains either l or the job portion l' scheduled on the same time step as l. However, by construction of S, l' is not scheduled at its latest starting time so it cannot belong to the chain from l'', so the chain contains l. Therefore l is a successor of l'' and $x_{i''}^* < x_i^*$.

As a consequence, given a job portion $l \in P_1 \cup S$:

- Any job portion $l''$ such that $x_i < x_{i''}$ cannot be scheduled on the same time step as l using point 1.

- Any job portion $l'' \neq l$ in C cannot be scheduled on the same time step as l since C is a chain.

- Any job portion $l'' \in P_4$ such that $x_{i''} < x_i$ cannot be scheduled on the same time step as l using point 2 (all job portions in P₄ are scheduled at their latest starting time).

- If $l' \in P_2 \cap S$ and $l'' \in P_2 \setminus C$ are such that $x_{i'} = x_{i''} < x_i$ and $x_{i'}^* < x_{i''}^* = x_i^*$, then $l''$ cannot be scheduled at its latest starting time in x (point 2), so it belongs to S'.

In other words, only job portions in $P_3 \cup S'$ can be scheduled on the same time step as l in x. ☐

Combining Proposition 10 and Proposition 11 yields the following theorem that establishes the approximation ratio of ListLeveling for $L3|prec, C_{max} \le M|F$.

**Theorem 5.** *ListLeveling has approximation ratio $\frac{3}{5}$ for $L3|prec, C_{max} \le M|F$.*

### 3.3.3. Analysis of ListLeveling for large L

As shown by Theorem 4 and Theorem 5, the ListLeveling algorithm yields non-trivial approximation ratios when the resource level has fixed value L = 2 and L = 3 respectively. The following proposition shows that, in the general case where L is not fixed, the solution built with the ListLeveling algorithm can be of arbitrarily poor quality.

**Proposition 12.** *There is no $\epsilon > 0$ such that ListLeveling is an $\epsilon$-approximation for $L|prec, C_{max} \le M|F$. This remains true when $p_i = 1$ for every $i \in J$.*

**Proof.** Let $k, d \in \mathbb{N}^*$. Let us build an instance of $L|prec, C_{max} \le M, p_i = 1|F$ as follows:

$$ - J = I_0 \cup (\bigcup_{k'=1}^{k} \bigcup_{d'=1}^{d} I_{k'}^{d'}) \cup (\bigcup_{k'=1}^{k-1} \bigcup_{d'=1}^{d} C_{k'}^{d'}) $$

- $I_0$ has $dL$ independent jobs that precede all other jobs

- For $k' \in \{1, 2, \dots, k\}$ and $d' \in \{1, 2, \dots, d\}$, $I_{k'}^{d'}$ has L independent jobs preceding the jobs of $C_{k'}^{d'}$

- For $k' \in \{1, 2, \dots, k-1\}$ and $d' \in \{1, 2, \dots, d\}$, $C_{k'}^{d'}$ has $d-1$ jobs forming a chain and preceding the jobs of $I_{k'+1}^{d'}$

- $M = kd + 1$
<figure><img src="image_20.png" /><figcaption>Fig. 13. Counter example.</figcaption></figure>

<figure><img src="image_21.png" /><figcaption>Fig. 14. Counter example optimal schedule.</figcaption></figure>

This construction is illustrated in Fig. 13.

An optimal schedule for this instance can be built as shown in Fig. 14. All the jobs of $I_0$ are on the first time step. The remaining jobs are shifted such that each $I_{k'}^{d'}$ is scheduled its own time step. This results in at least $L$ jobs being scheduled on each time step, giving an optimal objective value of $ML = kdL + L$.

Using the ListLeveling algorithm on this instance results in the schedule shown in Fig. 15. On each of the first $d$ time steps, $L$ jobs of $I_0$ are scheduled and all remaining jobs are scheduled at their latest starting times. As a result, for every $k' \in \{1, 2, \dots, k\}$, the jobs of $\bigcup_{d'=1}^{d} I_{k'}^{d'}$ are all scheduled on the same time step, thus largely exceeding $L$ jobs in parallel while only $d$ jobs are scheduled on remaining time steps. Assuming that $d \le L$, the value of this schedule is $(d+k)L + (k-1)(d-1)d$.

The ratio is $\frac{d+k}{kd+1} + \frac{(k-1)(d-1)d}{kdL+L}$, which can be arbitrarily close to 0 for large enough values of $L$, $k$ and $d$ with $d = o(L)$. $\square$
<figure><img src="image_22.png" /><figcaption>Fig. 15. Counter example ListLeveling schedule.</figcaption></figure>

The above result remains true even if Algorithm 3 is modified so that it schedules up to $L' > L$ jobs at a time. In other words, building good solutions for $L|prec, C_{max} \le M|F$ may require to schedule arbitrarily many jobs in parallel even if they have not reached their latest starting time. As a consequence, algorithms in the fashion of Algorithm 3 cannot possibly yield a constant approximation ratio when $L$ is not fixed.

## 4. Conclusion

The present work provides approximation results that refine previously existing complexity results for resource leveling problems in which the complementary of the total overload cost is maximized. It is shown that the problem without precedence constraints admits an EPTAS. An efficient quasi-linear $\frac{1}{8}$-approximation algorithm is also given. Under a classical complexity assumption, the problem with additional precedence constraints is shown not to admit a PTAS. A $\frac{1}{2}$-approximation algorithm is provided for a special case with an in-tree precedence graph. A list scheduling algorithm is shown to yield non-trivial approximation ratios when the resource level has fixed value 2 or 3. Whether there exists a constant approximation ratio for this problem when the resource level is not fixed remains an open question that could motivate further research.

## CRediT authorship contribution statement

**Pascale Bendotti:** Writing – original draft, Supervision, Project administration, Methodology, Investigation, Formal analysis, Conceptualization.
**Luca Brunod-Indrigo:** Writing – original draft, Project administration, Methodology, Investigation, Formal analysis, Conceptualization.
**Philippe Chrétienne:** Writing – original draft, Supervision, Project administration, Methodology, Investigation, Formal analysis, Conceptualization.
**Bruno Escoffier:** Writing – original draft, Supervision, Project administration, Methodology, Investigation, Formal analysis, Conceptualization.

## Declaration of competing interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.
# Data availability

No data was used for the research described in the article.

# References

[1] S. Hartmann, D. Briskorn, An updated survey of variants and extensions of the resource-constrained project scheduling problem, Eur. J. Oper. Res. 297 (2022) 1–14.

[2] J. Rieck, J. Zimmermann, T. Gather, Mixed-integer linear programming for resource leveling problems, Eur. J. Oper. Res. 221 (2012) 27–37.

[3] J. Rieck, J. Zimmermann, Exact methods for resource leveling problems, in: Handbook on Project Management and Scheduling, vol. 1, Springer, 2015, pp. 361–387.

[4] L. Bianco, M. Caramia, S. Giordani, Resource levelling in project scheduling with generalized precedence relationships and variable execution intensities, OR Spektrum 38 (2016) 405–425.

[5] T. Atan, E. Eren, Optimal project duration for resource leveling, Eur. J. Oper. Res. 266 (2018) 508–520.

[6] C. Verbeek, V. Van Peteghem, M. Vanhoucke, P. Vansteenwegen, E.-H. Aghezzaf, A metaheuristic solution approach for the time-constrained project scheduling problem, OR Spektrum 39 (2017) 353–371.

[7] S.E. Christodoulou, A. Michaelidou-Kamenou, G. Ellinas, Heuristic methods for resource leveling problems, in: Handbook on Project Management and Scheduling, vol. 1, Springer, 2015, pp. 389–407.

[8] J.L. Ponz-Tienda, A. Salcedo-Bernal, E. Pellicer, J. Benlloch-Marco, Improved adaptive harmony search algorithm for the resource leveling problem with minimal lags, Autom. Constr. 77 (2017) 82–92.

[9] J.L. Ponz-Tienda, A. Salcedo-Bernal, E. Pellicer, A parallel branch and bound algorithm for the resource leveling problem with minimal lags, Comput.-Aided Civ. Infrastruct. Eng. 32 (2017) 474–498.

[10] J. Qiao, Y. Li, Resource leveling using normalized entropy and relative entropy, Autom. Constr. 87 (2018) 263–272.

[11] H. Li, L. Xiong, Y. Liu, H. Li, An effective genetic algorithm for the resource levelling problem with generalised precedence relations, Int. J. Prod. Res. 56 (2018) 2054–2075.

[12] H. Li, X. Dong, Multi-mode resource leveling in projects with mode-dependent generalized precedence relations, Expert Syst. Appl. 97 (2018) 193–204.

[13] L. Bianco, M. Caramia, S. Giordani, The total adjustment cost problem with variable activity durations and intensities, Eur. J. Ind. Eng. 11 (2017) 708–724.

[14] S.B. Rodrigues, D.S. Yamashita, Exact methods for the resource availability cost problem, in: Handbook on Project Management and Scheduling, vol. 1, Springer, 2015, pp. 319–338.

[15] V. Van Peteghem, M. Vanhoucke, An artificial immune system algorithm for the resource availability cost problem, Flexible Serv. Manuf. J. 25 (2013) 122–144.

[16] X. Zhu, R. Ruiz, S. Li, X. Li, An effective heuristic for project scheduling with resource availability cost, Eur. J. Oper. Res. 257 (2017) 746–762.

[17] B.M. Woodworth, C.J. Willie, A heuristic algorithm for resource leveling in multi-project, multi-resource scheduling, Decis. Sci. 6 (1975) 525–540.

[18] M. Drótos, T. Kis, Resource leveling in a machine environment, Eur. J. Oper. Res. 212 (2011) 12–21.

[19] S.M. Easa, Resource leveling in construction by optimization, J. Constr. Eng. Manage. 115 (1989) 302–316.

[20] E. Demeulemeester, Minimizing resource availability costs in time-limited project networks, Manag. Sci. 41 (1995) 1590–1598.

[21] P. Bendotti, L. Brunod Indrigo, P. Chrétienne, B. Escoffier, Resource leveling: complexity of a unit execution time two-processor scheduling variant and related problems, J. Sched. (2024) 1–20.

[22] R.L. Graham, E.L. Lawler, J.K. Lenstra, A.R. Kan, Optimization and Approximation in Deterministic Sequencing and Scheduling: A Survey, Annals of Discrete Mathematics, vol. 5, Elsevier, 1979, pp. 287–326.

[23] P. Györgyi, T. Kis, A common approximation framework for early work, late work, and resource leveling problems, Eur. J. Oper. Res. 286 (2020) 129–137.

[24] T.C. Hu, Parallel sequencing and assembly line problems, Oper. Res. 9 (1961) 841–848.

[25] S. Berndt, M.A. Deppert, K. Jansen, L. Rohwedder, Load balancing: the long road from theory to practice, in: 2022 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX), SIAM, 2022, pp. 104–116.

[26] M. Akram, N. Maas, P. Sanders, D. Schreiber, Engineering optimal parallel task scheduling, in: 2025 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX), SIAM, 2025, pp. 168–180.

[27] K. Grage, K. Jansen, K.-M. Klein, An EPTAS for machine scheduling with bag-constraints, in: The 31st ACM Symposium on Parallelism in Algorithms and Architectures, 2019, pp. 135–144.

[28] K. Jansen, L. Rohwedder, On integer programming, discrepancy, and convolution, Math. Oper. Res. 48 (2023) 1481–1495.

[29] S. Khot, Ruling out PTAS for graph min-bisection, dense k-subgraph, and bipartite clique, SIAM J. Comput. 36 (2006) 1025–1071.

[30] H. Dell, T. Husfeldt, D. Marx, N. Taslaman, M. Wahlen, Exponential time complexity of the permanent and the Tutte polynomial, ACM Trans. Algorithms 10 (2014) 1–32.

[31] M.T. Kaufman, An almost-optimal algorithm for the assembly line scheduling problem, IEEE Trans. Comput. 100 (1974) 1169–1174.