# Resource Leveling: Complexity of a UET two-processor scheduling variant and
related problems

Bendotti  EDF R&D, 7 boulevard Gaspard Monge, 91120 Palaiseau, France Sorbonne
Université, CNRS, LIP6 UMR 7606, 4 place Jussieu, 75005 Paris, France  Pascale
EDF R&D, 7 boulevard Gaspard Monge, 91120 Palaiseau, France Sorbonne
Université, CNRS, LIP6 UMR 7606, 4 place Jussieu, 75005 Paris, France  Brunod
Indrigo  Sorbonne Université, CNRS, LIP6 UMR 7606, 4 place Jussieu, 75005
Paris, France  Luca  Sorbonne Université, CNRS, LIP6 UMR 7606, 4 place
Jussieu, 75005 Paris, France  Chrétienne  Sorbonne Université, CNRS, LIP6 UMR
7606, 4 place Jussieu, 75005 Paris, France  Philippe  Sorbonne Université,
CNRS, LIP6 UMR 7606, 4 place Jussieu, 75005 Paris, France  Escoffier  Sorbonne
Université, CNRS, LIP6 UMR 7606, 4 place Jussieu, 75005 Paris, France
Institut Universitaire de France  Bruno  Sorbonne Université, CNRS, LIP6 UMR
7606, 4 place Jussieu, 75005 Paris, France  Institut Universitaire de France

###### Abstract

This paper mainly focuses on a resource leveling variant of a two-processor
scheduling problem. The latter problem is to schedule a set of dependent UET
jobs on two identical processors with minimum makespan. It is known to be
polynomial-time solvable.

In the variant we consider, the resource constraint on processors is relaxed
and the objective is no longer to minimize makespan. Instead, a deadline is
imposed on the makespan and the objective is to minimize the total resource
use exceeding a threshold resource level of two. This resource leveling
criterion is known as the _total overload cost_. Sophisticated matching
arguments allow us to provide a polynomial algorithm computing the optimal
solution as a function of the makespan deadline. It extends a solving method
from the literature for the two-processor scheduling problem.

Moreover, the complexity of related resource leveling problems sharing the
same objective is studied. These results lead to polynomial or pseudo-
polynomial algorithms or $NP$-hardness proofs, allowing for an interesting
comparison with classical machine scheduling problems.

Keywords: Scheduling, resource leveling, complexity, matchings

##  1 Introduction

Most project scheduling applications involve renewable resources such as
machines or workers. A natural assumption is to consider that the amount of
such resources is limited, as in the widely studied Resource Constrained
Project Scheduling Problem (RCPSP). In many cases however, the resource
capacity can be exceeded if needed, yet at a significant cost, by hiring
additional workforce for instance. The field of scheduling known as resource
leveling aims at modelling such costs: while resource capacities are not a
hard constraint, the objective function is chosen to penalize resource
overspending or other irregularities in resource use.

#### Related works

Resource leveling is a well studied topic in recent literature, as a variant
of the RCPSP – see Hartmann and Briskorn [2022] for a survey. Among the
various leveling objective functions that are proposed, a very natural one is
the total overload cost, used in Rieck et al. [2012], Rieck and Zimmermann
[2015], Bianco et al. [2016], Atan and Eren [2018], Verbeeck et al. [2017].
The total overload cost, that is the resource use exceeding a given level, is
suitable for modelling the cost of mobilizing supplementary resource capacity,
the level representing a base capacity that should ideally not be exceeded.
Considering a single resource of level $L$ and denoting $r_{\tau}$ the
resource request at time step $\tau$, the function writes
$\sum_{\tau}\max(0,r_{\tau}-L)$ (see the hatched part in Figure 1). Other
notable examples of leveling objective functions introduced in the literature
are weighted square capacities [Christodoulou et al., 2015, Ponz-Tienda et
al., 2017b, a, Rieck et al., 2012, Rieck and Zimmermann, 2015, Qiao and Li,
2018, Li et al., 2018, Li and Dong, 2018], squared changes in resource request
[Qiao and Li, 2018, Ponz-Tienda et al., 2017b], absolute changes in resource
request [Bianco et al., 2017, Ponz-Tienda et al., 2017b, Rieck and Zimmermann,
2015], resource availability cost [Ponz-Tienda et al., 2017b, Rodrigues and
Yamashita, 2015, Van Peteghem and Vanhoucke, 2013, Zhu et al., 2017] and
squared deviation from a threshold [Qiao and Li, 2018].

Figure 1: Illustration of function $F$ for an instance with five jobs and
resource level $L=2$.

In terms of solving methods, the literature mainly provides heuristics
[Woodworth and Willie, 1975, Christodoulou et al., 2015, Zhu et al., 2017,
Atan and Eren, 2018, Drótos and Kis, 2011], metaheuristics [Ponz-Tienda et
al., 2017b, Qiao and Li, 2018, Li et al., 2018, Van Peteghem and Vanhoucke,
2013, Verbeeck et al., 2017] and exact methods [Easa, 1989, Demeulemeester,
1995, Ponz-Tienda et al., 2017a, Rieck et al., 2012, Rieck and Zimmermann,
2015, Bianco et al., 2017, Rodrigues and Yamashita, 2015, Bianco et al., 2016,
Atan and Eren, 2018, Drótos and Kis, 2011], but lacks theoretical results on
the computational complexity of these problems. This work aims at providing
such complexity results.

#### Contributions

In Neumann and Zimmermann [1999], resource leveling problems under generalized
precedence constraints and with various objectives, including total overload
cost, are shown to be strongly $NP$-hard using reductions from $NP$-hard
machine scheduling problems of the literature. The present work provides
$NP$-hardness proofs based on the same idea, yet it tackles a large panel of
more specific problems, including fixed-parameter special cases, in order to
refine the boundary between $NP$-hardness and polynomial-time tractability. To
some extent, resource leveling with total overload cost minimization shares
similarities with late work minimization [Sterna, 2011] in that portions of
jobs exceeding a limit (in resource use or in time respectively) are
penalized. In that respect, a special case of resource leveling problem is
proven equivalent to a two-machine late work minimization problem (see Section
4.5). The latter late work minimization problem is studied in Chen et al.
[2016] where it is shown to be $NP$-hard and solvable in pseudo-polynomial
time. Further approximation results on the early work maximization version of
the same problem include a PTAS [Sterna and Czerniachowska, 2017] and an FPTAS
[Chen et al., 2020]. A similar equivalence between a resource leveling problem
and a late work minimization problem is shown in Györgyi and Kis [2020] by
exchanging the roles of time and resource use (each time step becoming a
machine and conversely). A common approximation framework for both problems is
proposed as well as an $NP$-hardness result that is included as such in this
work to complement the range of investigated problems (see Section 6).

The core result in this work is a polynomial-time algorithm to minimize the
total overload cost with resource level $L=2$ in the case of unit processing
times and precedence constraints. This problem can be seen as the leveling
counterpart of the well-known machine scheduling problem denoted
$P2|prec,p_{i}=1|C_{max}$ in the standard three-field Graham notation [Graham
et al., 1979]. The algorithm relies on polynomial methods to solve
$P2|prec,p_{i}=1|C_{max}$ proposed in Fujii et al. [1969] and Coffman and
Graham [1971/1972]. Other resource leveling problems with various classical
scheduling constraints are investigated: bounded makespan, precedence
constraints (arbitrary or restricted to in-tree precedence graphs), release
and due dates (with or without preemption). Polynomial algorithms are provided
for some cases, notably using flow reformulations or inspired from machine
scheduling algorithms.

#### Outline

This paper is organized as follows. Section 2 gives a general description of
resource leveling problems and defines notations. Section 3 describes the
polynomial-time algorithm for the main problem studied in this work:
optimizing the total overload cost with level $L=2$, unit processing times and
precedence constraints. Section 4 provides complementary tractable cases among
resource leveling problems with classical scheduling constraints. Section 5
gives $NP$-hardness results. Section 6 summarizes the complexity results
obtained in this work. Section 7 gives elements of conclusion and
perspectives. The main notations used in this work are listed in Table 2 at
the end of the article.

##  2 Problem description and notations

Even though this work deals with one main problem with specific constraints
and parameters, this section gives a rather general description of resource
leveling problems as well as convenient notations to designate them. This will
prove to be useful in differentiating the various other problems for which
complexity results are also provided.

The scheduling problems considered in this work involve a single resource and
a set of jobs $J$ with processing times $p\in\mathbb{N}^{J}$ and resource
consumptions $c\in\mathbb{N}^{J}$. A schedule is a vector of job starting
times $x\in\mathbb{R}_{+}^{J}$. The starting time of job $i\in J$ in schedule
$x$ is denoted $x_{i}$. Note that since parameters are integer, solutions with
integer dates are dominant for the considered objective function in the non-
preemptive case [Neumann and Zimmermann, 1999]. In the sequel, only schedules
with integer values will therefore be considered (with the exception of
Section 4.4). For an integer date $\tau\in\mathbb{N}$, _time step_ $\tau$ will
designate the time interval of size one starting at $\tau$, namely
$[\tau,\tau+1)$.
For the sake of readability, the usual three-field Graham notation
$\alpha|\beta|\gamma$ introduced in Graham et al. [1979] for scheduling
problems will now be extended with resource leveling parameters.

The $\alpha$ field is used to describe the machine environment of a scheduling
problem. In the context of resource leveling, the machine environment
parameter is replaced with a resource level $L\in\mathbb{N}$. In the sequel,
the resource leveling problems with resource level $L$ are denoted $L|.|.$.
Following the case of machine scheduling, notations such as $L1|.|.$ and
$L2|.|.$ will be used when $L$ is fixed.

The $\beta$ field contains information about constraints and instance
specificities. Since resource consumptions $c\in\mathbb{N}^{J}$ are introduced
for resource leveling instances, the $\beta$ field should allow for
restrictions on those values. For example, $c_{i}=1$ will denote the case of
unit $c_{i}$ values. In this work, the constraints of the $\beta$ field
typically include a deadline on the makespan, denoted $C_{max}\leq M$.

The $\gamma$ field describes the objective function. In this work, the amount
of resource that fits under resource level $L$ (see the grey area in Figure 1)
is used as objective function, denoted $F$, instead of the total overload cost
itself. The two quantities being complementary, the complexity is equivalent
and the minimization of the total overload is turned into a maximization
problem. This eases the interpretation of the criterion in terms of the
structures used for solution methods (e.g., size of a matching or value of a
flow). Given an integer schedule $x$, denoting $r_{\tau}(x)$ the amount of
resource required at time step $\tau$ in $x$ and $C_{max}(x)$ the makespan of
$x$, function $F$ writes:

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

Note that $F$ generalizes to non-integer schedules as follows:

$F(x)=\int_{\tau=0}^{C_{max}(x)}\min(L,r(\tau,x))d\tau$

where $r(\tau,x)$ is the resource use at time $\tau$ in $x$.

##  3 A polynomial algorithm for $L2|prec,C_{max}\leq M,c_{i}=1,p_{i}=1|F$

This section is dedicated to the core result of this work: solving Problem
$L2|prec,C_{max}\leq M,c_{i}=1,p_{i}=1|F$ in polynomial time. Given a set of
jobs $J$ with unit processing times and unit resource consumption and a
precedence graph $G=(J,\mathcal{A})$ with set of arcs $\mathcal{A}$, the
problem is to find a feasible schedule $x$ with makespan at most $M$ such that
$F(x)$ is maximized for a resource level $L=2$. Figure 2 shows an example of
precedence graph with optimal schedules for $M=5$, $M=6$ and $M=7$.

(a) Precedence graph $G$

(b) Optimal schedule for $M=5$

(c) Optimal schedule for $M=6$

(d) Optimal schedule for $M=7$

Figure 2: Example of precedence graph and optimal schedule for
$L2|prec,C_{max}\leq M,c_{i}=1,p_{i}=1|F$

For convenience, it will be assumed w.l.o.g. that there are no idling time
steps, i.e., time steps where no job is processed, before the makespan of
considered schedules. With the above assumption, a schedule can be seen as a
sequence of columns, a column being a set of jobs scheduled at the same time
step. Note that if two jobs $i$ and $j$ belong to the same column, there can
be no path from $i$ to $j$ or from $j$ to $i$ in the precedence graph, in
other words, $i$ and $j$ must be independent.

Problem $L2|prec,C_{max}\leq M,c_{i}=1,p_{i}=1|F$ is closely related to its
classical counterpart in makespan minimization: $P2|prec,p_{i}=1|C_{max}$.
Among different approaches of the literature to solve
$P2|prec,p_{i}=1|C_{max}$ in polynomial time, a method relying on maximum
matchings between independent jobs is proposed in Fujii et al. [1969]. Since
independence between jobs is required for them to be scheduled at the same
time step, matching structures naturally appear in a two-machine environment.
The results of this section will show that this is still true in the context
of resource leveling. Another approach is proposed in Coffman and Graham
[1971/1972] with a better time complexity. The idea of this second method is
to build a priority list of the jobs based on the precedence graph and then
apply the corresponding list-scheduling algorithm. The optimality is proved
using a block decomposition of the resulting schedule. In broad outline, the
convenient matching structure of the method from Fujii et al. [1969] is used
to prove the existence of schedules that satisfy certain objective values
while the more efficient method from Coffman and Graham [1971/1972] is used to
actually build those schedules.

Two graphs will be considered as support for matchings, both of them being
deduced from the precedence graph $G$, as illustrated in Figure 3. First, let
$\widetilde{G}=(J,E)$ be the _independence graph_ where $E=\\{\\{i,j\\}\in
J^{2}\mid i\text{ independent from }j\\}$ – see Figure 3(a). A critical path
in a longest path in the precedence graph. It is a well known result that the
sum of processing times along a critical path is the minimum feasible makespan
with respect to precedence constraints. Let then $P$ be a critical path in
$G$. Consider the bipartite graph $\widetilde{G}_{P}=(P\cup(J\setminus
P),E_{P})$ where $E_{P}=\\{\\{i,j\\}\in E|i\in P,j\in J\setminus P\\}$, as
shown in Figure 3(b) where the jobs of $P$ are in gray. Note that in Figure 3,
independence relations are represented with dashed lines as opposed to solid
lines for precedence relations.

(a) Independence graph $\widetilde{G}$

(b) Bipartite independence graph $\widetilde{G}_{P}$

Figure 3: Examples of graphs for $L2|prec,C_{max}\leq M,c_{i}=1,p_{i}=1|F$

Let $m^{*}_{P}$ and $m^{*}$ denote the sizes of a maximum matching in
$\widetilde{G}_{P}$ and $\widetilde{G}$ respectively. The inequality
$m^{*}_{P}\leq m^{*}$ is always verified since $E_{P}$ is a subset of $E$. In
the example of Figure 3, $m^{*}_{P}=4$ and $m^{*}=5$.
The aim is to show that the optimal value of objective function $F$ can be
computed for any $M$ using only $m^{*}_{P}$, $m^{*}$, $|J|$ and $|P|$ – and
that an associated optimal schedule can be computed in polynomial time. More
precisely, it will be shown that the optimal objective value as a function of
$M$, denoted $F^{*}$, is piecewise linear with three distinct segments as
shown in Figure 4. Note that if $M<|P|$ there is no feasible schedule.

Figure 4: Optimal objective value as a function of $M$

The constant part of the function on the right coincides with the result of
Fujii et al. [1969] stating that the minimum makespan to schedule the project
on two machines is $|J|-m^{*}$. For $M\geq|J|-m^{*}$, $F^{*}$ equals its upper
bound $|J|$ – all jobs fit under resource level $L=2$. The contribution of
this work is therefore to provide the values of $F^{*}(M)$ for $|P|\leq
M\leq|J|-m^{*}$.

Note that the schedule of Figures 2(b) corresponds to an optimal solution for
$M=|P|=5$. Its value is $9$, which is indeed equal to $|P|+m^{*}_{P}=5+4$. If
the deadline is increased by one, i.e., $M=6$, then two more jobs can be added
under the resource level two, i.e., the optimal value is $11$, as shown in
Figure 2(c). It corresponds to the first breaking point in Figure 4, as
$M=6=|P|+m^{*}-m^{*}_{P}$ and $11=|P|+2m^{*}-m^{*}_{P}$. As it can be seen in
Figure 2(d), when $M=7$, all jobs can be scheduled under the resource level.
It corresponds to the second breaking point in Figure 4, as $M=7=|J|-m^{*}$.

The proposed approach is in two steps:

  1. 1.

Find an optimal solution for $M=|P|$;

  2. 2.

Find recursively an optimal solution for $M+1$ from an optimal solution for
$M$.

The following definition introduces the _augmenting sequence of a schedule_ in
the independence graphs $\widetilde{G}$ and in the bipartite independence
graph $\widetilde{G}_{P}$.

######  Definition 1 (augmenting sequence).

A sequence $(i_{0},j_{1},i_{1},j_{2},i_{2},\dots,j_{r},i_{r},j_{r+1})$ of
distinct jobs is an _augmenting sequence_ for $(\widetilde{G},x)$ (resp. for
$(\widetilde{G}_{P},x)$) if:

  * -

$(i_{0},j_{1},i_{1},j_{2},i_{2},\dots,j_{r},i_{r},j_{r+1})$ is a path in
$\widetilde{G}$ (resp. in $\widetilde{G}_{P}$);

  * -

the number of jobs scheduled at $x_{i_{0}}$ is not two;

  * -

the number of jobs scheduled at $x_{j_{r+1}}$ is not two;

  * -

for every $q\in\\{1,\dots,r\\}$, $x_{i_{q}}=x_{j_{q}}$.

The name augmenting sequence deliberately recalls the augmenting path used in
the context of matching problems. It will be seen in the sequel that both
notions actually coincide to some extent since an augmenting sequence defines
an augmenting path for a certain matching of jobs.

An example of augmenting sequence is illustrated in Figure 5. The jobs of the
sequence are surrounded by circles and connected with dashed arrows.

Figure 5: Example of augmenting sequence

###  3.1 Solution for $M=|P|$

The first step is to solve the problem for the minimum relevant value for $M$,
that is to say when $M$ equals the length of a critical path in the precedence
graph.
The following definition describes an elementary operation, illustrated in
Figure 6, that will be used in the sequel to improve the value of objective
function $F$ incrementally.

######  Definition 2 (elementary operation).

Let $x$ be a feasible schedule for instance $I=(G,M)$ with $M=|P|$, where $P$
is a critical path of $G$. Let $a,b\in J$ be two independent jobs such that
$x_{a}<x_{b}$ and such that $a$ is the only job scheduled at $x_{a}$.
Decomposition: Let us denote $\tau_{1}<\tau_{2}<\dots<\tau_{K}$ the time steps
in $\\{x_{a}+1,\dots,x_{b}-1\\}$ where at least one predecessor of $b$ is
scheduled, as well as $\tau_{0}=x_{a}$ and $\tau_{K+1}=x_{b}$ for convenience.
For each $k\in\\{1,\dots,K\\}$, the jobs scheduled at $\tau_{k}$ are
partitioned into $\alpha_{k}$ and $\beta_{k}$, where $\beta_{k}$ are the
predecessors of $b$ and $\alpha_{k}$ are the remaining jobs. Let us also
denote, for each $k\in\\{1,\dots,K+1\\}$, $A_{k}=\\{i\in
J\mid\tau_{k-1}<x_{i}<\tau_{k}\\}$, the sets of jobs scheduled in between the
$\tau_{k}$.
Translation: The jobs of $\beta_{k}$ are translated from $\tau_{k}$ to
$\tau_{k-1}$ for each $k\in\\{1,\dots,K\\}$ and job $b$ from $\tau_{K+1}$ to
$\tau_{K}$.

(a) Decomposition

(b) Translation

Figure 6: Elementary operation

The decomposition and translation steps of Definition 2 are illustrated in
Figure 6(a) and Figure 6(b) respectively.

The elementary operation of Definition 2 will now be shown to yield a feasible
schedule and its impact on objective function $F$ will be quantified.

######  Proposition 1.

Let $x$ be a feasible schedule for instance $I=(G,M)$ with $M=|P|$, where $P$
is a critical path of $G$. Let $a,b\in J$ be two independent jobs such that
$x_{a}<x_{b}$ and such that $a$ is the only job scheduled at $x_{a}$.
The schedule $x^{\prime}$ resulting from the elementary operation on $a$ and
$b$ is feasible and it verifies:

$F(x^{\prime})=\begin{cases}F(x)&\text{if exactly two jobs are}\\\
&\text{scheduled at }x_{b}\text{ in }x\\\ F(x)+1&\text{otherwise}\end{cases}$

###### Proof.

Let us first show that schedule $x^{\prime}$ is feasible. It is clear that the
elementary operation does not increase the makespan of the schedule, thus
respecting the makespan bound $M=|P|$. By construction, all predecessors of
job $b$ scheduled between $x_{a}$ and $x_{b}$ are in
$\bigcup_{k=1}^{K}\beta_{k}$. As a consequence, there is no precedence arc
going from a job of
$\\{a\\}\cup\bigcup_{k=1}^{K}\alpha_{k}\cup\bigcup_{k=1}^{K+1}A_{k}$ to a job
of $\\{b\\}\cup\bigcup_{k=1}^{K}\beta_{k}$. The translation of the elementary
operation does no violate any precedence constraint.
Let us now quantify the impact of the elementary operation on the objective
function. Since the makespan bound is $M=|P|$, there is exactly one job of
critical path $P$ at each time step in $\\{0,1,\dots,M-1\\}$. In particular,
since $a$ is the only job scheduled at $x_{a}$, it necessarily belongs to $P$.
Furthermore, for every $k\in\\{1,\dots,K\\}$, a job of $P$ is scheduled at
$\tau_{k}$. This job of $P$ is a successor of $a$ and therefore cannot be in
$\beta_{k}$, otherwise $a$ and $b$ would not be independent, by transitivity.
The job of $P$ must then be in $\alpha_{k}$, so $|\alpha_{k}|\geq 1$. Also,
$|\beta_{k}|\geq 1$ for every $k\in\\{1,\dots,K\\}$ by construction. As a
consequence:

  * -

For every $k\in\\{1,\dots,K\\}$, at least two jobs are scheduled at $\tau_{k}$
in $x^{\prime}$, which was already the case in $x$

  * -

At least two jobs are scheduled at $x_{a}$ in $x^{\prime}$ while there was
only one in $x$

  * -

One less job is scheduled at $x_{b}$ in $x^{\prime}$

  * -

Other time steps remain unchanged

Job $b$ cannot be the only job scheduled at $x_{b}$, otherwise $b$ would
belong to critical path $P$ and would not be independent from job $a$. The
difference between $F(x)$ and $F(x^{\prime})$ comes down to whether there are
two or more jobs scheduled at $x_{b}$ in $x$:

  * -

If exactly two jobs are scheduled at $x_{b}$ in $x$, then the contribution to
the objective function is increased by one in $x_{a}$ but decreased by one in
$x_{b}$, so $F(x^{\prime})=F(x)$

  * -

If at least three jobs are scheduled at $x_{b}$ in $x$, then the contribution
to the objective function is increased by one in $x_{a}$ and remains unchanged
in $x_{b}$, so $F(x^{\prime})=F(x)+1$

∎

######  Remark 1.

Definition 2 and Proposition 1 assume that jobs $a$ and $b$ in the elementary
operation are such that $x_{a}<x_{b}$. The case where $x_{b}<x_{a}$ can
actually be handled exactly the same way, up to an inversion of precedence
relations.

The possibility to improve the objective value of a schedule with makespan
$|P|$ using elementary operations will now be linked to the existence of a
particular augmenting sequence.

######  Lemma 1.

Let $x$ be a feasible schedule for instance $I=(G,M)$ with $M=|P|$, where $P$
is a critical path of $G$. If there exists an augmenting sequence
$\rho=(i_{0},j_{1},i_{1},j_{2},i_{2},\dots,j_{r},i_{r},j_{r+1})$ for
$(\widetilde{G}_{P},x)$ such that:

  * -

$i_{0}$ is the only job scheduled at $x_{i_{0}}$;

  * -

at least three jobs are scheduled at $x_{j_{r+1}}$;

then there exists a schedule $x^{\prime}$ with makespan $|P|$ such that
$F(x^{\prime})=F(x)+1$.
Furthermore, such a schedule can be computed from $x$ in polynomial time.

###### Proof.

The result will be proven using an induction on $r$.

(initialization) For $r=0$, the augmenting sequence reduces to two jobs
$i_{0}$ and $j_{1}$ that are independent and scheduled at different dates. The
elementary operation can be applied with $i_{0}$ as $a$ and $j_{1}$ as $b$.
Since there are at least three jobs scheduled at $x_{j_{1}}$, the resulting
schedule $x^{\prime}$ is such that $F(x^{\prime})=F(x)+1$ according to
Proposition 1.

(induction) Suppose that the property is verified up to the value $r-1$ for
some $r\geq 1$. If for some $q\in\\{1,\dots,r\\}$ there are at least three
jobs scheduled at $x_{i_{q}}$, then the sequence
$(i_{0},j_{1},i_{1},j_{2},i_{2},\dots,j_{q-1},i_{q-1},j_{q})$ is an augmenting
sequence with the required properties on which the induction hypothesis can be
applied.
One can now suppose that for every $q\in\\{1,\dots,r\\}$, the only jobs
scheduled at $x_{i_{q}}$ are $i_{q}$ and $j_{q}$. The idea is now to use the
elementary operation of Definition 2 to reduce the size of the augmenting
sequence. Assume that the elementary operation is applied using $i_{0}$ as $a$
and $j_{1}$ as $b$ and let $x^{\prime\prime}$ be the resulting schedule. If
$(i_{1},j_{2},i_{2},j_{3},i_{3},\dots,j_{r},i_{r},j_{r+1})$ is an augmenting
sequence for $(\widetilde{G}_{P},x^{\prime\prime})$, then the induction can be
applied.
If not, there exists $q\geq 2$ such that $\\{i_{q},j_{q}\\}$ coincide with
$\alpha_{k}\cup\beta_{k}$ in the decomposition of Definition 2, implying that
$x^{\prime\prime}_{i_{q}}\neq x^{\prime\prime}_{j_{q}}$. In that case,
schedule $x^{\prime\prime}$ would be irrelevant for the induction. Such a
crossing configuration is illustrated in Figure 7(a). Moreover, let us show
that $\alpha_{k}=\\{i_{q}\\}$ and $\beta_{k}=\\{j_{q}\\}$. Since the
augmenting sequence $\rho$ is a path in the bipartite graph
$\widetilde{G}_{P}$, it alternates between jobs of the critical path $P$ and
jobs of $J\setminus P$. In a schedule of makespan $|P|$, exactly one job
belongs to $P$ at each time step, so $i_{0}$ that is the only job scheduled at
$x_{i_{0}}$ belongs to $P$ and so do $i_{1},i_{2},\dots,i_{r}$. By
construction, in the decomposition of Definition 2, only block $\alpha_{k}$
can contain successors of $i_{0}=a$. Therefore, $i_{q}$ that is a successor of
$i_{0}$ since it is in the critical path must be in $\alpha_{k}$. The only
other job scheduled at $x_{i_{q}}$ is $j_{q}$ and it must belong to
$\beta_{k}$ that cannot be empty.
Having $\beta_{k}=\\{j_{q}\\}$ guarantees that $j_{q}$ is independent from
$a=i_{0}$, so $\\{i_{0},j_{q}\\}$ is an edge in $\widetilde{G}_{P}$. A
shortcut can then be operated from $i_{0}$ to $j_{q}$, as illustrated in
Figure 7(b), yielding sequence
$(i_{0},j_{q},i_{q},j_{q+1},i_{q+1},\dots,j_{r},i_{r},j_{r+1})$ that is an
augmenting sequence on which the induction hypothesis applies.

(a) Crossing configuration with $\\{i_{q}\\}=\alpha_{k}$ and
$\\{j_{q}\\}=\beta_{k}$

(b) Shortcut

Figure 7: Solving a crossing configuration in the augmenting sequence

∎

######  Proposition 2.

Any optimal solution $x^{*}$ of the instance $I=(G,M)$ with $M=|P|$ verifies
$F(x^{*})=|P|+m^{*}_{P}$. Furthermore, such an optimal schedule can be
computed in polynomial time.

###### Proof.

Let us first show that the objective function value for a feasible schedule is
at most $|P|+m^{*}_{P}$. Let $x$ be a feasible schedule with makespan $|P|$.
Let $m$ be the number of time steps in $\\{0,\dots,|P|-1\\}$ with at least two
jobs scheduled in $x$. It is clear that $F(x)=|P|+m$. By definition of a
critical path, exactly one job of $P$ is scheduled at every time step of
$\\{0,\dots,|P|-1\\}$. Given that two jobs scheduled at the same time step are
necessarily independent, matching each job of the critical path with a job
that is scheduled at the same date, when there is one, yields a matching in
$\widetilde{G}_{P}$. In other words, a matching of size $m$ in
$\widetilde{G}_{P}$ can be deduced from $x$, so $m\leq m^{*}_{P}$ and
$F(x)\leq|P|+m^{*}_{P}$.
It will now be shown that there exists a feasible schedule $x$ such that
$F(x)=|P|+m^{*}_{P}$. Suppose that a given schedule $x$ is such that there are
$m$ time steps in $\\{0,\dots,|P|-1\\}$ where at least two jobs are scheduled,
with $m<m^{*}_{P}$. Again, $F(x)=|P|+m$ and it is possible to deduce from $x$
a matching $\mu$ of size $m$ in $\widetilde{G}_{P}$. This matching being not
of maximum size, Berge’s theorem [Berge, 1957] states that there exists an
augmenting path. Let
$(i_{0},j_{1},i_{1},j_{2},i_{2},\dots,j_{r},i_{r},j_{r+1})$ denote the
sequence of jobs in the augmenting path, with $i_{0}\in P$, $j_{r+1}\in
J\setminus P$ and both being not matched in $\mu$. The following properties
hold:

  * -

$i_{0}$ is a job of $P$ that is not matched in $\mu$, so it is the only one
scheduled at $x_{i_{0}}$.

  * -

$j_{r+1}$ is a job of $J\setminus P$ that is not matched in $\mu$. Since there
is a job of $P$ at each time step, $j_{r+1}$ is scheduled at $x_{j_{r+1}}$
together with a job of $P$. This job of $P$ could be matched with $j_{r+1}$ in
$\mu$ but it is not so, by construction of $\mu$, it must be matched with a
third job. Thus, three jobs are scheduled at $x_{j_{r+1}}$.

  * -

$i_{q}$ and $j_{q}$ are matched together in $\mu$ so $x_{i_{q}}=x_{j_{q}}$ for
every $q\in\\{1,\dots,r\\}$.

Those properties imply that
$(i_{0},j_{1},i_{1},j_{2},i_{2},\dots,j_{r},i_{r},j_{r+1})$ is an augmenting
sequence satisfying the requirements of Lemma 1. Applying Lemma 1 gives that
there exists a schedule $x^{\prime}$ with $F(x^{\prime})=F(x)+1$. As a
conclusion, any feasible schedule of $I=(G,|P|)$ can be modified incrementally
to reach an objective function value of $|P|+m^{*}_{P}$. ∎

###  3.2 Solution for $M>|P|$

The problem will now be solved for other values of $M$ based on the solution
for $M=|P|$. The idea is to apply transformations that increment the makespan
of the initial schedule while keeping its optimality. First, it will be shown
that optimal solutions always reach makespan deadline $M$ when $M$ is in a
certain interval.

######  Lemma 2.

For any makespan deadline $M\in\\{|P|,\dots,|J|-m^{*}\\}$ any optimal schedule
for $I=(G,M)$ has makespan exactly $M$.

###### Proof.

Let $M\in\\{|P|,\dots,|J|-m^{*}\\}$ and suppose that there exists an optimal
schedule $x$ for $I$ of makespan $C_{max}(x)<M$. According to the result of
Fujii et al. [1969], the minimum makespan to schedule the project on two
machines is $|J|-m^{*}$. This implies that there exists a time step $\tau$
where at least three jobs are scheduled in $x$.
Consider the transformation illustrated in Figure 8. One of the jobs scheduled
at $\tau$ can be scheduled at $\tau+1$ instead and the subsequent jobs can be
scheduled one time step later.
The resulting schedule $x^{\prime}$ has makespan
$C_{max}(x^{\prime})=C_{max}(x)+1\leq M$ and objective value
$F(x^{\prime})=F(x)+1$. This contradicts the optimality of $x$ since
$x^{\prime}$ is feasible for $I$ with a strictly higher objective value. ∎

Figure 8: Example of one-job elongation

######  Lemma 3.

Let $M\in\\{|P|,\dots,|J|-m^{*}-1\\}$ and let $x$ be an optimal schedule for
$I=(G,M)$. Suppose that $x$ is such that, at each time step
$\tau\in\\{0,\dots,M-1\\}$, either $1$, $2$ or $3$ jobs are scheduled. If
there exists an augmenting sequence
$\rho=(i_{0},j_{1},i_{1},j_{2},i_{2},\dots,j_{r},i_{r},j_{r+1})$ for
$(\widetilde{G},x)$ satisfying $x_{i_{0}}\neq x_{j_{r+1}}$, then there exists
a schedule $x^{\prime}$ with makespan $M+1$ such that $F(x^{\prime})=F(x)+2$.
Furthermore, such a schedule can be computed from $x$ in polynomial time.

###### Proof.

Some useful properties of the augmenting sequence are first derived from basic
transformations.
An augmenting sequence can indeed be obtained in which $i_{q}$ and $j_{q}$ are
the only jobs scheduled at $x_{i_{q}}$ for every $q\in\\{1,\dots,r\\}$.
Suppose that three jobs are scheduled at $x_{i_{q}}$ for some
$q\in\\{1,\dots,r\\}$, two cases are possible:

  * -

if $i_{0}$ is scheduled at $x_{i_{q}}$, then the sequence
$(i_{q},j_{q+1},i_{q+1},j_{q+2},i_{q+2},\dots,j_{r},i_{r},j_{r+1})$ is an
augmenting sequence and satisfies $x_{i_{q}}\neq x_{j_{r+1}}$;

  * -

otherwise the sequence
$(i_{0},j_{1},i_{1},j_{2},i_{2},\dots,j_{q-1},i_{q-1},j_{q})$ is an augmenting
sequence satisfying $x_{i_{0}}\neq x_{j_{q}}$.

In both cases, an augmenting sequence with the required properties can be
obtained by truncating the initial one. Such truncations can be operated on
the augmenting sequence until all intermediary time steps have exactly two
jobs scheduled.

It can also be ensured that no arc of the augmenting sequence jumps over a
time step different from $x_{i_{0}}$ and $x_{j_{r+1}}$ with exactly three jobs
scheduled. Indeed, suppose that an arc $(a,b)$ of the augmenting sequence is
such that there exists a job $c$ with exactly three jobs scheduled at $x_{c}$
and w.l.o.g. $x_{a}<x_{c}<x_{b}$, as shown in Figure 9. Since $a$ and $b$ are
independent, $c$ is either independent from $a$ or from $b$ – or both. If $c$
is independent from $a$, then the augmenting sequence can be truncated after
$a$ and ended with arc $(a,c)$. If $c$ is independent from $b$, then the
augmenting sequence can be truncated before $b$ and started with arc $(c,b)$.

Figure 9: Shortcut preventing a jump

One can now suppose that the augmenting sequence $\rho$ is such that:

  * -

$i_{q}$ and $j_{q}$ are the only jobs scheduled at $x_{i_{q}}$ for every
$q\in\\{1,\dots,r\\}$;

  * -

for every arc $(i_{q},j_{q+1})$ and every time step
$\tau\in\\{x_{i_{q}},\dots,x_{j_{q+1}}\\}\setminus\\{x_{i_{0}},x_{j_{r+1}}\\}$,
at most two jobs are scheduled at $\tau$.

Let $\tau_{min}=\min_{i\in\rho}x_{i}$ and $\tau_{max}=\max_{i\in\rho}x_{i}$.
For every time step
$\tau\in\\{\tau_{min},\dots,\tau_{max}\\}\setminus\\{x_{i_{0}},x_{j_{r+1}}\\}$,
either $1$ or $2$ jobs are scheduled at $\tau$. Consider the subset of jobs
$J^{\prime}=\\{i\in J\mid\tau_{min}\leq
x_{i}\leq\tau_{max}\\}\setminus\\{i_{0},j_{r+1}\\}$.
Let $\mu$ denote the matching on $J^{\prime}$ obtained by pairing the jobs
scheduled at the same time step. It is clear that
$\mu\cup\\{\\{i_{q},j_{q+1}\\}\mid
q\in\\{0,\dots,r\\}\\}\setminus\\{\\{j_{q},i_{q}\\}\mid
q\in\\{1,\dots,r\\}\\}$ is a matching between independent jobs of
$J^{\prime}\cup\\{i_{0},j_{r+1}\\}$ of size $|\mu|+1$. Using the result of
Fujii et al. [1969], it is possible to schedule the jobs of
$J^{\prime}\cup\\{i_{0},j_{r+1}\\}$ on two machines using at most
$|J^{\prime}|+2-(|\mu|+1)=|J^{\prime}|-|\mu|+1$ time steps. Three cases can be
distinguished, only one of which is actually possible:

  1. 1.

If $i_{0}$ and $j_{r+1}$ are both the only jobs scheduled on their time steps
in $x$, the jobs of $J^{\prime}\cup\\{i_{0},j_{r+1}\\}$ are scheduled on
$|J^{\prime}|-|\mu|+2$ time steps in $x$. This contradicts the optimality of
$x$, since, using Fujii et al. [1969], there exists a schedule of makespan
$M-1$ with the same objective value as $x$, which is impossible according to
Lemma 2.

  2. 2.

If either $i_{0}$ or $j_{r+1}$ is scheduled alone on its time step – the other
being on a time step with exactly three jobs, the jobs of
$J^{\prime}\cup\\{i_{0},j_{r+1}\\}$ are scheduled on $|J^{\prime}|-|\mu|+1$
time steps in $x$. This contradicts the optimality of $x$ since, using Fujii
et al. [1969], all jobs of $J^{\prime}\cup\\{i_{0},j_{r+1}\\}$ can be
scheduled on the same number of time steps without exceeding the resource
level.

  3. 3.

If both $i_{0}$ and $j_{r+1}$ are scheduled on time steps with exactly three
jobs, the jobs of $J^{\prime}\cup\\{i_{0},j_{r+1}\\}$ are scheduled on
$|J^{\prime}|-|\mu|$ time steps in $x$. Using Fujii et al. [1969], these jobs
can be scheduled on $|J^{\prime}|-|\mu|+1$ time steps without exceeding the
resource level, so the objective function can be increased by $2$. This is the
expected result.

∎

######  Lemma 4.

For any $M\in\mathbb{N}$, $M\geq|P|$, the optimal objective function verifies:

$F^{*}(M)\leq 2(M-|P|)+|P|+m^{*}_{P}$

###### Proof.

Using Proposition 2 and by definition of $m^{*}_{P}$, in any feasible
schedule, at most $m^{*}_{P}$ jobs of $P$ are scheduled on the same time step
as a job of $J\setminus P$. Equivalently, at least $|P|-m^{*}_{P}$ jobs of $P$
are alone on their time step in any feasible schedule.
This implies that $F^{*}(M)\leq 2M-(|P|-m^{*}_{P})$ for any $M\in\mathbb{N}$,
$M\geq|P|$, which can be rewritten as $F^{*}(M)\leq 2(M-|P|)+|P|+m^{*}_{P}$. ∎

######  Lemma 5.

For any $M\in\mathbb{N}$, $M\geq|P|$, the optimal objective function verifies:

$F^{*}(M)\leq M+m^{*}$

###### Proof.

Let $M\in\mathbb{N}$, $M\geq|P|$, and suppose that there exists a feasible
schedule $x$ for $I=(G,M)$ such that $F(x)=M+m$. At least $m$ time steps have
two or more jobs scheduled in $x$. A matching between independent jobs of size
at least $m$ can then be deduced from $x$. By definition of $m^{*}$ as the
maximum size for a matching between independent jobs, $m\leq m^{*}$ and
$F(x)\leq m^{*}+M$. Inequality $F(x)\leq m^{*}+M$ is then verified for any
feasible schedule so $F^{*}(M)\leq M+m^{*}$. ∎

The following theorem allows for the computation of $F^{*}$ as a function of
$M$ as illustrated in Figure 4.

######  Theorem 1.

The optimal objective function value $F^{*}$ as a function of makespan
deadline $M$ is piecewise linear and defined as follows:

  * -

For $M\in\\{|P|,\dots,|P|+m^{*}-m^{*}_{P}\\}$:
$F^{*}(M)=2(M-|P|)+|P|+m^{*}_{P}$;

  * -

For $M\in\\{|P|+m^{*}-m^{*}_{P},\dots,|J|-m^{*}\\}$: $F^{*}(M)=M+m^{*}$;

  * -

For $M\in\mathbb{N}$, $M\geq|J|-m^{*}$: $F^{*}(M)=|J|$.

Furthermore, an optimal schedule can be computed for any $M\geq|P|$ in
polynomial time.

###### Proof.

Let us prove by induction on $M$ that there exists a schedule $x^{M}$ of
makespan $M$ such that $F(x^{M})=2(M-|P|)+|P|+m^{*}_{P}$ for every
$M\in\\{|P|,\dots,|P|+m^{*}-m^{*}_{P}\\}$.
The case of $M=|P|$ was solved in Section 3.1.
Suppose that the property holds for some
$M\in\\{|P|,\dots,|P|+m^{*}-m^{*}_{P}-1\\}$ and let $x^{M}$ be the associated
schedule. If there exists a time step with at least $4$ jobs scheduled in
$x^{M}$, two of those jobs can be scheduled on the next time step while all
jobs scheduled after are postponed by one time unit, as illustrated in Figure
10. This yields an optimal schedule $x^{M+1}$.

Figure 10: Example of two-job elongation

If not, $x^{M}$ satisfies the requirement of Lemma 3 since either $1$, $2$ or
$3$ jobs are scheduled at each time step $\tau\in\\{0,\dots,M-1\\}$. Let $\mu$
denote a matching obtained by selecting a pair of jobs for each time step
where at least two jobs are scheduled in $x^{M}$. Since
$F(x^{M})=2(M-|P|)+|P|+m^{*}_{P}$ according to the induction hypothesis, there
are $M-|P|+m^{*}_{P}$ such time steps. It is then clear that $\mu$ is a
matching between independent jobs of size $M-|P|+m^{*}_{P}$. This matching is
not maximum because
$M-|P|+m^{*}_{P}\leq|P|+m^{*}-m^{*}_{P}-1-|P|+m^{*}_{P}<m^{*}$. By Berge’s
Theorem, there exists an augmenting path
$\rho=(i_{0},j_{1},i_{1},j_{2},i_{2},\dots,j_{r},i_{r},j_{r+1})$ in
$\widetilde{G}$ such that $\\{i_{q},j_{q}\\}\in\mu$ for each
$q\in\\{1,\dots,r\\}$ and such that neither $i_{0}$ nor $j_{r+1}$ are matched
in $\mu$. Notice the following:

  * -

If exactly two jobs were scheduled at $x^{M}_{i_{0}}$, $i_{0}$ would be in
$\mu$. Either $1$ or $3$ jobs are scheduled at $x^{M}_{i_{0}}$.

  * -

If exactly two jobs were scheduled at $x^{M}_{j_{r+1}}$, $j_{r+1}$ would be in
$\mu$. Either $1$ or $3$ jobs are scheduled at $x^{M}_{j_{r+1}}$.

  * -

By construction of $\mu$, $x^{M}_{i_{q}}=x^{M}_{j_{q}}$ for every
$q\in\\{1,\dots,r\\}$.

Furthermore, if $x_{i_{0}}$ and $x_{j_{r+1}}$ were equal, three jobs would be
scheduled at $x_{i_{0}}$ and at least one job in $\\{i_{0},j_{r+1}\\}$ would
be matched in $\mu$. As a consequence, $x_{i_{0}}\neq x_{j_{r+1}}$. All the
requirements of Lemma 3 are now satisfied by $x^{M}$ and $\rho$. Applying
Lemma 3 gives that there exists a schedule $x^{M+1}$ of makespan $M+1$ such
that $F(x^{M+1})=2(M+1-|P|)+|P|+m^{*}_{P}$. This value reaches the upper bound
of Lemma 4 so $x^{M+1}$ is optimal.

Let us prove by induction on $M$ that there exists a schedule $x^{M}$ of
makespan $M$ such that $F(x^{M})=M+m^{*}$ for every
$M\in\\{|P|+m^{*}-m^{*}_{P},\dots,|J|-m^{*}\\}$. The case of
$M=|P|+m^{*}-m^{*}_{P}$ follows from the previous case.
Suppose that the property holds for some
$M\in\\{|P|+m^{*}-m^{*}_{P},\dots,|J|-m^{*}-1\\}$ and let $x^{M}$ be the
associated schedule. Using the induction hypothesis, $F(x^{M})=M+m^{*}$ and,
since $M<|J|-m^{*}$, $F(x^{M})<|J|$. There must exist a time step with at
least three jobs scheduled in $x^{M}$. A schedule $x^{M+1}$ with makespan
$M+1$ and such that $F(x^{M+1})=M+1+m^{*}$ can be obtained using one-job
elongation as shown in Figure 8. This value reaches the upper bound of Lemma 5
so $x^{M+1}$ is optimal.

For $M\geq|J|-m^{*}$, the schedule obtained through the method of Fujii et al.
is always optimal since it reaches the natural upper bound $|J|$ of the
objective function. ∎

###  3.3 Algorithm

The main steps in the resolution of $L2|prec,C_{max}\leq M,c_{i}=1,p_{i}=1|F$
are summarized in Algorithm 1. Schedule computation steps are not detailed but
rely in particular on the proofs of Lemma 1 and Lemma 3.

Algorithm 1 Sketch of algorithm for $L2|prec,C_{max}\leq M,c_{i}=1,p_{i}=1|F$

1:Choose a critical path $P$ in $G$

2:Compute $m^{*}_{P}$ and $m^{*}$ the size of a maximum matching in
$\widetilde{G}_{P}$ and $\widetilde{G}$ respectively

3:if $M\geq|J|-m^{*}$ then

4: Return the schedule computed with the method of Coffman and Graham
[1971/1972]

5:end if

6:Compute $x$ the earliest schedule of $G$

7:while $F(x)<|P|+m^{*}_{P}$ do

8: Compute a schedule $x^{\prime}$ of makespan $|P|$ with
$F(x^{\prime})=F(x)+1$ using Lemma 1

9: $x=x^{\prime}$

10:end while

11:if $M=|P|$ then

12: Return $x$

13:end if

14:while $C_{max}(x)<M$ do

15: if At least four jobs are scheduled at a time step in $x$ then

16: Compute a schedule $x^{\prime}$ of makespan $C_{max}(x)+1$ with
$F(x^{\prime})=F(x)+2$ using a two-job elongation

17: $x=x^{\prime}$

18: else if $C_{max}(x)<|P|+m^{*}-m^{*}_{P}$ then

19: Compute a schedule $x^{\prime}$ of makespan $C_{max}(x)+1$ with
$F(x^{\prime})=F(x)+2$ using Lemma 3

20: $x=x^{\prime}$

21: else

22: Compute a schedule $x^{\prime}$ of makespan $C_{max}(x)+1$ with
$F(x^{\prime})=F(x)+1$ using a one-job elongation

23: $x=x^{\prime}$

24: end if

25:end while

26:Return $x$

Let us discuss the time complexity of Algorithm 1. An important point to note
is that, although the method of Fujii et al. [1969] has been used, due to its
convenient matching structure, to prove that $L2|prec,C_{max}\leq
M,c_{i}=1,p_{i}=1|F$ is polynomial, it is not the most computationally
efficient. Therefore, solving problem $P2|prec,p_{i}=1|C_{max}$ when applying
Lemma 3 is done using the more efficient method of Coffman and Graham
[1971/1972]. The time required to perform the different computation steps is
as follows:

  * -

Computing the transitive closure of precedence graph $G$: $O(|J|^{3})$

  * -

Solving the problem for $M=|P|$:

    * -

Finding an augmenting sequence (alternating path in bipartite independence
graph $\widetilde{G}_{P}$): $O(|J|+|E_{P}|)$

    * -

Elementary operation: $O(|J|)$

    * -

Size of an augmenting path: $O(|P|)$

    * -

Maximum number of augmenting sequences to find: $|P|$

Total to solve the $M=|P|$ case: $O(|P|^{2}|J|)$

  * -

Improving the schedule up to $M$:

    * -

Finding an augmenting sequence in an arbitrary graph: $O(|E|)$ [Micali and
Vazirani, 1980]

    * -

Rescheduling on two machines: $O(|J|^{2})$ [Coffman and Graham, 1971/1972]

    * -

Maximum number of augmenting sequences to find: $|J|$

Total to improve the schedule up to $M$: $O(|J|^{3})$

Total computation time of Algorithm 1 is therefore $O(|J|^{3})$.

##  4 Further tractable special cases

In this section, five resource leveling problems are shown to be solvable in
polynomial or pseudo-polynomial time. Section 5 will show that further
generalization of those special cases leads to strongly $NP$-hard problems.

Precedence constraints, as considered in the core problem of this work, are
classical scheduling constraints and are present in many practical
applications. However, $L=2$ is very specific and solving problems with other
values of $L$ can be interesting. Section 4.1 shows that, when precedence
graphs are restricted to in-trees, the problem is solved to optimality for any
$L\in\mathbb{N}$ by adapting Hu’s algorithm [Hu, 1961]. Unit processing times
is also a strong assumption and results for more general $p_{i}$ values can be
of use. Section 4.2 shows that restricting the resource level to $L=1$ yields
another polynomial special case for any processing times.

Release and due dates are other classical scheduling constraints that can be
studied together with a resource leveling objective. Polynomial solving
methods are given for two problems with release dates and due dates in which
preemption is allowed. Section 4.3 deals with $L|r_{i},d_{i},c_{i}=1,pmtn|F$
by translating it as a flow problem. Section 4.4 solves
$L2|r_{i},d_{i},pmtn|F$ using linear programming.

Finally, Section 4.5 shows that, when there are no precedence constraints, a
tractable method exists for non-unit processing times and resource
consumptions. A pseudo-polynomial algorithm is provided for $L2|C_{max}\leq
M|F$ based on dynamic programming.

###  4.1 A polynomial algorithm for $L|in\text{-}tree,C_{max}\leq
M,p_{i}=1,c_{i}=1|F$

The classical scheduling problem $P|in\text{-}tree,C_{max}\leq
M,p_{i}=1|C_{max}$ can be solved in polynomial time using Hu’s algorithm [Hu,
1961]. In this section, its leveling counterpart is considered, namely
$L|in\text{-}tree,C_{max}\leq M,p_{i}=1,c_{i}=1|F$. The idea is therefore to
adapt the algorithm proposed in Hu [1961] in order to obtain a polynomial
algorithm to solve $L|in\text{-}tree,C_{max}\leq M,p_{i}=1,c_{i}=1|F$.
Hu’s algorithm can be applied in the case of Unit Execution Times (UET) when
the precedence graph is an in-tree. It is a list algorithm in which jobs are
sorted in increasing order of latest starting time.
The following algorithm uses the same priority list: jobs with small latest
starting time $\bar{\tau}_{i}$ are scheduled first. However, since the jobs
are constrained by the deadline $M$, the algorithm must execute at a given
time $\tau$ the jobs whose latest starting time is $\tau$ and that have not
been scheduled yet. This can cause the resource level $L$ to be exceeded.

Algorithm 2 UETInTreeLeveling$(J,G,L,M)$

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

2:$G_{0}\leftarrow G$

3:for $\tau=0,\dots,M-1$ do

4: Select up to $L$ leaves of $G_{\tau}$ with the smallest values of
$\bar{\tau}_{i}$, let this subset be $S_{\tau}$ $\triangleright$ Note that the
selected leaves may have different $\bar{\tau}_{i}$ values

5: $S_{\tau}=S_{\tau}\cup\\{i\text{ node of
}G_{\tau}\mid\bar{\tau}_{i}=\tau\\}$

6: for all $i\in S_{\tau}$ do

7: $x_{i}\leftarrow\tau$

8: end for

9: Build $G_{\tau+1}$ from $G_{\tau}$ by removing the jobs of $S_{\tau}$

10:end for

11:Return $x$

In order for a feasible schedule to exist, the deadline $M$ chosen as input
for UETInTreeLeveling should be at least the length of the critical path in
the precedence graph – which is the depth of the in-tree in the present case.
Furthermore, it can be assumed that $M\leq|J|$, which ensures that
UETInTreeLeveling is executed in polynomial time.
UETInTreeLeveling returns schedules with a very specific structure. The
following lemma gives some of those specificities that will prove to be useful
in showing that UETInTreeLeveling is actually optimal.

######  Lemma 6.

Let $x$ be the schedule returned by UETInTreeLeveling.
Suppose that at a given time step $\tau\in\\{0,\dots,M-1\\}$ the set
$S_{\tau}$ of jobs scheduled at $\tau$ in $x$ is such that $|S_{\tau}|>L$. The
following assertions are true:

  * (i) Every $i\in S_{\tau}$ has latest starting time $\bar{\tau}_{i}=\tau$;

  * (ii) For every $\tau^{\prime}\leq\tau$, $|S_{\tau^{\prime}}|\geq L$;

  * (iii) For every $\tau^{\prime}\leq\tau$, every $i\in S_{\tau^{\prime}}$ has latest starting time $\bar{\tau}_{i}\leq\tau$.

###### Proof.

First, it is clear that when time step $\tau$ is reached in UETInTreeLeveling,
all jobs with latest starting time at most $\tau-1$ have already been
scheduled. This is true thanks to the instruction of line 5 that ensures that
all jobs reaching their latest starting time are scheduled.
As a consequence, all jobs with latest starting time $\tau$ that remain in
$G_{\tau}$ are leaves and they have the lowest $\bar{\tau}_{i}$ value. There
are at least $L+1$ such jobs otherwise it would be impossible to have
$|S_{\tau}|>L$. The instruction of line 4 therefore selects $L$ jobs with
latest starting time $\tau$ and instruction of line 5 adds the remaining ones
to $S_{\tau}$. This proves assertion (i).
Due to assertion (i) and since $|S_{\tau}|>L$, there are at least $L$ jobs
with latest starting time $\tau$. For any $\tau^{\prime}\leq\tau$, $G_{\tau}$
is a subtree of $G_{\tau^{\prime}}$ so $G_{\tau^{\prime}}$ has at least $L$
leaves corresponding to jobs with latest starting time at most $\tau$. In
particular, $G_{\tau^{\prime}}$ has at least $L$ leaves, which ensures that
$|S_{\tau^{\prime}}|\geq L$ and proves assertion (ii).
Since UETInTreeLeveling prioritizes jobs with lower $\bar{\tau}_{i}$ values
and since for any $\tau^{\prime}\leq\tau$, $G_{\tau^{\prime}}$ has at least
$L$ leaves corresponding to jobs with latest starting time $\tau$ or less, no
job with latest starting time strictly higher than $\tau$ can be scheduled at
$\tau$ or before. This proves assertion (iii). ∎

######  Proposition 3.

$L|in\text{-}tree,C_{max}\leq M,p_{i}=1,c_{i}=1|F$ is solvable in polynomial
time using UETInTreeLeveling.

###### Proof.

Let $x$ be the schedule returned by UETInTreeLeveling. Figure 11 gives an
example of such a schedule and illustrates the decomposition of the objective
function that follows. For any time step $\tau\in\\{0,\dots,M-1\\}$, let
$S_{\tau}$ denote the set of jobs scheduled at $\tau$ in $x$.
First, $x$ is a feasible schedule. Indeed, by selecting leaves of the subtree
$G_{\tau}$, the instruction of line 4 ensures that the predecessors of the
selected jobs have already been scheduled, thus satisfying precedence
constraints. As for the deadline constraint, it is satisfied thanks to the
instruction of line 5 that ensures that each job is scheduled no later than
its latest starting time.
If for every $\tau\in\\{0,\dots,M-1\\}$, $|S_{\tau}|\leq L$, then $x$ is
optimal since $F(x)=|J|$, which reaches a natural upper bound on $F$.
If not, let $\tau$ be the largest time step such that $|S_{\tau}|>L$. In any
feasible schedule, all jobs $i$ with latest starting time
$\bar{\tau}_{i}\leq\tau$ must be scheduled at $\tau$ or before. It implies
that only jobs $i$ with latest starting time $\bar{\tau}_{i}>\tau$ can be
scheduled on time steps $\tau+1,\tau+2,\dots,M-1$. An upper bound on $F$ is
therefore given by $(\tau+1)L+|\\{i\in J\mid\bar{\tau}_{i}>\tau\\}|$.
Assertion (ii) of Lemma 6 gives that the contribution to $F(x)$ of interval
$[0,\tau+1]$ is
$\sum_{\tau^{\prime}=0}^{\tau}\min(L,|S_{\tau^{\prime}}|)=(\tau+1)L$. Since
$\tau$ is the last time step such that $|S_{\tau}|>L$ and given assertion
(iii) of Lemma 6, all jobs of $\\{i\in J\mid\bar{\tau}_{i}>\tau\\}$ are
scheduled on time steps $\tau+1,\tau+2,\dots,M-1$ without exceeding resource
level $L$. It then holds that the contribution to $F(x)$ of interval
$[\tau+1,M]$ is $|\\{i\in J\mid\bar{\tau}_{i}>\tau\\}|$. Finally, the value of
$F(x)$ writes:

$F(x)=(\tau+1)L+|\\{i\in J\mid\bar{\tau}_{i}>\tau\\}|$

which reaches the previously given upper bound and is therefore optimal. ∎

Figure 11: Example of schedule resulting from UETInTreeLeveling

###  4.2 A polynomial algorithm for $L1|prec,C_{max}\leq M,c_{i}>0|F$

Suppose that $L=1$ and that $c_{i}>0$ for every $i\in J$. Let us also assume
that the makespan deadline $M$ is larger than the longest path in the
precedence graph – otherwise no feasible schedule exists. For any $i\in J$,
let us denote $\bar{\tau}_{i}$ the latest starting time of job $i$, i.e., the
makespan deadline $M$ minus the longest path from job $i$ in the precedence
graph $G$.
Algorithm UnitResourceLeveling below starts by scheduling jobs sequentially in
a topological order and then schedules the remaining ones at their latest
starting time.

Algorithm 3 UnitResourceLeveling$(J,G,p)$

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

2:Choose a topological order $i_{1},i_{2},\dots,i_{n}$ on $J$

3:$x_{i_{1}}=0$

4:for all $k\in\\{2,\dots,n\\}$ do

5:
$x_{i_{k}}\leftarrow\min(\sum_{k^{\prime}=1}^{k-1}p_{i_{k^{\prime}}},\bar{\tau}_{i_{k}})$

6:end for

7:Return $x$

######  Proposition 4.

UnitResourceLeveling solves $L1|prec,C_{max}\leq M,c_{i}>0|F$ in polynomial
time.

###### Proof.

Let us prove that UnitResourceLeveling can be executed in
$O(|J|+|\mathcal{A}|)$ time (recall that $\mathcal{A}$ is the set of arcs in
the precedence graph). First, $\bar{\tau}_{i}$ values for every $i\in J$ as
well as the topological order can be computed with a graph traversal in
$O(|J|+|\mathcal{A}|)$ time. As for the main loop, it can be executed in
$O(|J|)$ time.
Let us now prove that UnitResourceLeveling provides a schedule that maximizes
the time during which at least one unit of resource is used.
In the particular case where $\sum_{i\in J}p_{i}\leq M$, it is easily seen
that all the jobs can be scheduled consecutively in a topological order thus
leading to a resource usage that is always at most $L=1$. It is exactly what
the algorithm does since, when $\sum_{i\in J}p_{i}\leq M$, the inequality
$\sum_{k^{\prime}=1}^{k-1}p_{i_{k}}\leq\bar{\tau}_{i_{k}}$ always holds on
line 5.
If $\sum_{i\in J}p_{i}>M$ then there exists $k>1$ such that
$\sum_{k^{\prime}=1}^{k-1}p_{i_{k^{\prime}}}>\bar{\tau}_{i_{k}}$. Let $k$ be
the first such index. In the schedule returned by UnitResourceLeveling, jobs
$i_{1},i_{2},\dots,i_{k-1}$ are scheduled consecutively without interruption
on time interval $[0,\sum_{k^{\prime}=1}^{k-1}p_{i_{k^{\prime}}}]$. By
definition of $\bar{\tau}_{i_{k}}$, the jobs on a longest path starting from
$i_{k}$ are executed without interruption on time interval
$[\bar{\tau}_{i_{k}},M]$. Given that
$\sum_{k^{\prime}=1}^{k-1}p_{i_{k^{\prime}}}>\bar{\tau}_{i_{k}}$, the returned
schedule uses at least one unit of resource constantly on time interval
$[0,M]$. The amount of resource below the level $L=1$ is therefore maximized.
Also note that the vector $x$ returned by UnitResourceLeveling is a feasible
schedule as it satisfies precedence constraints. Indeed, given an arc $(i,j)$
of the precedence graph it is clear that, by definition,
$\bar{\tau}_{i}+p_{i}\leq\bar{\tau}_{j}$ and that $i$ comes before $j$ in any
topological order. If $x_{j}=\bar{\tau}_{j}$, then
$x_{i}\leq\bar{\tau}_{i}\leq\bar{\tau}_{j}-p_{i}=x_{j}-p_{i}$ and therefore
$x_{i}+p_{i}\leq x_{j}$. Assuming that $i=i_{k}$ and $j=i_{k^{\prime}}$ in the
topological order, if
$x_{j}=\sum_{k^{\prime\prime}=1}^{k^{\prime}-1}p_{i_{k^{\prime\prime}}}$, then
$x_{i}\leq\sum_{k^{\prime\prime}=1}^{k-1}p_{i_{k^{\prime\prime}}}\leq\sum_{k^{\prime\prime}=1}^{k^{\prime}-1}p_{i_{k^{\prime\prime}}}-p_{i}=x_{j}-p_{i}$
and therefore $x_{i}+p_{i}\leq x_{j}$. ∎

###  4.3 A polynomial algorithm for $L|r_{i},d_{i},c_{i}=1,pmtn|F$

The aim of this section is to show that Problem $L|r_{i},d_{i},c_{i}=1,pmtn|F$
reduces to a linear program. Let $\tau_{0}<\tau_{1}<\tau_{2}<\dots<\tau_{K}$
be such that $\\{\tau_{0},\tau_{1},\dots,\tau_{K}\\}=\\{r_{i}\mid i\in
J\\}\cup\\{d_{i}\mid i\in J\\}$. For convenience, let also
$\kappa_{i}=\\{k\in\\{1,\dots,K\\},[\tau_{k-1},\tau_{k}]\subseteq[r_{i},d_{i}]\\}$.
The following variables are considered:

  * -

$x_{ik}$ $\forall i\in J,\;\forall k\in\kappa_{i}$: the number of time units
of job $i$ processed during interval $[\tau_{k-1},\tau_{k}]$;

  * -

$y_{k}$ $\forall k\in\\{1,\dots,K\\}$: number of time units processed on
interval $[\tau_{k-1},\tau_{k}]$ not exceeding the resource level;

  * -

$z_{k}$ $\forall k\in\\{1,\dots,K\\}$: number of time units processed on
interval $[\tau_{k-1},\tau_{k}]$ over the resource level;

Note that the following program only provides an implicit solution of Problem
$L|r_{i},d_{i},c_{i}=1,pmtn|F$. Variables $x_{ik}$ give the number of time
units of a job $i$ in the interval $[\tau_{k-1},\tau_{k}]$ but this does not
tell when each individual time unit is executed. It will be shown later that
an algorithm can be used to deduce a fully-fledged solution of
$L|r_{i},d_{i},c_{i}=1,pmtn|F$ from $x_{ik}$ values.
The program writes:

$\displaystyle\max_{x,y,z}\quad$ $\displaystyle\sum_{k=1}^{K}y_{k}$
$\displaystyle s.t.\quad$ $\displaystyle\sum_{k\in\kappa_{i}}x_{ik}=p_{i}$
$\displaystyle\forall i\in J$ (1) $\displaystyle
y_{k}+z_{k}=\sum_{\begin{subarray}{c}i\in J\\\ \kappa_{i}\ni
k\end{subarray}}x_{ik}$ $\displaystyle\forall k\in\\{1,\dots,K\\}$ (2)
$\displaystyle 0\leq x_{ik}\leq\tau_{k}-\tau_{k-1}$ $\displaystyle\forall i\in
J,\;\forall k\in\\{1,\dots,K\\}$ (3) $\displaystyle 0\leq
y_{k}\leq(\tau_{k}-\tau_{k-1})L$ $\displaystyle\forall k\in\\{1,\dots,K\\}$
(4) $\displaystyle z_{k}\geq 0$ $\displaystyle\forall k\in\\{1,\dots,K\\}$ (5)

Note that in this program, maximizing $\sum_{k=1}^{K}y_{k}$ is equivalent to
minimizing $\sum_{k=1}^{K}z_{k}$ since $\sum_{k=1}^{K}y_{k}+z_{k}=\sum_{i\in
J}p_{i}$. The alternative program writes:

$\displaystyle\min_{x,y,z}\quad$ $\displaystyle\sum_{k=1}^{K}z_{k}$
$\displaystyle s.t.\quad$
$\displaystyle(\ref{constraint:first})\dots(\ref{constraint:last})$

It can be interpreted as a minimum cost flow problem. Figure 12 shows the
structure of the flow graph with flow values on arcs. The costs are equal to
one for arcs with $z_{k}$ and $0$ otherwise. Arcs with $x_{ik}$ have capacity
$\tau_{k}-\tau_{k-1}$, arcs with $y_{k}$ have capacity
$L(\tau_{k}-\tau_{k-1})$ and arcs with $z_{k}$ have infinite capacity.

Figure 12: Flow graph with source $s$ and sink $t$

An explicit solution of Problem $L|r_{i},d_{i},c_{i}=1,pmtn|F$ can be
constructed with an additional post-processing step. Consider the interval
$[\tau_{k-1},\tau_{k}]$ for some $k$ in $\\{1,\dots,K\\}$ and let
$J_{k}=\\{i\in J\mid[\tau_{k-1},\tau_{k}]\subseteq[r_{i},d_{i}]\\}$.
The following algorithm, illustrated in Figure 13, computes the sub-intervals
of $[\tau_{k-1},\tau_{k}]$ on which each job of $J_{k}$ is executed. Its idea
is simple: the interval is filled line by line from left to right by placing
one job after another and starting a new line every time the end of the
interval is reached. Those line breaks may cause a job to be split into two
parts, one reaching the end of the interval and the other starting back from
the beginning.

Algorithm 4 IntervalScheduling$(J_{k},x_{.k},\tau_{k-1},\tau_{k})$

1:$t\leftarrow 0$

2:for all $i\in J_{k}$ do

3: $t^{\prime}=t+x_{ik}$

4: if $t^{\prime}\leq\tau_{k}-\tau_{k-1}$ then

5: $I_{i}\leftarrow\\{[\tau_{k-1}+t,\tau_{k-1}+t^{\prime}]\\}$

6: else

7: $t^{\prime}=t^{\prime}-(\tau_{k}-\tau_{k-1})$

8: $I_{i}=\\{[\tau_{k-1},\tau_{k-1}+t^{\prime}],[\tau_{k-1}+t,\tau_{k}]\\}$

9: end if

10: $t=t^{\prime}$

11:end for

12:Return $(I_{i})_{i\in J_{k}}$

Figure 13: Example of interval job scheduling for
$J_{k}=\\{i_{1},i_{2},i_{3},i_{4}\\}$, $\tau_{k}-\tau_{k-1}=5$,
$x_{i_{1}k}=3$, $x_{i_{2}k}=4$, $x_{i_{3}k}=2$, $x_{i_{4}k}=4$

It is clear that IntervalScheduling is executed in $O(|J|)$ time. Executing it
for each $k\in\\{1,\dots,K\\}$ can therefore be done in $O(|J|^{2})$. Note
that in the solution provided by IntervalScheduling, each job $i_{l}$ is
executed on either one or two sub-intervals of $[\tau_{k-1},\tau_{k})$. As a
consequence, each job is executed on at most $O(|J|)$ disjoint intervals in
the final solution.

######  Proposition 5.

$L|r_{i},d_{i},c_{i}=1,pmtn|F$ is solvable in polynomial time.

######  Proposition 6.

$L|r_{i},d_{i},p_{i}=1,c_{i}=1|F$ is solvable in polynomial time.

###### Proof.

Since $L|r_{i},d_{i},c_{i}=1,pmtn|F$ reduces to a minimum cost flow problem,
standard algorithms can be used to solve it and yield integer solutions when
$p_{i},r_{i},d_{i}\in\mathbb{N}$. In particular, optimal integer solutions can
be found for $L|r_{i},d_{i},p_{i}=1,c_{i}=1,pmtn|F$, which is actually the
same as finding optimal solutions for $L|r_{i},d_{i},p_{i}=1,c_{i}=1|F$. ∎

###  4.4 A polynomial algorithm for $L2|r_{i},d_{i},pmtn|F$

Similarly as in Section 4.3, the aim of this section is to show that problem
$L2|r_{i},d_{i},pmtn|F$ reduces to a linear program. It will be assumed that
all considered instances are feasible, namely that $p_{i}\leq d_{i}-r_{i}$ for
every job $i\in J$.
In Problem $L2|r_{i},d_{i},pmtn|F$, the resource consumption $c_{i}$ of job
$i\in J$ can take any value in $\mathbb{N}$, yet it is sufficient to consider
the case where $c_{i}\in\\{1,2\\}$. Indeed, since objective function $F$ only
takes into consideration the resource consumption that fits under resource
level $L=2$, any $c_{i}>2$ can be handled as $c_{i}=2$ without changing the
optimum. As for potential jobs $c_{i}=0$, they have no impact on the
objective.

Let us then suppose that $c_{i}\in\\{1,2\\}$ for every $i\in J$ and denote
$J_{1}=\\{i\in J\mid c_{i}=1\\}$ and $J_{2}=\\{i\in J\mid c_{i}=2\\}$. Let
$\tau_{0}<\tau_{1}<\tau_{2}<\dots<\tau_{K}$ be such that
$\\{\tau_{0},\tau_{1},\dots,\tau_{K}\\}=\\{r_{i}\mid i\in J\\}\cup\\{d_{i}\mid
i\in J\\}$. For convenience, let also
$\kappa_{i}=\\{k\in\\{1,\dots,K\\},[\tau_{k-1},\tau_{k}]\subseteq[r_{i},d_{i}]\\}$.
The following variables are considered:

  * -

$x^{1}_{ik}$ $\forall i\in J_{1},\;\forall k\in\kappa_{i}$: the number of time
units of job $i$ processed during interval $[\tau_{k-1},\tau_{k}]$ that fit
under the resource level;

  * -

$x^{2}_{ik}$ $\forall i\in J_{2},\;\forall k\in\kappa_{i}$: the number of time
units of job $i$ processed during interval $[\tau_{k-1},\tau_{k}]$ that fit
under the resource level.

Just like in Section 4.3, the following linear program only gives an implicit
solution of the problem from which a proper schedule can then be deduced. The
program writes:

$\displaystyle\max_{x^{1},x^{2}}\quad$ $\displaystyle\sum_{i\in
J_{1}}\sum_{k\in\kappa_{i}}x^{1}_{ik}+2\sum_{i\in
J_{2}}\sum_{k\in\kappa_{i}}x^{2}_{ik}$ $\displaystyle s.t.\quad$
$\displaystyle\sum_{k\in\kappa_{i}}x^{\alpha}_{ik}\leq p_{i}$
$\displaystyle\forall\alpha\in\\{1,2\\},\;\forall i\in J_{\alpha}$ (6)
$\displaystyle
x^{1}_{ik}\leq(\tau_{k+1}-\tau_{k})-\sum_{\begin{subarray}{c}j\in J_{2}\\\
\kappa_{j}\ni k\end{subarray}}x^{2}_{jk}$ $\displaystyle\forall i\in
J_{1},\;\forall k\in\kappa_{i}$ (7)
$\displaystyle\sum_{\begin{subarray}{c}i\in J_{1}\\\ \kappa_{i}\ni
k\end{subarray}}x^{1}_{ik}\leq
2\left((\tau_{k+1}-\tau_{k})-\sum_{\begin{subarray}{c}j\in J_{2}\\\
\kappa_{j}\ni k\end{subarray}}x^{2}_{jk}\right)$ $\displaystyle\forall
k\in\\{1,\dots,K\\}$ (8) $\displaystyle\sum_{\begin{subarray}{c}i\in J_{2}\\\
\kappa_{i}\ni k\end{subarray}}x^{2}_{ik}\leq(\tau_{k+1}-\tau_{k})\forall
k\in\\{1,\dots,K\\}$ (9) $\displaystyle x^{\alpha}_{ik}\geq 0$
$\displaystyle\forall\alpha\in\\{1,2\\},\;\forall i\in J_{\alpha},\;\forall
k\in\kappa_{i}$ (10)

A complete solution in which each job is given a set of intervals on which it
is executed can be deduced from optimal values of $x^{1}_{ik}$ and
$x^{2}_{ik}$ variables. Recall that variable $x^{1}_{ik}$ and $x^{2}_{ik}$
only represent the portions of the jobs that fit under the resource level.
Those portions of jobs are scheduled on each interval $[\tau_{k-1},\tau_{k}]$
as shown in Figure 14: the jobs of $J_{2}$ are scheduled first, then the jobs
of $J_{1}$ are scheduled in the remaining space with Algorithm 4. Once this is
done, the processing time left for each job $i$ can be scheduled anywhere in
the remaining space of its availability interval $[r_{i},d_{i}]$. The initial
assumption that $p_{i}\leq d_{i}-r_{i}$ for every job $i\in J$ ensures that it
is possible to do so.

Figure 14: Example of interval job scheduling

######  Proposition 7.

$L2|r_{i},d_{i},pmtn|F$ is solvable in polynomial time.

######  Remark 2.

Unlike in the case of Section 4.3, nothing guarantees to find integer solution
to the problem.

######  Remark 3.

The method can be generalized to Problem
$L|r_{i},d_{i},pmtn,c_{i}\in\\{1,L\\}|F$, in which jobs either consume one or
$L$ units of resource.

###  4.5 A pseudo-polynomial algorithm for $L2|C_{max}\leq M|F$

In order to solve $L2|C_{max}\leq M|F$ in pseudo-polynomial time, some
assumptions are made w.l.o.g. to exclude trivial cases. First, it can be
assumed that resource consumptions values are in $\\{0,1,2\\}$. Indeed, when
$L=2$, replacing resource consumption of each job $i\in J$ by
$\widetilde{c}_{i}=\min(c_{i},2)$ does not change the objective function
values. Jobs with resource consumption $c_{i}=0$ have no impact and can be
scheduled at any feasible date, they can be ignored. Only jobs with
$c_{i}\in\\{1,2\\}$ are to be considered in the sequel.

Let us denote $J_{1}=\\{i\in J\mid c_{i}=1\\}$ and $J_{2}=\\{i\in J\mid
c_{i}=2\\}$. Let also $p_{J_{1}}=\sum_{i\in J_{1}}p_{i}$ and
$p_{J_{2}}=\sum_{i\in J_{2}}p_{i}$. If $p_{J_{2}}\geq M$, the problem is
solved simply by scheduling the jobs of $J_{2}$ one after another while
possible and at their latest possible date afterwards. This uses at least two
units of resource constantly on $[0,M]$ thus maximizing $F$. Let us therefore
assume that $p_{J_{2}}<M$.

The following lemma links the objective value of a schedule $x$ to a subset of
$J_{1}$, allowing for the construction of the former from the latter.

######  Lemma 7.

Let $I=(J,p,c,M)$ be an instance of $L2|C_{max}\leq M|F$.
For any subset of jobs $J^{\prime}\subseteq J_{1}$, there exists a schedule
$x$ such that:

$\displaystyle F(x)\geq 2p_{J_{2}}$ $\displaystyle+\min(\sum_{i\in
J^{\prime}}p_{i},M-p_{J_{2}})$ $\displaystyle+\min(\sum_{i\in J_{1}\setminus
J^{\prime}}p_{i},M-p_{J_{2}})$

Furthermore, $x$ can be computed in polynomial time.

###### Proof.

The schedule $x$ is built as follows and as illustrated in Figure 15:

  * -

The jobs of $J_{2}$ are scheduled one after the other from $0$ to $p_{J_{2}}$.

  * -

The jobs of $J^{\prime}$ are scheduled one after the other, starting from
$p_{J_{2}}$, while the makespan deadline is not exceeded and at their latest
possible date afterwards.

  * -

The jobs of $J_{1}\setminus J^{\prime}$ are scheduled as the jobs of
$J^{\prime}$

Figure 15: Schedule construction

The schedule $x$ is such that:

  * -

The jobs of $J_{2}$ use exactly two units of resource on $[0,p_{J_{2}}]$;

  * -

The jobs of $J^{\prime}$ use at least one unit of resource on
$[p_{J_{2}},p_{J_{2}}+\min(\sum_{i\in J^{\prime}}p_{i},M-p_{J_{2}})]$;

  * -

The jobs of $J_{1}\setminus J^{\prime}$ use at least one unit of resource on
$[p_{J_{2}},p_{J_{2}}+\min(\sum_{i\in J_{1}\setminus
J^{\prime}}p_{i},M-p_{J_{2}})]$.

This implies that $F(x)\geq 2p_{J_{2}}+\min(\sum_{i\in
J^{\prime}}p_{i},M-p_{J_{2}})+\min(\sum_{i\in J_{1}\setminus
J^{\prime}}p_{i},M-p_{J_{2}})$. ∎

Having two jobs of $J_{2}$ that overlap in a schedule is never advantageous in
terms of leveling objective. This idea is formalized in the following lemma:

######  Lemma 8.

The schedules in which the jobs of $J_{2}$ do not overlap are dominant.

###### Proof.

One job of $J_{2}$ is sufficient to reach resource level $L=2$ for its whole
duration and overlapping with another job is a missed contribution to function
$F$. Given the previous assumption that $p_{J_{2}}<M$, it is always possible
to find an optimal schedule in which the jobs of $J_{2}$ do not overlap. ∎

The following lemma complements the inequality of Lemma 7 by another
inequality that is valid when the jobs of $J_{2}$ do not overlap.

######  Lemma 9.

Let $I=(J,p,c,M)$ be an instance of $L2|C_{max}\leq M|F$ and let
$x\in\mathbb{N}^{J}$ be a feasible schedule for $I$ such that the jobs of
$J_{2}$ do not overlap.
Then there exists a subset of jobs $J^{\prime}\subseteq J_{1}$ such that:

$\displaystyle F(x)\leq 2p_{J_{2}}$ $\displaystyle+\min(\sum_{i\in
J^{\prime}}p_{i},M-p_{J_{2}})$ $\displaystyle+\min(\sum_{i\in J_{1}\setminus
J^{\prime}}p_{i},M-p_{J_{2}})$

###### Proof.

Let us build two disjoint subsets $J^{\prime},J^{\prime\prime}\subseteq J_{1}$
from $x$ using the following procedure:

1:$J^{\prime}\leftarrow\emptyset$ $J^{\prime\prime}\leftarrow\emptyset$

2:for $\tau=0,\dots,M-1$ do

3: if a job of $J_{2}$ is processed on time step $\tau$ in $x$ then

4: Continue

5: end if

6: for $\widetilde{J}=J^{\prime},J^{\prime\prime}$ do

7: if a job of $\widetilde{J}$ is processed on time step $\tau$ in $x$ then

8: Continue

9: else if a job of $i\in J\setminus(J^{\prime}\cup J^{\prime\prime})$ is
processed on time step $\tau$ in $x$ then

10: $\widetilde{J}=\widetilde{J}\cup\\{i\\}$

11: end if

12: end for

13:end for

14:Return $J^{\prime},J^{\prime\prime}$

Let us denote $T^{\prime}$ (resp. $T^{\prime\prime}$) the set of time steps
where no job of $J_{2}$ is processed and where at least one job of
$J^{\prime}$ (resp. $J^{\prime\prime}$) is processed. It is clear that
$|T^{\prime}|\leq\min(\sum_{i\in J^{\prime}}p_{i},M-p_{J_{2}})$ and
$|T^{\prime\prime}|\leq\min(\sum_{i\in J^{\prime\prime}}p_{i},M-p_{J_{2}})$.
For any time step $\tau\in\\{0,\dots,M-1\\}$, three cases are possible:

  * -

$\tau\in T^{\prime}\cap T^{\prime\prime}$: at least two jobs of $J_{1}$ are
processed at time step $\tau$ in $x$, one being in $J^{\prime}$ and another in
$J^{\prime\prime}$;

  * -

$\tau\in(T^{\prime}\setminus T^{\prime\prime})\cup(T^{\prime\prime}\setminus
T^{\prime})$: exactly one job of $J_{1}$ is processed at time step $\tau$ in
$x$, it is either in $J^{\prime}$ or in $J^{\prime\prime}$;

  * -

$\tau\notin T^{\prime}\cup T^{\prime\prime}$: either a job of $J_{2}$ is
processed at time step $\tau$ in $x$ or no job at all, otherwise it would have
been added to either $J^{\prime}$ or $J^{\prime\prime}$ in the procedure.

In other words, $F(x)=2p_{J_{2}}+|T^{\prime}|+|T^{\prime\prime}|$ and as a
consequence $F(x)\leq 2p_{J_{2}}+\min(\sum_{i\in
J^{\prime}}p_{i},M-p_{J_{2}})+\min(\sum_{i\in
J^{\prime\prime}}p_{i},M-p_{J_{2}})$. The final inequality $F(x)\leq
2p_{J_{2}}+\min(\sum_{i\in J^{\prime}}p_{i},M-p_{J_{2}})+\min(\sum_{i\in
J_{1}\setminus J^{\prime}}p_{i},M-p_{J_{2}})$ is derived using that
$J^{\prime\prime}\subseteq J_{1}\setminus J^{\prime}$. ∎

Thanks to Lemma 8, the inequality of Lemma 9 actually applies to any schedule.
Combining it with the inequality of Lemma 7 yields the following equality:

$\displaystyle\max_{x}F(x)=2p_{J_{2}}+\max_{J^{\prime}\subseteq J_{1}}$
$\displaystyle\left(\min(\sum_{i\in J^{\prime}}p_{i},M-p_{J_{2}})\right.$
$\displaystyle\left.+\min(\sum_{i\in J_{1}\setminus
J^{\prime}}p_{i},M-p_{J_{2}})\right)$ (11)

It is then clear that if a subset $J^{\prime}\subseteq J_{1}$ is found that
maximizes $\min(\sum_{i\in J^{\prime}}p_{i},M-p_{J_{2}})+\min(\sum_{i\in
J_{1}\setminus J^{\prime}}p_{i},M-p_{J_{2}})$, the maximum value of $F$ over
feasible schedules can be deduced directly. Furthermore, using Lemma 7, it is
actually possible to build a schedule $x$ from $J^{\prime}$ such that:

$\displaystyle F(x)\geq 2p_{J_{2}}$ $\displaystyle+\min(\sum_{i\in
J^{\prime}}p_{i},M-p_{J_{2}})$ $\displaystyle+\min(\sum_{i\in J_{1}\setminus
J^{\prime}}p_{i},M-p_{J_{2}})$

Schedule $x$ thus maximizes $F$, it is an optimal solution of the problem.

A possible interpretation of Equation 11 is that solving $L2|C_{max}\leq M|F$
is equivalent to solving a two-machine early work maximization problem on the
jobs of $J_{1}$: subset $J^{\prime}$ (resp. $J\setminus J^{\prime}$)
corresponds to the jobs scheduled on the first (resp. second) machine and the
portion of jobs executed before date $M-p_{J_{2}}$ is maximized. By
complementarity of the early and late work criterions, the equivalence with
the late work minimization version of the problem also holds. Late work
minimization on two machines with common deadline, namely $P2|d_{j}=d|Y$ is
studied in Chen et al. [2016] and shown to be solvable in pseudo-polynomial
time. Applying the algorithm proposed in Chen et al. [2016] leads to a
solution method for $L2|C_{max}\leq M|F$ running in
$O(|J|+|J_{1}|p_{j_{1}}^{2})$. Yet, finding an optimal subset $J^{\prime}$ can
be done with a better time complexity using standard dynamic programming. A
table $T[k,b]_{0\leq k\leq|J_{1}|,\;0\leq b\leq p_{J_{1}}}$ can be computed in
time $O(|J_{1}|p_{J_{1}})$ where $T[k,b]=1$ if there exists a subset of the
first $k$ jobs of $J_{1}$ whose sum is $b$ and $T[k,b]=0$ otherwise. Then, for
each $b$ such that $T[|J_{1}|,b]=1$, the values of
$\min(b,M-p_{J_{2}})+\min(p_{J_{1}}-b,M-p_{J_{2}})$ can be computed in order
to find the maximum value. This maximum value is optimal and the corresponding
optimal subset $J^{\prime}\subseteq J_{1}$ can be recovered with a standard
backward technique in time $O(|J_{1}|)$.

This leads to the following proposition:

######  Proposition 8.

Problem $L2|C_{max}\leq M|F$ can be solved in $O(|J|+|J_{1}|p_{J_{1}})$ time.

###### Proof.

A subset $J^{\prime}\subseteq J_{1}$ that maximizes $\min(\sum_{i\in
J^{\prime}}p_{i},M^{\prime})+\min(\sum_{i\in J_{1}\setminus
J^{\prime}}p_{i},M^{\prime})$ can be built in time $O(|J_{1}|p_{J_{1}})$ using
dynamic programming.
Lemmas 7 and 9 guarantee that $J^{\prime}$ satisfies
$\max_{x}F(x)=2p_{J_{2}}+\min(\sum_{i\in
J^{\prime}}p_{i},M^{\prime})+\min(\sum_{i\in J_{1}\setminus
J^{\prime}}p_{i},M^{\prime})$. Moreover, lemma 7 states that a schedule $x$
can be built from $J^{\prime}$ that maximizes $F$. This can be done in
$O(|J|)$ time.
An optimal schedule for an instance of problem $L2|C_{max}\leq M,c_{i}=1|F$
can therefore be found with a total computation time of
$O(|J|+|J_{1}|p_{J_{1}})$. ∎

##  5 $NP$-hardness results

Some of the algorithms presented in the previous sections highlight
similarities between resource leveling and classical scheduling problems in
terms of solution. This section shows that hardness results easily transfer
from machine scheduling problems to their leveling counterparts. This will
follow from the Lemma 10; it intuitively shows that resource leveling problems
can be seen as generalizations of classical machine scheduling problems.

######  Lemma 10.

Let $I^{\prime}$ be an instance of $Pk|\beta|C_{max}$ for some
$k\in\mathbb{N}$ and some set of constraints $\beta$. Let
$I^{\prime\prime}=(I^{\prime},M)$ be an instance of $Lk|\beta,C_{max}\leq
M,c_{i}=1|F$.
The two following assertions are equivalent:

  * (i) $I^{\prime}$ has a solution of makespan at most $M$

  * (ii) $I^{\prime\prime}$ has a feasible schedule $x$ with $F(x)=\sum_{i\in J}p_{i}$

###### Proof.

First note that a solution of $Pk|\beta|C_{max}$ is described by a schedule
$x$ and a partition $(J_{1},J_{2},\dots,J_{k})$ of $J$ such that $J_{l}$ is
the subset of non-overlapping jobs processed on the $l$-th machine.
(i) $\Rightarrow$ (ii) Let then $(x,(J_{1},J_{2},\dots,J_{k}))$ be a feasible
solution of $Pk|\beta|C_{max}$ with makespan at most $M$. It is clear that the
schedule $x$ is a feasible schedule for $Lk|\beta,C_{max}\leq M,c_{i}=1|F$
since it satisfies the constraints of $\beta$ and has makespan at most $M$.
Furthermore, the jobs can be processed on $k$ machines, which implies that the
resource consumption never exceeds $L=k$ and gives that $F(x)=\sum_{i\in
J}p_{i}$. As a consequence, $Lk|\beta,C_{max}\leq M,c_{i}=1|F$ has a feasible
schedule $x$ with $F(x)=\sum_{i\in J}p_{i}$.
(i) $\Leftarrow$ (ii) Let $x$ be a feasible schedule for $Lk|\beta,C_{max}\leq
M,c_{i}=1|F$ such that $F(x)=\sum_{i\in J}p_{i}$. Using the following
procedure, let us build a partition $J_{1},J_{2},\dots,J_{k}$ of $J$ such that
each $J_{l}$ is a subset of non-overlapping jobs.

1:$J_{l}\leftarrow\emptyset$ $\forall l\in\\{1,\dots,k\\}$

2:Sort the jobs of $J$ in increasing order of starting time in $x$

3:Let $i_{1},i_{2},\dots,i_{n}$ be the resulting list

4:for $i=i_{1},i_{2},\dots,i_{n}$ do

5: $l^{*}\leftarrow argmin_{l\in\\{1,\dots,k\\}}\max_{j\in
J_{l}}(x_{j}+p_{j})$ $\triangleright$ $l^{*}$ is the index of the least loaded
machine

6: $J_{l^{*}}=J_{l^{*}}\cup\\{i\\}$

7:end for

8:Return $(J_{1},J_{2},\dots,J_{k})$

The claim is that when $J_{l^{*}}$ is selected on line 5, $x_{i}\geq\max_{j\in
J_{l^{*}}}(x_{j}+p_{j})$. Indeed, if $x_{i}<\max_{j\in
J_{l^{*}}}(x_{j}+p_{j})$, by definition of $l^{*}$, all machines are loaded
and at least $k+1$ jobs are being processed simultaneously on the non-empty
interval $[x_{i},\max_{j\in J_{l^{*}}}(x_{j}+p_{j}))$, implying that
$F(x)<\sum_{i\in J}p_{i}$, which is a contradiction. The inequality
$x_{i}\geq\max_{j\in J_{l^{*}}}(x_{j}+p_{j})$ being verified at each step of
the procedure guarantees that the jobs in each $J_{l}$ do not overlap. A
feasible solution for $Pk|\beta|C_{max}$ with makespan at most $M$ is
therefore given by $(x,(J_{1},J_{2},\dots,J_{k}))$. ∎

The equivalence of Lemma 10 provides a general reduction from a problem of the
form $Pk|\beta|C_{max}$ to a problem of the form $Lk|\beta,C_{max}\leq
M,c_{i}=1|F$. The $NP$-hardness (resp. strong $NP$-hardness) of the former
thus implies the $NP$-hardness of the latter.

######  Corollary 1.

The problems listed below are strongly $NP$-hard:

  * -

$L1|r_{i},d_{i},c_{i}=1|F$

  * -

$L2|chains,C_{max}\leq M,c_{i}=1|F$

  * -

$L|C_{max}\leq M,c_{i}=1|F$

  * -

$L|prec,C_{max}\leq M,c_{i}=1,p_{i}=1|F$

Problem $L2|C_{max}\leq M,c_{i}=1|F$ is $NP$-hard.

###### Proof.

Problems $1|r_{i},d_{i}|C_{max}$, $P2|chains|C_{max}$, $P||C_{max}$ and
$P|prec,p_{i}=1|C_{max}$ are known to be strongly $NP$-hard (see respectively
[Garey and Johnson, 1977], [Du et al., 1991], [Garey and Johnson, 1978] and
[Ullman, 1975]). Problem $P2||C_{max}$ is known to be $NP$-hard [Lenstra et
al., 1977]. ∎

######  Remark 4.

While $P2|prec|C_{max}$ and $P|prec,p_{i}=1|C_{max}$ are known to be strongly
$NP$-hard, which can be used to prove the complexity of their leveling
counterparts, the complexity of $P3|prec,p_{i}=1|C_{max}$ remains unknown. It
is then not possible to get a complexity result for $L3|prec,C_{m}ax\leq
M,c_{i}=1,p_{i}=1|F$ based on Lemma 10.

The $NP$-hardness of $L1|r_{i},d_{i},c_{i}=1|F$ can actually be extended to
the case of $L=2$ quite naturally: an instance of $L1|r_{i},d_{i},c_{i}=1|F$
reduces to an instance of $L2|r_{i},d_{i},c_{i}=1|F$ with an additional job
$i$ verifying $p_{i}=M$, $r_{i}=0$ and $d_{i}=M$ since job $i$ uses one unit
of resource from $0$ to $M$. Hence the following corollary:

######  Corollary 2.

$L2|r_{i},d_{i},c_{i}=1|F$ is strongly $NP$-hard.

Another easy extension of Corollary 1 can be made to prove that $L1|chains|F$
is strongly $NP$-hard. It requires to notice that an instance $I$ of
$L1|r_{i},d_{i},c_{i}=1|F$ reduces to an instance of $L1|chains|F$ where each
job in $I$ is given a predecessor and a successor that force it to be
scheduled in its availability interval. More precisely, for a job $i$ in $I$,
two jobs $i^{\prime}$ and $i^{\prime\prime}$ are added with
$p_{i^{\prime}}=r_{i}$, $p_{i^{\prime\prime}}=M-d_{i}$,
$c_{i^{\prime}}=c_{i^{\prime\prime}}=0$ and precedence constraints
$(i^{\prime},i)$ and $(i,i^{\prime\prime})$. This gives the following
corollary:

######  Corollary 3.

$L1|chains|F$ is strongly $NP$-hard.

##  6 Summary of results

Table 1 summarizes the complexity results that were obtained in this work.
Column headers are classical scheduling constraints: makespan deadline
($C_{max}\leq M$), precedence constraints ($prec$), possibly in the form of an
$in\text{-}tree$ and release and due dates ($r_{i},d_{i}$), which may be
considered with or without preemption ($pmtn$). Row headers are parameters
restrictions: the value of $L$ may be restricted to one or two while unit
values may be imposed for processing times and resource consumptions.
The entries of the table include the complexity of the corresponding problem
as well as the result proving it. A natural question arising from this table
is the complexity of problems for $L=3$ or larger constant $L$, in particular
$L3|prec,c_{i}=1,p_{i}=1|F$. This latter problem generalizes
$P3|prec,p_{i}=1|C_{max}$, the complexity of which is a famous open problem in
scheduling.

######  Remark 5.

Problem $L1|C_{max}\leq M|F$ is solved to optimality by scheduling jobs with
$c_{i}>0$ one after another while $M$ is not exceeded and scheduling all
remaining jobs at $M-p_{i}$.
In the case of Problem $L|p_{i}=1,c_{i}=1,C_{max}\leq M|F$, all jobs are
independent from each other and equivalent, with unit processing time and
resource consumption. It is clear that scheduling one job per time step
sequentially, going back to $0$ when $M$ is reached, solves the problem to
optimality.

Table 1: Complexity of resource leveling problems

| $C_{max}\leq M$ | $prec,C_{max}\leq M$ | $r_{i},d_{i}$
---|---|---|---
| $prec=any$ | $prec=in\text{-}tree$ | $\text{no }pmtn$ | $pmtn$
$L1$ | $\emptyset$ |  in $P$ (Remark 5) |  str. $NP$-hard (Cor. 3) |  str. $NP$-hard (Cor. 1) |  in $P$ (Prop. 5)
$c_{i}>0$ |  in $P$ (Prop. 4)
$L2$ | $\emptyset$ |  in $P_{pseudo}$ (Prop. 8) $NP$-hard (Cor. 1) |  str. $NP$-hard (Cor. 1) |  str. $NP$-hard (Cor. 2) |  in $P$ (Prop. 7)
$c_{i}=1$
$p_{i}=c_{i}=1$ |  in $P$ (Remark 5) |  in $P$ (Th. 1) |  in $P$ (Prop. 6)
$L$ | $\emptyset$ |  str. $NP$-hard (Cor. 1) |  str. $NP$-hard [Györgyi and Kis, 2020]
$c_{i}=1$ |  in $P$ (Prop. 5)
$p_{i}=c_{i}=1$ |  in $P$ (Remark 5) |  str. $NP$-hard (Cor. 1) , |  in $P$ (Prop. 3) |  in $P$ (Prop. 6)

##  7 Conclusion

A polynomial-time algorithm solving a resource leveling counterpart of a well-
known two-processor scheduling problem is proposed in this paper as a main
result. As complementary results, various related resource leveling problems
are studied, some of which are shown to be solvable in polynomial time as
well. Close links are highlighted between classical machine scheduling
resource leveling. Both solving methods and $NP$-hardness results are mirrored
from one field to the other. While the translation of negative complexity
results is rather straightforward, the main contribution of this work lies on
the design of algorithms. Besides the core problem, an interesting result in
that regard is the adaptation of Hu’s algorithm to solve the case of unit
processing times with unit resource consumptions and an in-tree precedence
graph.

Although polynomial and pseudo-polynomial algorithms are given, the problem
variants that they can solve remain special cases. An interesting perspective
would be to consider more advanced constraints and less restrictive
parameters, to meet practical requirements. In particular, some problem
variants are polynomial for unit processing times but become strongly
$NP$-hard in the general case. A possible extension of this work would then be
to find good approximation algorithms for some of the more realistic resource
leveling problems.
The objective function that was chosen is certainly relevant to model resource
overload costs, yet it does not prevent peaks in resource use, which are often
ill-advised in practice. Studying the resource investment objective, which
minimizes the highest amount of resource consumption, could therefore be
another perspective for future research.

Table 2: Table of notations General
---
$J$ | Set of jobs
$p_{i}$ |  Processing time of job $i$
$c_{i}$ |  Resource consumption of job $i$
$G$ | Precedence graph
$\mathcal{A}$ |  Set of arcs in $G$
$x$ | Schedule
$x_{i}$ |  Starting time of job $i$ in schedule $x$
$L$ | Resource level
$M$ | Deadline on makespan
$F$ | Objective function
$P$ |  Critical path in $G$
Scheduling constraints
$C_{max}$ | Makespan
$prec$ | Precedence constraints
$in\text{-}tree$ | In-tree precedence graph
$pmtn$ | Preemption allowed
$r_{i}$ |  Release date of job $i$
$d_{i}$ |  Due date of job $i$
Auxiliary graphs
$\widetilde{G}$ | Independence graph
$E$ |  Set of edges in $\widetilde{G}$
$m^{*}$ |  Size of a maximum matching in $\widetilde{G}$
$\widetilde{G}_{P}$ |  Bipartite independence graph for critical path $P$
$E_{P}$ |  Set of edges in $\widetilde{G}_{P}$
$m^{*}_{P}$ |  Size of a maximum matching in $\widetilde{G}_{P}$

## References

  * Atan and Eren [2018] T. Atan and E. Eren.  Optimal project duration for resource leveling.  _European Journal of Operational Research_ , 266(2):508–520, 2018.
  * Berge [1957] C. Berge.  Two theorems in graph theory.  _Proceedings of the National Academy of Sciences_ , 43(9):842–844, 1957.
  * Bianco et al. [2016] L. Bianco, M. Caramia, and S. Giordani.  Resource levelling in project scheduling with generalized precedence relationships and variable execution intensities.  _OR spectrum_ , 38(2):405–425, 2016.
  * Bianco et al. [2017] L. Bianco, M. Caramia, and S. Giordani.  The total adjustment cost problem with variable activity durations and intensities.  _European Journal of Industrial Engineering_ , 11(6):708–724, 2017.
  * Chen et al. [2016] X. Chen, M. Sterna, X. Han, and J. Blazewicz.  Scheduling on parallel identical machines with late work criterion: Offline and online cases.  _Journal of Scheduling_ , 19:729–736, 2016.
  * Chen et al. [2020] X. Chen, Y. Liang, M. Sterna, W. Wang, and J. Błażewicz.  Fully polynomial time approximation scheme to maximize early work on parallel machines with common due date.  _European Journal of Operational Research_ , 284(1):67–74, 2020.
  * Christodoulou et al. [2015] S. E. Christodoulou, A. Michaelidou-Kamenou, and G. Ellinas.  Heuristic methods for resource leveling problems.  In _Handbook on Project Management and Scheduling Vol. 1_ , pages 389–407. Springer, 2015.
  * Coffman and Graham [1971/1972] E. Coffman, Jr. and R. Graham.  Optimal scheduling for two-processor systems.  _Acta Informat._ , 1:200–213, 1971/1972.
  * Demeulemeester [1995] E. Demeulemeester.  Minimizing resource availability costs in time-limited project networks.  _Management Science_ , 41(10):1590–1598, 1995\.
  * Drótos and Kis [2011] M. Drótos and T. Kis.  Resource leveling in a machine environment.  _European Journal of Operational Research_ , 212(1):12–21, 2011.
  * Du et al. [1991] J. Du, J.-T. Leung, and G. Young.  Scheduling chain-structured tasks to minimize makespan and mean flow time.  _Inform. and Comput._ , 92(2):219–236, 1991.
  * Easa [1989] S. M. Easa.  Resource leveling in construction by optimization.  _Journal of construction engineering and management_ , 115(2):302–316, 1989.
  * Fujii et al. [1969] M. Fujii, T. Kasami, and K. Ninomiya.  Optimal sequencing of two equivalent processors.  _SIAM Journal on Applied Mathematics_ , 17(4):784–789, 1969.
  * Garey and Johnson [1978] M. Garey and D. Johnson.  Strong NP-completeness results: motivation, examples, and implications.  _J. Assoc. Comput. Mach._ , 25(3):499–508, 1978\.
  * Garey and Johnson [1977] M. R. Garey and D. S. Johnson.  Two-processor scheduling with start-times and deadlines.  _SIAM journal on Computing_ , 6(3):416–426, 1977\.
  * Graham et al. [1979] R. L. Graham, E. L. Lawler, J. K. Lenstra, and A. R. Kan.  Optimization and approximation in deterministic sequencing and scheduling: a survey.  In _Annals of discrete mathematics_ , volume 5, pages 287–326. Elsevier, 1979.
  * Györgyi and Kis [2020] P. Györgyi and T. Kis.  A common approximation framework for early work, late work, and resource leveling problems.  _European Journal of Operational Research_ , 286(1):129–137, 2020.
  * Hartmann and Briskorn [2022] S. Hartmann and D. Briskorn.  An updated survey of variants and extensions of the resource-constrained project scheduling problem.  _European Journal of operational research_ , 297(1):1–14, 2022.
  * Hu [1961] T. C. Hu.  Parallel sequencing and assembly line problems.  _Operations research_ , 9(6):841–848, 1961.
  * Lenstra et al. [1977] J. Lenstra, A. Rinnooy Kan, and P. Brucker.  Complexity of machine scheduling problems.  _Ann. of Discrete Math._ , 1:343–362, 1977.
  * Li and Dong [2018] H. Li and X. Dong.  Multi-mode resource leveling in projects with mode-dependent generalized precedence relations.  _Expert Systems with Applications_ , 97:193–204, 2018.
  * Li et al. [2018] H. Li, L. Xiong, Y. Liu, and H. Li.  An effective genetic algorithm for the resource levelling problem with generalised precedence relations.  _International Journal of Production Research_ , 56(5):2054–2075, 2018.
  * Micali and Vazirani [1980] S. Micali and V. V. Vazirani.  An ${O}(\sqrt{|V|}·|{E}|)$ algorithm for finding maximum matching in general graphs.  In _21st Annual Symposium on Foundations of Computer Science (FOCS 1980)_ , pages 17–27. IEEE, 1980.
  * Neumann and Zimmermann [1999] K. Neumann and J. Zimmermann.  Resource levelling for projects with schedule-dependent time windows.  _European Journal of Operational Research_ , 117(3):591–605, 1999.
  * Ponz-Tienda et al. [2017a] J. L. Ponz-Tienda, A. Salcedo-Bernal, and E. Pellicer.  A parallel branch and bound algorithm for the resource leveling problem with minimal lags.  _Computer-Aided Civil and Infrastructure Engineering_ , 32(6):474–498, 2017a.
  * Ponz-Tienda et al. [2017b] J. L. Ponz-Tienda, A. Salcedo-Bernal, E. Pellicer, and J. Benlloch-Marco.  Improved adaptive harmony search algorithm for the resource leveling problem with minimal lags.  _Automation in Construction_ , 77:82–92, 2017b.
  * Qiao and Li [2018] J. Qiao and Y. Li.  Resource leveling using normalized entropy and relative entropy.  _Automation in Construction_ , 87:263–272, 2018.
  * Rieck and Zimmermann [2015] J. Rieck and J. Zimmermann.  Exact methods for resource leveling problems.  In _Handbook on Project Management and Scheduling Vol. 1_ , pages 361–387. Springer, 2015.
  * Rieck et al. [2012] J. Rieck, J. Zimmermann, and T. Gather.  Mixed-integer linear programming for resource leveling problems.  _European Journal of Operational Research_ , 221(1):27–37, 2012.
  * Rodrigues and Yamashita [2015] S. B. Rodrigues and D. S. Yamashita.  Exact methods for the resource availability cost problem.  In _Handbook on Project Management and Scheduling Vol. 1_ , pages 319–338. Springer, 2015.
  * Sterna [2011] M. Sterna.  A survey of scheduling problems with late work criteria.  _Omega_ , 39(2):120–129, 2011.
  * Sterna and Czerniachowska [2017] M. Sterna and K. Czerniachowska.  Polynomial time approximation scheme for two parallel machines scheduling with a common due date to maximize early work.  _Journal of Optimization Theory and Applications_ , 174:927–944, 2017.
  * Ullman [1975] J. Ullman.  NP-complete scheduling problems.  _J. Comput. System Sci._ , 10:384–393, 1975.
  * Van Peteghem and Vanhoucke [2013] V. Van Peteghem and M. Vanhoucke.  An artificial immune system algorithm for the resource availability cost problem.  _Flexible services and manufacturing journal_ , 25(1):122–144, 2013.
  * Verbeeck et al. [2017] C. Verbeeck, V. Van Peteghem, M. Vanhoucke, P. Vansteenwegen, and E.-H. Aghezzaf.  A metaheuristic solution approach for the time-constrained project scheduling problem.  _OR spectrum_ , 39(2):353–371, 2017.
  * Woodworth and Willie [1975] B. M. Woodworth and C. J. Willie.  A heuristic algorithm for resource leveling in multi-project, multi-resource scheduling.  _Decision Sciences_ , 6(3):525–540, 1975.
  * Zhu et al. [2017] X. Zhu, R. Ruiz, S. Li, and X. Li.  An effective heuristic for project scheduling with resource availability cost.  _European journal of operational research_ , 257(3):746–762, 2017.