# Comparison of three classical lower bounds for the Parallel Machines Scheduling Problem

Jacques Carlier, Eric Pinson, Abderrahim Sahli, Antoine Jouglet

► To cite this version:

Jacques Carlier, Eric Pinson, Abderrahim Sahli, Antoine Jouglet. Comparison of three classical lower bounds for the Parallel Machines Scheduling Problem. RAIRO - Operations Research, 2025, 59 (3), pp.1475-1500. 10.1051/ro/2025043. hal-05464783

HAL Id: hal-05464783

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

Submitted on 19 Jan 2026

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 CC BY 4.0 - Attribution - International License
# COMPARISON OF THREE CLASSICAL LOWER BOUNDS FOR THE PARALLEL MACHINES SCHEDULING PROBLEM

JACQUES CARLIER<fnref n="1" />, ERIC PINSON<fnref n="2" />, ABDERRAHIM SAHLI<fnref n="3" />,* D AND ANTOINE JOUGLET<fnref n="1" />

**Abstract.** This paper compares three classical lower bounds for the Parallel Machines Scheduling Problem (PMSP). The first lower bound considered is the makespan of Jackson's Pseudo Preemptive Schedule (JPPS). The second is the preemptive bound, which is obtained by relaxing the non-preemption constraint, and the third is based on Energetic Reasoning (ER). To compare these three bounds, we first provide a rigorous mathematical characterization. Specifically, we introduce a mathematical definition of the ER-derived lower bound as the smallest value of the trial makespan that results in a successful ER feasibility test. This definition relies on the fundamental concepts of critical intervals and specific operations that we called crossing operations, for which we give some theoretical properties. We establish an *Energy theorem*, which provides an analytical formulation of the energetic lower bound. In an extension of the JPPS and ER lower bounds, we give an analytical formulation of the preemptive bound. From the analytical characterization of these three bounds, we attempt to analyze their relative performances. In particular, we find that the ER lower bound differs from JPPS because on some machines at least two operations must be scheduled for ER. The preemptive bound differs from JPPS because idle periods may be required in an optimal preemptive schedule. Interestingly, these three characterizations are quite similar, and so can provide insight into the ways in which the bounds differ. Our results can be directly extended to the cumulative scheduling problem, and we report some experimental experiments that compare these bounds and confirm the theoretical results stated above.

**Mathematics Subject Classification.** 90B35, 05C85, 05C21.

Received July 16, 2024. Accepted April 8, 2025.

## 1. INTRODUCTION

The job-shop scheduling problem is an emblematic disjunctive problem in the scheduling literature. The job-shop involves non-preemptive operations that are subject to precedence constraints. Multiple dedicated machines are available, and each operation requires a specific machine for its execution, meaning that there will be disjunctions between operations requiring the same machine. The objective is to minimize the makespan,

<footnote>*Keywords*. Scheduling, cumulative resource, energetic reasoning, lower bound.</footnote>

<footnote n="1">¹ Sorbonne universités, Université de Technologie de Compiégne, CNRS, Laboratoire Heudiasyc UMR 7253, CS 60 319, 60 203 Compiégne, France.</footnote>

<footnote n="2">² Université Bretagne Loire, Université Catholique de l'Ouest, LARIS EA 7315, Angers, France.</footnote>

<footnote n="3">³ Univ Gustave Eiffel, ESIEE Paris, COSYS-GRETTIA, F-77454 Marne-la-Vallée, France.</footnote>

<footnote>*Corresponding author: abderrahim.sahli@esiee.fr</footnote>
which is the total time taken for all operations to be completed. To address the job-shop problem, it is common practice to decompose it into one-machine sequencing problems. The aim in the one-machine sequencing problem is to sequence *n* non-preemptive operations such as to minimize makespan. Each operation is characterized by a release date $r_i$, a processing time $p_i$, and a tail $q_i$. The release date $r_i$, also known as the head, represents the longest path value in the job-shop precedence graph between an imaginary starting operation and operation *i*. Symmetrically, $p_i + q_i$ corresponds to the longest path value between operation *i* and an imaginary ending operation. Let us recall the properties of the Jackson Preemptive Schedule (JPS), which is an optimal solution for the preemptive version of the one-machine sequencing problem [6]. In JPS the makespan is given by $max_{J \subseteq I} h(J)$, where $h(J) = \min_{j \in J} r_j + \sum_{j \in J} p_j + \min_{j \in J} q_j$ represents a subset bound. The bound for disjunctions is expressed as $\min(r_i + p_i + q_i, r_j + p_j + q_j)$ for any pair $(i, j)$ of operations [5].

The emblematic cumulative problem in the scheduling literature is the Resource Constrained Project Scheduling Problem (RCPSP). This problem involves scheduling non-preemptive operations such as to minimize the makespan, taking into account the constant yet limited availability of resources that these non-preemptive operations require. The standard method for solving RCPSP, whether exactly or approximately, involves decomposing it into as many cumulative scheduling problems (CuSP) as there are resources available. These CuSPs are interconnected by precedence constraints among operations, which are defined by release dates and tails, just as in the disjunctive case.

Most exact and approximate solution methods are therefore based on bounds and heads and tails adjustments for the CuSP. Let us recall that an instance of the Cumulative Scheduling Problem consists of (1) one single resource with a given capacity and (2) a set of operations, each of which is characterized by a processing time, a release date, a tail and a resource capacity requirement. The problem is to assign to each operation a starting time such that all timing constraints are satisfied, the capacity *m* of the resource is never exceeded, and the makespan (total duration) is minimized. The Parallel Machines Scheduling Problem (PMSP) is the particular case of the CuSP where each operation requires exactly one unit of the resource during execution. In this paper we revisit three classical bounds for the PMSP. Note that by using the three-field notation system proposed in [19], the PMSP can be represented as $Pm/r_i, q_i/C_{max}$.

The flow-based preemptive bound for the PMSP was proposed by Horn [22] and improved by Labetoulle et al. [23]. Another classical but constructive bound for the PMSP is based on Jackson's Pseudo Preemptive Schedule (JPPS). This bound is effective in practice, but it is theoretically dominated by the preemptive bound. However, the preemptive bound is heavily penalized by its cubic time complexity, while the JPPS bound can be computed in $O(n \log n + nm \log m)$ time [8]. Moreover, JPPS entails the design of heads and tails adjustments with a quadratic time complexity [7].

The most famous lower bound is based on so-called Energetic Reasoning (ER) [15]. It can be seen as a destructive bound in which, for a trial value of the makespan $C_{max}$, tails are replaced by deadlines. Given a time interval $[\alpha, \delta]$, energetic reasoning means computing the mandatory part of the operations that must be processed in any feasible schedule between time instants $\alpha$ and $\delta$. A bisection on the values of $C_{max}$ enables to compute the ER lower bound, which corresponds to the minimal value of the trial makespan leading to a positive feasibility test.

Until recently, heads and tails adjustments linked to energetic reasoning required a cubic time complexity algorithm, and an important question that Baptiste, Le Pape and Nuijten asked in their book [2] was whether this complexity could be improved. In another recent paper [10] we showed that it could, putting forward a quadratic time complexity algorithm for the same purpose. It should also be noted that Bonifas [4], Ouellet and Quimper [24], Tesch [27, 28], were simultaneously proposing interesting alternative approaches yielding $O(n^2 \log n)$ time algorithms for computing these adjustments. We refer to Hidri et al. [21] which introduce a completely new vision of Energetic Reasoning that explores new perspectives using a job partition.

The aim of this paper is to characterize mathematically three lower bounds for the PMSP, namely JPPS bound, the preemptive bound and the energetic bound. Previous experimental works have highlighted that they are very close in practice [17], but no dominance relations have been established, especially in order to discriminate the preemptive bound from ER lower bound [8]. So, two motivations are at the origin of this work.
The first one is to understand their structural differences and why they are so close. The second one is to design tools to forge new efficient algorithms for Energetic Reasoning, which appears to be the more powerful method but remains a costly solution. Thus, the paper focuses on mathematical characterizations of Energetic Reasoning. Crossing operations play a central role in ER, since for “too small” trial value of $C_{max}$, their energy requirement matches the interval slacks ($\delta - \alpha$) that may lead to an unfeasibility test. We prove that the energetic bound may result in some cases from an adjustment of the trial makespan $C_{max}$ ensuring that at any time instant $t$, there are at most $m$ crossing operations, and denoted $LB_2$. Otherwise, if it is strictly larger, and denoted $LB_3$, it corresponds to a non-empty time interval associated with a non-empty subset of operations for which the total energy matches the resource availability. We term this interval a critical interval and provide a formal characterization, and we state an Energy Theorem providing an analytical formulation of this bound. In the extension of JPPS and ER lower bounds, we state an analytical formulation of the preemptive bound, for which some necessary idle periods are identified to facilitate the comparison with the other bounds.

The organization of this paper is as follows. In Section 2, we introduce the PMSP and the CuSP, together with their underlying relations. In Section 3, we report lower bounds proposed in the last decades for the PMSP, focusing essentially on those mentioned above. In Section 4, we introduce crossing operations and explain how to compute a lower bound involving these operations. In Section 5, we describe the constructive energetic lower bound $LB_3$ based on the notion of critical interval. In Section 6, we state some properties relating to these critical intervals, and we establish the Energy Theorem, allowing an analytical characterization of the constructive ER lower bound. In Section 7, we propose a formal characterization of the preemptive bound. In Section 8, we compare the different bounds described in the preceding sections. Finally, Section 9 presents our conclusions and some prospects for future research.

## 2. THE CUSP AND THE PMSP

### 2.1. The CuSP optimization

The aim of the CuSP is to schedule without preemption a set $I$ of $n$ independent operations on a single resource composed of $m$ identical machines. Each operation $i$ has a release date $r_i$, a processing time $p_i$, a tail $q_i$, and a resource consumption $c_i$, i.e., operation $i$ needs to mobilize $c_i$ machines simultaneously. The aim is to find a schedule minimizing the makespan $C_{max}$. With $C_i$ denoting the completion time of operation $i$ in this schedule, we have: $C_{max} = \max_{i \in I}(C_i + q_i)$. Note that $r_i, q_i$ and $c_i$ are assumed to be rational. Thus, $C_{max}$ can take rational values as indicated in [12]. Therefore, we can assume that all these values are integers by multiplying them by the least common multiple of their denominators.

### 2.2. The CuSP Decision

In the CuSP Decision, a trial value of $C_{max}$ is given, and the tail corresponding to each operation $i$ is replaced by a deadline $d_i = C_{max} - q_i$. The aim is to find a schedule such that (1) each operation $i$ is processed within the time window $[r_i, d_i]$, and (2) at any time $t$ the sum of resource requirements for operations processed at $t$ is smaller than or equal to the availability $m$ of the resource.

### 2.3. Parallel Machines Scheduling Problem

The PMSP is simply a particular case of the CuSP for which each operation requires a single machine during its execution, i.e., $c_i = 1$, ($i \in I$). Several alternative lower bounds have been proposed for this central scheduling problem, including techniques based on bin packing, network flows and linear programming [10, 19, 17, 24]. But notice that this paper is devoted to the three lower bounds mentioned before.

Any instance of a CuSP can be reduced to a PMSP instance by splitting each operation $i$ with a resource requirement $c_i$ into $c_i$ operations, each requiring exactly one machine (and adding synchronization constraints on operation pieces, but this aspect has no repercussion on our algorithms). One obvious drawback of this way of proceeding is that the related algorithmic complexities theoretically increase by a factor that depends on $m$.
Nevertheless, these complexities are not affected in most cases, when computing lower bounds, even it seems to be rather counterintuitive. This is in particular the case for two literature checkers: the $O(n^2)$ algorithm of Baptiste et al., and the $O(n \log^2 n)$ algorithm of Ouellet and Quimper. It relies on the fact that ER does not take into account the integrity of the resource requirements $c_i$. So, an operation $i$ can be split into two operations: the first is processed at the beginning of the interval, the second one at the end of the interval. For this reason, and for the sake of simplicity as well as clarity, the developments outlined in the following sections focus mainly on the particular case PMSP.

## 3. LOWER BOUNDS FOR THE PMSP

Here we recall some lower bounds that have been proposed for the PMSP over the last decades. Note that our aim is not to provide a comprehensive survey on these bounds, but mainly to focus on some of the bounds that we shall then use below in this paper. For a more detailed state-of-the-art, the reader is referred to the paper by Haouari and Gharbi [17].

### 3.1. A brief literature review of lower bounds

An initial very simple lower bound, which can be computed in $O(n)$ time, is given by:

$$LB_0 = \max_{j \in I} (r_j + p_j + q_j).$$

Let $J \subseteq I = \{1, 2, \dots, n\}$ denote a subset of operations for an instance of PMSP. From some enhancements proposed by Carlier in 1984 the following may then be derived:

$$LB_1(J) = \frac{1}{m}(r_{i_1} + r_{i_2} + \dots + r_{i_m}) + \frac{1}{m}\sum_{j \in J} p_j + \frac{1}{m}(q_{j_1} + q_{j_2} + \dots + q_{j_m})$$

where $i_1, i_2, \dots, i_m$ (resp. $j_1, j_2, \dots, j_m$) denote the $m$ first operations in $J$ rearranged in an ascending order of heads (resp. tails).

Clearly, the subset bound $LB_1(J)$ can be computed in $O(n \log n)$ time. Vandelelde [29] proposed some adjusted versions of these bounds. Dell'Amico and Martello [13] designed (in 1995) Bin Packing based bounds that are computed in $O(n^2 \log UB)$ time, where UB denotes an upper bound of the optimal makespan. Some improvements to these bounds were proposed (in 2002) by Gharbi and Haouari [17]. There have been numerous other works, among which we might mention operation subset bounds, machine subset bounds or operation machine subset bounds derived from previous bounds by applying some lifting procedures. We refer the reader to [17] for more details. More “sophisticated” and efficient lower bounds have been proposed, and we recall the basic underlying principles for three of these below.

### 3.2. The preemptive bound

This destructive lower bound, denoted as LBP, was first proposed by Horn [22] and improved by Labetoulle et al. [23]. Let $(r_i, p_i, q_i)_{i \in I}$ be an instance of PMSP. As pointed out in Section 2, given a trial value of $C_{max}$, any operation $i$ has a corresponding deadline $d_i = C_{max} - q_i$. Sorting the release dates and deadlines by increasing order, we get $K \le 2n$ distinct values $u_1 < u_2 < \dots < u_K$ from which we form the $K-1$ time intervals $T_k = [u_k, u_{k+1}]$ with amplitude $l_k = u_{k+1} - u_k$. We then build the graph $G(C_{max}) = (X, U)$ with $X = \{s, p\} \cup \{1, 2, \dots, n\} \cup \{T_1, T_2, \dots, T_{K-1}\}$. An arc connects the source $s$ to each node corresponding to an operation $i$ with a capacity upper bound equal to $p_i$, and each node corresponding to a time interval $T_k$ to the sink $p$ with a capacity upper bound equal to $m \times l_k$. Moreover, an arc connects an operation node $i$ to an interval node $T_k$ if operation $i$ can be processed within the time interval $T_k$, i.e., $T_k \subseteq [r_i, d_i]$. Its corresponding capacity upper bound is equal to $\min\{p_i, l_k\}$ (see Fig. 1).

Notice that formally, the interval nodes $T_k$, the associated amplitudes $l_k$ and arcs connecting nodes $T_k$ to certain operation nodes depend the trial makespan $C_{max}$. For a seek of readability, we refer to $G(C_{max})$ as the
<figure><img src="image_2.png" /><figcaption>FIGURE 1. The associated network.</figcaption></figure>

graph implicitly built on the basis of the trial makespan $C_{max}$. Clearly, a preemptive schedule for the trial value of $C_{max}$ exists if and only if we can find a flow of value $\sum_{i \in \{1, 2, ..., n\}} p_i$ from $s$ to $p$ in $G$. A bisection on the values of $C_{max}$ enables the optimal preemptive bound to be determined in $O(n^3(\log n + \log p_{max}))$ time, where $p_{max}$ is the greatest processing time over the set of operations [23]. No analytic characterization has yet been proposed for this efficient bound, whose major drawback is nevertheless a rather penalizing time complexity. We propose such a characterization in Section 8.

### 3.3. Jackson's pseudo preemptive schedule bound

Here we introduce the JPPS-based lower bound, denoted by LBJ. As in a preemptive schedule, in a pseudo preemptive schedule, the preemption of any available operation is also allowed, but we assume that a processor can be shared by a group of operations, and that an operation can be processed on more than one processor at a time. So, the number of processors assigned to an available operation $i$ at time $t$, denoted by $\alpha_i(t)$, is not necessarily an integer. To build JPPS, we use a list algorithm whose priority dispatching rule is the complete tail $c_i(t) = q_i + a_i(t)$ where $a_i(t)$ is the remaining processing time of job $i$ at the current time $t$. So, in contrast to the one machine case (priority $q_i$), the priority attached to an available operation does not remain fixed throughout, but depends on its residual duration. The only restriction is that at any time $t$, we must have $a_i(t) \ge p_i - (t - r_i)$ for any operation $i$. An operation is said to be partially available if $a_i(t) = p_i - (t - r_i)$: such an operation can only be scheduled at a rate $\alpha_i(t) \le 1$. It is said to be totally available if $a_i(t) > p_i - (t - r_i)$: such an operation can be processed at a rate $\alpha_i(t) \le m$. JPPS first schedules the non in-process (i.e., not currently processed) operations with maximal complete tail at a maximal rate consistent with their status (partially or totally available), and is therefore composed of consecutive schedule blocks during which the subset of in-process operations and the associated rates are invariant, a schedule block $B$ being partitioned into a set of partially available operations $P$ and a set of totally available operations $T$. A schedule block starting at time $t$ is completed at time $t+\theta$, referred to as decision time, and associated with some event which leads to modifications on its structure. In such a block, operations in $T$ are scheduled at the same rate $\alpha_T$ and those in $P$ are processed at rate 1. The operations in the block are processed in $[t, t+\theta]$. Figure 2 gives a small example of how this algorithm can be applied. The JPPS schedule is composed of six blocks. At time 0, the only available operation is operation 1, which is partially available. Therefore, it is processed at a rate of 1, and the first block consists solely of operation 1 with an idle machine. At time 1, both operations 1 and 2 are partially available. They are processed at a rate of 1 each, so the second block includes operations 1 and 2. At time 2, operation 3 becomes partially available but has a lower priority compared to operations 1 and 2. Consequently, the second block still consists of operations 1 and 2. The third block then includes operation 3, which is processed at a rate of 2. The fourth block consists of operations 3, 4, and 5. During this block, operation 3 is processed at a rate of 1, while operations 4 and 5 are processed at a rate of $\frac{1}{2}$ each. The fifth block includes operations 4 and 5, both processed at a rate of 1. The makespan of the schedule is 7, calculated as $r_2 + p_2 + q_2$.

Carlier and Pinson [8] provided an analytical expression of the JPPS makespan, denoted as $C_{max}^{JPPS}$, as follows.

**Lemma 3.1 ([8]).**

$$LBJ = C_{max}^{JPPS} = \max\{LB_0, LB_1\}$$
<figure><img src="image_3.png" /><figcaption>FIGURE 2. Jackson's pseudo preemptive schedule.</figcaption></figure>

where

$$LB_1 = \max_{J \subseteq I, |J| \ge m} LB_1(J).$$

Note that $LB_0$ corresponds to the case where a single operation $i$ is the only operation processed on its respective machine (i.e., it is a one-operation subset bound). Moreover, the lower bound $LB_1$ is defined as

$$LB_1 = \max_{J \subseteq I, |J| \ge m} LB_1(J),$$

where $LB_1(J)$ is a subset bound associated with the subset $J$. JPPS a schedule made of successive blocks associated with the subsets $J$, as explained in [8]. Carlier and Pinson also proved that this lower bound can be computed in $O(n \log n + nm \log m)$ time, and that adjustments of heads and tails for the PMSP can be performed using JPPS in $O(n^2)$ time. For more details, the reader is referred to their papers [8,9].

### 3.4. Energetic reasoning

We now set the makespan $C_{max}$ and replace tails by deadlines by setting: $d_i(C_{max}) = C_{max} - q_i$. Energetic Reasoning (ER) was first introduced by Erschler and Lopez [15] to solve the cumulative scheduling problems (CuSP Decision). The energetic approach, which has been formalized and assessed both from a theoretical and an experimental standpoint by Baptiste et al. [1], seeks to develop feasibility tests and time-bound adjustments, either to ensure that a given schedule is infeasible or to derive some necessary conditions that any feasible schedule must satisfy. Given a time interval $[\alpha, \delta]$, energetic reasoning means computing the mandatory part of the operations that must be processed in any feasible schedule between time instants $\alpha$ and $\delta$. The minimal energy required by operation $i$ on $[\alpha, \delta]$, termed $W_i(C_{max}, \alpha, \delta)$, is obtained from positions of $i$ that overlap as little as possible with the interval. To compute $W_i(C_{max}, \alpha, \delta)$, operation $i$ is either left-shifted or right-shifted on its time window $[r_i, d_i(C_{max})]$, i.e., operation $i$ either starts at $r_i$ or finishes at $d_i$. We can therefore state that $W_i(C_{max}, \alpha, \delta) = \min(p_i^+(\alpha), p_i^-(\delta), \delta - \alpha)$, where $p_i^+(\alpha)$ denotes the maximal time span during which operation $i$ overlaps time interval $[\alpha, +\infty[$ if it is left-shifted, and $p_i^-(\delta)$ the maximal time span during which operation $i$ overlaps time interval $]-\infty, \delta]$ if it is right-shifted. Consequently, we have:

$$p_i^+(\alpha) = \max(0, \min(p_i, r_i + p_i - \alpha))$$

$$p_i^-(\delta) = \max(0, \min(p_i, \delta - d_i(C_{max}) + p_i)).$$
<figure><img src="image_4.png" /><figcaption>FIGURE 3. Intersection energy.</figcaption></figure>

The total energy over the time interval $[\alpha, \delta]$ is thus defined by $W(C_{\max}, \alpha, \delta) = \sum_{i=1}^{n} W_i(C_{\max}, \alpha, \delta)$. The energy balance $EB(C_{\max}, \alpha, \delta) = m(\delta - \alpha) - W(C_{\max}, \alpha, \delta)$ is the difference between the maximum energy available over $[\alpha, \delta]$ and $W(C_{\max}, \alpha, \delta)$ (Fig. 3).

**Proposition 3.2** (ER Checker [1]). *Given an instance of PMSP, if the condition*

$$ \forall \alpha, \delta \in \mathbf{N}^{+}, \alpha < \delta \quad \mathrm{EB}(C_{\max}, \alpha, \delta) \geq 0 $$

is violated then the considered instance is infeasible.

In [1], Baptiste et al. proposed a very nice $O(n^2)$ time algorithm to verify the corresponding feasibility test, from which they also derived an $O(n^3)$ time algorithm for computing heads and tails adjustments. They showed that $O(n^2)$ intervals $[\alpha, \delta]$ need to be considered. Let us define the sets:

$$ O_1(i) = \{r_i, r_i + p_i, d_i - p_i\}, \quad \forall i \in I, $$

$$ O_2(i) = \{r_i + p_i, d_i - p_i, d_i\}, \quad \forall i \in I $$

$$ O_t(i) = \{r_i + d_i - t\}, \quad \forall i \in I $$

$$ \text{and } O_1 = \bigcup_{i \in I} O_1(i), \quad O_2 = \bigcup_{i \in I} O_2(i), \quad O_t = \bigcup_{i \in I} O_t(i). $$

They proved that:

**Proposition 3.3** ([1]). *To be sure that the condition in Proposition 3.2 holds, it is sufficient to check intervals $[\alpha, \delta]$ in $\Omega = \Omega_A \cup \Omega_B \cup \Omega_C$ with:*

$$ \Omega_A = \{[\alpha, \delta] | \alpha \in O_1, \delta \in O_2, \alpha < \delta\} $$

$$ \Omega_B = \{[\alpha, \delta] | \alpha \in O_1, \delta \in O_\alpha, \alpha < \delta\} $$

$$ \Omega_C = \{[\alpha, \delta] | \delta \in O_2, \alpha \in O_\delta, \alpha < \delta\}. $$

The number of such intervals is equal to $15n^2$. Derien and Petit [14] showed that only $2n^2$ intervals need to be considered. In this paper, we characterize the corresponding intervals. A better algorithm, of complexity $O(n \log^2 n)$, was proposed recently by Ouellet and Quimper [24] which consider all potential intervals, but some are only considered implicitly by exploiting the Monge property of the intervals of interest. The result of that checker is always the same as the algorithms of Baptiste and Derrien. The most efficient checker to date was recently introduced by Carlier, Sahli, Jouglet, and Pinson, exhibiting a complexity of $O(\alpha(n)n \log n)$ [11]. Notice that a bisection on the values of $C_{\max}$ enables to compute the destructive ER lower bound, denoted as LBE. This lower bound corresponds to the minimal value of the trial makespan $\tilde{C}_{\max}$ leading to a positive feasibility test, i.e., $\forall 0 \le \alpha \le \delta \le \tilde{C}_{\max}$, $W(\tilde{C}_{\max}, \alpha, \delta) \le m(\delta - \alpha)$. The resulting time complexity is $O(n^2 \log C_{\max})$ for the algorithm by Baptiste et al. [1]. We recently introduced an algorithm for computing ER lower bound with a time complexity of $O(n^2)$ [12]. In Sections 4 and 5, we propose an analytical characterization of this bound. Given a makespan $C_{\max}$, each time interval $[\alpha, \delta]$ can be linked to a triplet $(\alpha, \beta, \gamma)$ such that $\delta = \alpha + \beta = C_{\max} - \gamma$ (see Fig. 4).
<figure><img src="image_5.png" /><figcaption>FIGURE 4. The triplet $(\alpha, \beta, \gamma)$.</figcaption></figure>

<table><caption>TABLE 1. Summary of lower bounds and their Computational complexities.</caption><thead><tr><td>Bound</td><td>Description</td><td>Complexity</td></tr></thead><tbody><tr><td>LB<sub>0</sub></td><td>The Critical Path Bound (See Sect. 3.1)</td><td>O(n)</td></tr><tr><td>LB<sub>1</sub></td><td>The Jackson Set Bound (See Sect. 3.3)</td><td>O(n log n + nm log m)</td></tr><tr><td>LB<sub>2</sub></td><td>The Cumulative Constraint Bound (See Sect. 4.3)</td><td>O(n log n)</td></tr><tr><td>LB<sub>3</sub></td><td>The Energetic Set Bound (See Sect. 5)</td><td>O(α(n)n log n)</td></tr><tr><td>LB<sub>4</sub></td><td>The Preemptive Set Bound (See Sect. 7)</td><td>O(n<sup>3</sup> log n)</td></tr><tr><td>LB<sub>J</sub></td><td>The Jackson Bound LBJ = max(LB<sub>0</sub>, LB<sub>1</sub>) (See Sect. 3.3)</td><td>O(n log n + nm log m)</td></tr><tr><td>LBE</td><td>The Energetic Bound LBE = max(LB<sub>0</sub>, LB<sub>2</sub>, LB<sub>3</sub>) (See Sect. 6)</td><td>O(α(n)n log n)</td></tr><tr><td>LBP</td><td>The Preemptive Bound LBP = max(LB<sub>0</sub>, LB<sub>4</sub>) (See Sect. 7)</td><td>O(n<sup>3</sup> log n)</td></tr></tbody></table>

Carlier et al. [12] define the energetic bound LBE as the smallest value of $C_{max}$ for which the classical ER checker does not detect infeasibility. $LB_2$ is the smallest value of $C_{max}$ for which there is no time instant with $m + 1$ crossing operations. It can be computed in $O(n \log n)$ and generalizes the bounds on disjunctions in the cumulative case. If infeasibility is detected by the checker for $C_{max} = LB_2$, then $LBE = LB_3$. In this case, LBE corresponds to a critical interval that is saturated.

### 3.5. Notation

The following table summarizes the notation used for various lower bounds discussed in this paper. Each bound is associated with its computational complexity and a reference to the corresponding section (Tab. 1).

## 4. LOWER BOUNDS BASED ON CROSSING OPERATIONS

Let $(r_i, p_i, q_i)_{i \in I}$ be an instance of PMSP. As pointed out in Section 2, given a trial value of $C_{max}$, we can associate with operation *i* a deadline $d_i(C_{max}) = C_{max} - q_i$ and we get a decision problem.

### 4.1. Crossing operations

Crossing operations play a central role in ER, since for “too small” trial value of $C_{max}$, their energy requirement matches the interval slacks $(\delta - \alpha)$ that may lead to an unfeasibility test.

**Definition 4.1.** Given a makespan $C_{max}$ and a time instant $t \le C_{max}$, an operation *i* is called a crossing operation at time *t* if $d_i - p_i \le t < r_i + p_i$ (see Fig. 5).

**Proposition 4.2.** Given a makespan $C_{max}$ and a time instant $t \le C_{max}$, each crossing operation *i* satisfies:

$$r_i + 2p_i + q_i > C_{max}.$$

*Proof.* A crossing operation *i* satisfies:

$$\begin{cases} r_i + p_i > t \\ d_i - p_i \le t \end{cases} \Rightarrow r_i + 2p_i - d_i > 0.$$
<figure><img src="image_6.png" /><figcaption>FIGURE 5. Crossing operation at time t.</figcaption></figure>

But $d_i = C_{\max} - q_i$, so $r_i + 2p_i + q_i > C_{\max}$.

Consequently, if $i$ is a crossing operation, it satisfies: $r_i + 2p_i + q_i > C_{\max}$.

We can deduce that if $\max_{i \in I}(r_i + 2p_i + q_i) \le C_{\max}$, then there is no crossing operation.

Below, we denote the makespan associated with an optimal non-preemptive schedule as $C_{\max}^*$. We can state:

**Lemma 4.3.** If $\max_{i \in I}(r_i + 2p_i + q_i) < C_{\max}^*$, then there exists an optimal schedule for which at least two operations are processed per machine.

*Proof.* We consider an optimal non-preemptive schedule having a minimal number of critical operations. Let us assume (w.l.g.) that machine 1 processes a single operation, say $i$, and that machine 2 processes at least two operations where $j$ (resp. $k$) is the first (resp. last) one. Suppose that machine 2 is critical (i.e., it matches the optimal makespan: $C_{\max}^* = r_j + p_j + \dots + p_k + q_k$). Moreover, suppose that operation $i$ is processed as soon as possible (i.e., it is left-shifted). Let us consider the following two cases:

**Case 1:** $r_j + p_j > r_i + p_i$. Transferring operation $k$ from machine 2 to machine 1 leads to a new schedule in which neither machine 1 nor machine 2 are critical, and we get a contradiction.

**Case 2:** $r_j + p_j \le r_i + p_i$. If we shift right operation $i$ of $p_i$ time units, we can transfer operation $j$ from machine 2 to machine 1 (operation $j$ precedes operation $i$).

This is possible because $\max_{i \in I}(r_i + 2p_i + q_i) < C_{\max}^*$. So, $i$ is not a crossing operation. Once more, this leads to a new schedule in which neither machine 1 nor machine 2 is critical, and we get a contradiction. Consequently, at least two operations are processed per machine.

**Corollary 4.4.** If $\max_{i \in I}(r_i + 2p_i + q_i) < C_{\max}^*$, then $n = |I| \ge 2m$, and there is no crossing operation for any time $t \le C_{\max}^*$.

*Proof.* It follows simply from Proposition 4.2 and Lemma 4.3.

## 4.2. A first lower bound for $C_{\max}^*$

Moreover, we can state:

**Theorem 4.5.** If $\max_{i \in I}(r_i + 2p_i + q_i) < C_{\max}^*$, then $I$ contains at least $2m$ operations, there is no crossing operation at any time $t \le C_{\max}^*$, and the quantity

$$LB'_1 = \frac{1}{m}(r_{i_1} + r_{i_2} + \dots + r_{i_m}) + \frac{1}{m}\sum_{j \in I} p_j + \frac{1}{m}(q_{j_1} + q_{j_2} + \dots + q_{j_m})$$

is a lower bound of $C_{\max}^*$, where $\{i_1, i_2, \dots, i_m\}$ and $\{j_1, j_2, \dots, j_m\}$ denote disjoint subsets of $I$ minimizing $LB'_1$.
Proof. Let us assume that $\max_{i \in I}(r_i + 2p_i + q_i) < C_{\max}^*$. From Corollary 4.4 we have $n = |I| \ge 2m$, and there is no crossing operation at any time. Moreover, from Lemma 4.3, there exists an optimal non-preemptive schedule for which at least two operations are processed per machine. Let $i_k$ (resp. $j_k$) denote the first (resp. last) operation processed on machine $k$, ($k \in \{1, 2, \dots, m\}$). Moreover, let $R_k$ (resp. $Q_k$) denote the first (resp. last) idle period on machine $k$, ($k \in \{1, 2, \dots, m\}$). Clearly, we have $(r_{i_1} + r_{i_2} + \dots + r_{i_m}) \le \sum_{k \in \{1, \dots, m\}} R_k$ and $(q_{j_1} + q_{j_2} + \dots + q_{j_m}) \le \sum_{k \in \{1, \dots, m\}} Q_k$. So, by comparing and taking into account the other idle periods of the non-preemptive schedule, we get the result.

Furthermore, by construction, the resulting subsets of operations $\{i_1, i_2, \dots, i_m\}$ and $\{j_1, j_2, \dots, j_m\}$ are disjoint, and we have:

$$LB_1' = \frac{1}{m}(r_{i_1} + r_{i_2} + \dots + r_{i_m}) + \frac{1}{m}\sum_{j \in I} p_j + \frac{1}{m}(q_{j_1} + q_{j_2} + \dots + q_{j_m}).$$

□

### 4.3. Discarding the crossing operations: an alternative lower bound $LB_2$

Adjusting the trial makespan to keep at most $m$ crossing operations leads to an alternative lower bound. Let us recall that given a makespan $C_{\max}$ and a time instant $t$, a crossing operation satisfies $d_i - p_i \le t < r_i + p_i$. Clearly, such an operation is always running in the interval $[t - 1, t]$ for any non-preemptive schedule. An immediate consequence is that if there are strictly more than $m$ crossing operations at time $t$, then no non-preemptive schedule with a makespan less than or equal to $C_{\max}$ can exist. This leads to an alternative lower bound $LB_2$ associated with a non-preemptive schedule. This bound results from an adjustment of the trial makespan $C_{\max}$ ensuring that at any time instant $t$, there are at most $m$ crossing operations, which can easily be tested by checking that there is no interval $[r_i + p_i - 1, r_i + p_i]$ in which more than $m$ operations are processed. This technique is well known, it is called *time tabling*.

An $O(n \log n)$ algorithm for counting the crossing operations was proposed in Beldiceanu and Carlsson [3].

**Example 4.6.** Consider the instance where $m = 2$ machines and involving $n = 3$ operations, each operation having a processing time equal to 1, a release date equal to 0, and a tail equal to 0. We have: $LB_2 = 2$.

**Proposition 4.7.** For $C_{\max} = LB_2$, there exists a time point $t$ such that:

- There are $k_1$ operations $i$ satisfying $r_i + p_i = t$ and $d_i - p_i = t$;

- There are $k_2$ operations spanning the interval $[t - \epsilon, t + \epsilon]$ ($\epsilon$ sufficiently small), where $(m+1-k_2) \le k_1 \le (2m-k_2)$;

where $(m+1-k_2) \le k_1 \le (2m-k_2)$. The value of $LB_2$ is in the form of $r_i + 2p_i + q_i$.

If $C_{\max}$ is strictly less than $LB_2$, we have $k_1 + k_2$ operations spanning at time $t$, while if $C_{\max}$ is greater than or equal to $LB_2$, we have fewer than $m$ operations spanning at time $t$.

From Proposition 4.2, for a trial makespan $C_{\max}$, a crossing operation satisfies $r_i + 2p_i + q_i > C_{\max}$. The idea underlying the definition of $LB_2$ is to adjust the makespan in such a way that at most $m-1$ operations may be considered crossing operations. Assume that the operations are sorted in increasing order of $(r_i + 2p_i + q_i)$-values, which gives $v$ distinct quantities $r_{l_1} + 2p_{l_1} + q_{l_1} < r_{l_2} + 2p_{l_2} + q_{l_2} < \dots < r_{l_v} + 2p_{l_v} + q_{l_v}$ with $n_k$ operations matching the value $(r_{l_k} + 2p_{l_k} + q_{l_k})$. From this it follows that (Fig. 6):

$$LB_2 = r_{l_s} + 2p_{l_s} + q_{l_s} \quad \text{with} \quad s = \min\left\{k \mid \sum_{i=1}^{k} n_i > m\right\}.$$
<figure><img src="image_7.png" /><figcaption>FIGURE 6. LB₂ lower bound.</figcaption></figure>

## 5. THE ENERGETIC CONSTRUCTIVE BOUND LB₃ BASED ON A CRITICAL INTERVAL

Let us suppose that for $C_{max} = LB_2$, the checker determines that there is no feasible solution, in other words that there is no interval with a strictly negative energy balance. In this case there will be a new lower bound $LB_3$, defined as the smallest value strictly greater than $LB_2$ for which all intervals have a positive energy balance. $LB_3$ therefore represents the mathematical lower bound for the set of $C_{max}$ values where the checker does not detect intervals with strictly negative energy balances (i.e., $LBE = LB_3$). The purpose of Lemma 5.1 below is to define the notion of a critical interval.

**Lemma 5.1.** For $C_{max}$ equal to $LB_3$, there exists at least one interval of strictly positive length that has a zero energy balance. We term this interval a critical interval.

*Proof.* The idea underlying the proof of Lemma 5.1 is as follows: for $C_{max}$ equal to $LB_3$, assuming that all intervals $[\alpha, \delta]$ of strictly positive length ($\alpha < \delta$) have a strictly positive energy balance (i.e., $EB(C_{max}, \alpha, \delta) > 0$), if an adjustment is made such that $C'_{max} = C_{max} - \epsilon$ with an arbitrarily small $\epsilon > 0$, then we obtain a collection of intervals whose energy balance remains positive, which implies a contradiction with the definition of $LB_3$.

Proposition 3.3 (see Sect. 3.4) states that it is sufficient to check the feasibility condition on the intervals of the set $\Omega = \Omega_A \cup \Omega_B \cup \Omega_C$. In the sequel we denote this set as $\Omega(C_{max})$, since the bounds of some intervals $[\alpha, \delta]$ of the corresponding 15 types may depend on the due dates $d_i(C_{max}) = C_{max} - q_i$ ($i \in I$). We first prove that if we make the adjustment $C'_{max} = C_{max} - \epsilon$ with arbitrarily small $\epsilon > 0$, then all intervals $[\alpha', \delta'] \in \Omega(C'_{max})$ may be derived from the intervals $[\alpha, \delta] \in \Omega(C_{max})$. Updating the due dates such that $d_i(C'_{max}) = d_i(C_{max}) - \epsilon$ clearly leads to a new collection of intervals $[\alpha', \delta'] \in \{[\alpha - \epsilon, \delta], [\alpha, \delta - \epsilon], [\alpha - \epsilon, \delta - \epsilon], [\alpha, \delta]\}$ belonging to $\Omega(C'_{max})$, the validity condition $\alpha' < \delta'$ being satisfied since by definition each interval $[\alpha, \delta] \in \Omega(C_{max})$ satisfies $\alpha < \delta$. Where an interval $[\alpha, \delta]$ does not meet this condition, we have $\alpha \ge \delta$, and it is straightforward to show that if $\alpha > \delta$, the adjustment $C'_{max} = C_{max} - \epsilon$ cannot lead to an interval $[\alpha', \delta']$ satisfying $\alpha' < \delta'$ and thus belonging to $\Omega(C'_{max})$. There nevertheless remains the particular case where $\alpha = \delta$, giving rise to an interval of the form $[\alpha', \delta'] = [\alpha - \epsilon, \alpha]$, which satisfies $\alpha' < \delta'$ and therefore belongs to $\Omega(C'_{max})$. Consequently, all intervals $[\alpha', \delta'] \in \Omega(C'_{max})$ may be derived from $[\alpha, \delta] \in \Omega(C_{max})$ by updating the instantiation of the bounds $\alpha$ and $\delta$ and including the particular case mentioned.
Now, let us suppose that we make the adjustment $C'_{\max} = C_{\max} - \epsilon$ with arbitrarily small $\epsilon > 0$, and let us also suppose that $C'_{\max} > \text{LB}_2$ and that each interval in $\Omega(C_{\max})$ satisfies the condition $\text{EB}(C_{\max}, \alpha, \delta) > 0$. Consider an interval $[\alpha', \delta'] \in \{[\alpha - \epsilon, \delta], [\alpha, \delta - \epsilon], [\alpha - \epsilon, \delta - \epsilon], [\alpha, \delta]\}$. Concerning an update $\alpha' = \alpha - \epsilon$, the operations $K^+ = \{i \in I | r_i < \alpha$ and $p_i^+(\alpha) < p_i^-(\delta)\}$ will clearly be impacted in terms of energy demand, the energy demand for each of these operations increasing by $\epsilon$, while the energy availability over this interval increases by $m\epsilon$. Symmetrically, concerning an update $\delta' = \delta - \epsilon$, the operations $K^- = \{i \in I | d_i - p_i < \delta$ and $p_i^+(\alpha) > p_i^-(\delta)\}$ will be impacted, their energy demand decreasing by $\epsilon$, but balanced by the adjustment $d_i(C'_{\max}) = d_i(C_{\max}) - \epsilon$ ($i \in I$), while the energy availability over this interval decreases by $m\epsilon$. Where $\delta' = \delta$, there is no longer any offset, and the energy balance must take account of the reduction in energy demand for the operations $K^-$. We may therefore state the following regarding the energy balance:

$$- [\alpha', \delta'] = [\alpha, \delta - \epsilon]:$$

$$\text{EB}(C'_{\max}, \alpha', \delta') = \text{EB}(C_{\max}, \alpha, \delta) - m\epsilon \geq 0.$$

$$- [\alpha', \delta'] = [\alpha - \epsilon, \delta]:$$

$$\text{EB}(C'_{\max}, \alpha', \delta') = \text{EB}(C_{\max}, \alpha, \delta) + m\epsilon - (|K^-| + |K^+|)\epsilon \geq 0.$$

$$- [\alpha', \delta'] = [\alpha - \epsilon, \delta - \epsilon]:$$

$$\text{EB}(C'_{\max}, \alpha', \delta') = \text{EB}(C_{\max}, \alpha, \delta) + m\epsilon - m\epsilon - |K^+|\epsilon \geq 0.$$

$$- [\alpha', \delta'] = [\alpha, \delta]:$$

$$\text{EB}(C'_{\max}, \alpha', \delta') = \text{EB}(C_{\max}, \alpha, \delta) - |K^-|\epsilon \geq 0$$

since $\epsilon$ is taken to be strictly positive but arbitrarily small. Once again we need to take account of the particular case where $\alpha = \delta$, which gives an interval of the form $[\alpha', \delta'] = [\alpha - \epsilon, \alpha]$. For such an interval we clearly have $\text{EB}(C'_{\max}, \alpha', \delta') \geq 0$ since, given that $C'_{\max} = C_{\max} - \epsilon > \text{LB}_2$, there will be at most $m$ crossing operations at time $t = \alpha$ (see Prop. 4.7). In conclusion, for any interval $[\alpha', \delta'] \in \Omega(C'_{\max})$ we have $\text{EB}(C'_{\max}, \alpha', \delta') \geq 0$, which contradicts the definition of $\text{LB}_3$ as the smallest value strictly greater than $\text{LB}_2$ for which all intervals have a positive energy balance. Consequently, there exists at least one interval $[\alpha, \delta]$ satisfying $\alpha < \delta$ and $\text{EB}(C_{\max}, \alpha, \delta) = 0$. $\square$

# 6. THE ENERGY THEOREM

In this section we analyze the ER lower bound LBE. The value of $C_{\max}$ is set to LBE, and if we assume that there exists a critical interval, then LBE will be equal to $\text{LB}_3$. We present an Energy Theorem that generalizes the subset-bound. First, we introduce some definitions before establishing properties associated with critical intervals of maximal length. Next, we consider three separate cases that differ with respect to the presence or absence of crossing operations and switching operations: these cases might be labelled a simple case, an intermediate case, and a general case. Definitions 6.1–6.4 are not used outside this Section 6. We include them solely for the purpose of proving the Energy Theorem. Informally stated, a switching operation is a non-crossing operation for which the expression of energy demand changes when $C_{\max}$ increases. An overflowing operation is an operation which has a part processed outside the interval.

## 6.1. Definitions

Let us denote by $J(\alpha, \delta)$ the subset of operations with a strictly positive energy in the time interval $[\alpha, \delta]$.

**Definition 6.1.** Given a makespan $C_{\max}$ and an interval $[\alpha, \delta]$, an operation $i$ is termed a crossing operation of the interval $[\alpha, \delta]$ if we have $W_i(\alpha, \delta) = \delta - \alpha$.
An operation where this condition is not satisfied will sometimes be referred to as a *non-crossing* operation. Hereafter, where there is no ambiguity, we will not explicitly specify the interval $[\alpha, \delta]$ in relation to a crossing operation. Clearly, a crossing operation satisfies:

$$ (CO) \begin{cases} r_i \le \alpha, d_i \ge \delta \\ r_i + p_i \ge \delta \\ d_i - p_i \le \alpha. \end{cases} $$

**Definition 6.2.** An non-crossing operation $i \in J(\alpha, \delta)$ is termed a *switching operation* where $p^+(\alpha) = p^-(\delta) < (\delta - \alpha)$.

**Definition 6.3.** – A non-crossing operation $i \in J(\alpha, \delta)$ is a *before-overflowing operation* if it satisfies the following conditions:

$$ p_i^+(\alpha) \le p_i^-(\delta) \quad \text{and} \quad r_i \le \alpha. $$

The set encompassing all before-overflowing operations is denoted as $\mathcal{B}$.

– A non-crossing operation $i \in J(\alpha, \delta)$ is termed a *strict before-overflowing operation* if it satisfies the following conditions:

$$ p_i^+(\alpha) \le p_i^-(\delta) \quad \text{and} \quad r_i < \alpha. $$

The set of all strict before-overflowing operations is denoted as $\mathcal{BS}$.

– A non-crossing operation $i \in J(\alpha, \delta)$ is termed an *equal before-overflowing operation* if it satisfies the following conditions:

$$ p_i^+(\alpha) \le p_i^-(\delta) \quad \text{and} \quad r_i = \alpha. $$

The set of all equal before-overflowing operations is denoted as $\mathcal{BE}$.

Note that the set $\mathcal{B}$ of before-overflowing operations is equal to the union of $\mathcal{BS}$ and $\mathcal{BE}$. Symmetrically, we have the following definitions:

**Definition 6.4.** – A non-crossing operation $i \in J(\alpha, \delta)$ is termed an *after-overflowing operation* if it satisfies the following conditions:

$$ p_i^+(\alpha) \ge p_i^-(\delta) \quad \text{and} \quad d_i \ge \delta. $$

The set encompassing all after-overflowing operations is denoted as $\mathcal{A}$.

– A non-crossing operation $i \in J(\alpha, \delta)$ is termed a *strict after-overflowing operation* if it satisfies the following conditions:

$$ p_i^+(\alpha) \ge p_i^-(\delta) \quad \text{and} \quad d_i > \delta. $$

The set of all strict after-overflowing operations is denoted as $\mathcal{AS}$.

– A non-crossing operation $i \in J(\alpha, \delta)$ is termed an *equal after-overflowing operation* if it satisfies the following conditions:

$$ p_i^+(\alpha) \ge p_i^-(\delta) \quad \text{and} \quad d_i = \delta. $$

The set of all equal after-overflowing operations is denoted as $\mathcal{AE}$.

Any switching operation is both a before-overflowing and an after-overflowing operation, and belongs to both $\mathcal{B}$ and $\mathcal{A}$. The set of switching operations corresponds to the intersection of $\mathcal{B}$ and $\mathcal{A}$.
## 6.2. Properties of critical intervals of maximal length

We now establish some properties relating to critical intervals that will enable us to prove the Energy Theorem. In the following propositions, the value of $C_{\max}$ is set to LBE = $LB_3$. Recall that $LB_3$ is the minimal trial makespan for which the ER feasibility test is positive, and that it will have at least one corresponding critical interval $[\alpha, \delta]$ satisfying: $\delta - \alpha > 0$.

Consider a critical interval $[\alpha^*, \delta^*]$ having the greatest possible length, that is to say a length equal to the upper bound of the lengths of critical intervals. Note that our remarks here are not limited to the families $\Omega_A$, $\Omega_B$, and $\Omega_C$. A critical interval of maximum length can be trivially obtained if the values are integers. This interval has a non-zero length but a zero net energy balance. Here we make an assumption that there are no crossing operations, but in scenarios where crossing operations are present the properties that we establish can be extended by replacing $m$ with $m - m'$, where $m'$ denotes the number of crossing operations.

**Proposition 6.5.** *The cardinality of* $B \cup A$ *is greater than or equal to* $2m$.

*Proof.* We will demonstrate by contradiction that the number of operations belonging to $B \cup A$ is at least $2m$. Suppose that $B \cup A$ contains at most $2m - 1$ operations. A simultaneous tightening of $\epsilon$ to the right of $\alpha^*$ and to the left of $\delta^*$ (with $\epsilon$ chosen to be sufficiently small) would result in a reduction of energy supply by $(2m \cdot \epsilon)$, while the energy demand would decrease by at most $((2m - 1) \cdot \epsilon)$. As a consequence, the interval would have a strictly negative energy balance, which represents a contradiction, given that by hypothesis the critical interval $[\alpha^*, \delta^*]$ has a zero energy balance. $\square$

**Proposition 6.6.** *The cardinality of* $B$ (*resp. A*) *is greater than or equal to* $m$.

*Proof.* We will demonstrate by contradiction that the number of operations belonging to $B$ is at least $m$. Suppose that $B$ contains at most $m - 1$ operations. Tightening $\epsilon$ to the right of the point $\alpha^*$ would result in a reduction of energy supply by $(m \cdot \epsilon)$, while the energy demand would decrease by at most $((m - 1) \cdot \epsilon)$. As a consequence, we would end up with a strictly negative energy balance interval, leading to a contradiction. Symmetrically, we can prove that $A$ contains at least $m$ operations. $\square$

**Proposition 6.7.** *The number of non-switching operations in* $BS$ (*i.e., the operations belonging to* $BS \setminus AS$) *is at most* $m - 1$.

*The number of non-switching operations in* $AS$ (*i.e., the operations belonging to* $AS \setminus BS$) *is at most* $m - 1$.

*Proof.* If this were not the case, a contradiction becomes apparent if we imagine extending the interval to the left (resp. right) for $BS \setminus AS$ (resp. $AS \setminus BS$). $\square$

**Proposition 6.8.** *The cardinality of* $BS \cup AS$ *is at most* $2m - 1$.

*Proof.* If this were not the case, there would be a contradiction with the critical interval in question being of the greatest possible length. The contradiction becomes apparent if we imagine extending the interval symmetrically. $\square$

## 6.3. The Energy Theorem

Given the above proposition, we can now state the Energy Theorem, which provides an analytical characterization of the constructive lower bound LBE linked to Energetic Reasoning. Our formulation requires both heads and tails (see Sect. 3.4, Fig. 4).
<figure><img src="image_8.png" /><figcaption>FIGURE 7. Energy Theorem – the case where crossing and switching operations are absent.</figcaption></figure>

### 6.3.1. Case without crossing and switching operations

We will start by considering the scenario where the critical interval $[\alpha^*, \delta^*]$ of greatest possible length involves no crossing operations and no switching operations. The proof can be extended to cover other scenarios.

**Lemma 6.9.** If there are no switching or crossing operations, we may select two disjoint subsets of operations, denoted as $J_B = \{i_1, \dots, i_m\}$ and $J_A = \{j_1, \dots, j_m\}$. This selection ensures the satisfaction of the energy equality:

$$ \mathrm{LB}_3 = \frac{1}{m} \left[ (r_{i_1} + r_{i_2} + \dots + r_{i_m}) + \sum_{i \in J(\alpha^*, \delta^*)} p_i + (q_{j_1} + q_{j_2} + \dots + q_{j_m}) \right]. $$

In addition, there will exist an operation $i \in J_B$ such that $\alpha^* = r_i$ and another operation $j \in J_A$ such that $\delta^* = d_j$.

*Proof.* We can select the operations $i_1, \dots, i_m$ as follows:

- Select all the operations belonging to $\mathcal{BS}$.

- Complete the selection with operations from $\mathcal{BE}$.

Given the absence of switching operations, the two subsets of operations, $\mathcal{BS}$ and $\mathcal{AS}$, are disjoint, implying that $\mathcal{BS} = \mathcal{BS} \setminus \mathcal{AS}$. From Proposition 6.7 we have $|\mathcal{BS}| = |\mathcal{BS} \setminus \mathcal{AS}| \le m - 1$. Consequently, at least one operation $i \in J_B$ is selected from $\mathcal{BE}$, satisfying $\alpha^* = r_i$. Note that $\mathcal{BE}$ cannot be empty and that it contains enough operations to define the $m$ operations of $J_B$, since we have from Proposition 6.5 that the cardinality of $\mathcal{B}$ ($\mathcal{B} = \mathcal{BS} \cup \mathcal{BE}$) is at least $m$. Similarly, since there are no switching operations, the two subsets of operations, $\mathcal{B}$ and $\mathcal{A}$, are also disjoint. Hence, $J_A = \{j_1, \dots, j_m\}$ may be constructed in a similar way, ensuring the selection of at least one operation $j$ from $\mathcal{AE}$. The critical interval $[\alpha^*, \delta^*] = [r_i, d_j]$ thus belongs to $\Omega_A$. $\square$

Figure 7 presents an instance of the $P_m/r_i, q_i/C_{\max}$ problem consisting of 6 operations and 2 machines. This serves as an illustration of the Energy Theorem in a scenario involving no switching or crossing operations. In our example, $\mathrm{LB}_3$ is equal to 9. The selected operations are $J_B = \{1, 3\}$ and $J_A = \{2, 4\}$. The validity of the following expression can be trivially established:

$$ \mathrm{LB}_3 = \frac{1}{2} \left[ (r_1 + r_3) + \sum_{i=1}^{6} p_i + (q_2 + q_4) \right] = 9. $$

In this specific instance, the critical interval is $[2, 7] = [r_3, d_4]$, belonging to $\Omega_A$.
### 6.3.2. Case without crossing operations

Any switching operation belongs to both $\mathcal{B}$ and $\mathcal{A}$. It may thus be assigned to either $J_B$ or $J_A$, as we will see below.

**Lemma 6.10.** If switching operations are present and there are no crossing operations, the Energy Theorem remains valid. Furthermore, the critical interval $[\alpha^*, \delta^*]$ falls within $\Omega_A$, $\Omega_B$, or $\Omega_C$.

*Proof.* To define the two sets $J_A$ and $J_B$, three constraints must be satisfied. The first constraint requires $J_B$ to contain exactly $m$ operations from $\mathcal{B}$. The second constraint requires $J_A$ to contain exactly $m$ operations from $\mathcal{A}$. The third constraint requires all mandatory operations to be placed in exactly one set. These mandatory operations include the operations in $\mathcal{BS}$ and $\mathcal{AS}$ and may involve switching operations. We will at first disregard the third constraint, since this constraint is easily addressed via a post-processing step, as we explain at the end of the proof.

Let us place all non-switching operations from $\mathcal{AS}$ in $J_A$, and all non-switching operations from $\mathcal{BS}$ in $J_B$. Next, we add some non-switching operations from $\mathcal{AE}$ to $J_A$. If there are enough operations, then $J_A$ will contain exactly $m$ operations from $\mathcal{A} \setminus \mathcal{B}$, in which case the proof is concluded, since from Proposition 6.6 we have that $\mathcal{B}$ contains at least $m$ operations that can be placed in $J_B$. If, on the other hand, the number of non-switching operations in $\mathcal{AE}$ is not sufficient to give us $m$ operations in $J_A$, then we add enough switching operations from set $\mathcal{A}$ to $J_A$ to achieve this. This is feasible because $\mathcal{A}$ contains at least $m$ operations, and the operations already assigned to $J_B$ are in $\mathcal{B} \setminus \mathcal{A}$. Here, too, the proof is concluded, as a consequence of Proposition 6.5, which states that the cardinality of the union of $\mathcal{A}$ and $\mathcal{B}$ is larger than $2m$, and hence we are able to place $m$ operations from $\mathcal{B}$ in $J_B$. The post-processing step involves replacing some operations from $\mathcal{AE}$ and $\mathcal{BE}$ with mandatory switching operations. These procedural steps ensure that the two disjoint subsets $J_B$ and $J_A$ can be defined. Let us consider the following cases:

- $J_B \cap \mathcal{BE} = \emptyset$ and $J_A \cap \mathcal{AE} = \emptyset$: This case is impossible; if it were the case, then $J_B \cup J_A \subset \mathcal{AS} \cup \mathcal{BS}$, from which it would follow that $|\mathcal{AS} \cup \mathcal{BS}| \ge 2m$, contradicting Proposition 6.8.

- $J_B \cap \mathcal{BE} \neq \emptyset$ and $J_A \cap \mathcal{AE} = \emptyset$: At least one operation $i \in J_B$ belongs to $\mathcal{BE}$ and at least one operation $j \in J_A$ is a switching operation belonging to $\mathcal{BS} \cap \mathcal{AS}$. Consequently, operation $i$ satisfies $r_i = \alpha^*$, and operation $j$ satisfies $\delta^* + \alpha^* = r_j + d_j$. This implies that the critical interval $[\alpha^*, \delta^*]$ is defined as $[r_i, r_j + d_j - r_i]$ and belongs to $\Omega_B$.

- $J_B \cap \mathcal{BE} = \emptyset$ and $J_A \cap \mathcal{AE} \neq \emptyset$: At least one operation $j \in J_A$ belongs to $\mathcal{AE}$ and at least one operation $i \in J_B$ is a switching operation belonging to $\mathcal{BS} \cap \mathcal{AS}$. The critical interval $[\alpha^*, \delta^*] = [r_i + d_i - d_j, d_j]$ thus belongs to $\Omega_C$.

- $J_B \cap \mathcal{BE} \neq \emptyset$ and $J_A \cap \mathcal{AE} \neq \emptyset$: At least one operation $i \in J_B$ belongs to $\mathcal{BE}$ and at least one operation $j \in J_A$ belongs to $\mathcal{AE}$. The critical interval $[\alpha^*, \delta^*]$ is thus defined as $[r_i, d_j]$ and falls within $\Omega_A$.

□

Figure 8 provides an example illustrating the Energy Theorem in a scenario where at least one switching operation exists, and there are no crossing operations. In this example, there are three instances of the $P_m/r_i$, $q_i/C_{max}$ problem, each consisting of 6 operations and 2 machines. In instance (a), operation 4 is a switching operation belonging to $\mathcal{BE} \cap \mathcal{AE}$ and is selected to define $J_A$. The critical interval is $[r_3, d_4] = [2, 7]$, falling within $\Omega_A$. In instance (b), operation 4 is a switching operation belonging to $\mathcal{BS} \cap \mathcal{AS}$ and is chosen to define $J_A$. The critical interval is $[r_3, r_4 + d_4 - r_3] = [2, 7]$, belonging to $\Omega_B$. In instance (c), operation 3 is a switching operation in $\mathcal{BS} \cap \mathcal{AS}$ and is chosen to define $J_B$. The critical interval is $[r_3 + d_3 - d_4, d_4] = [2, 7]$, falling within $\Omega_C$.

### 6.3.3. General case

**Theorem 6.11** (The Energy Theorem). If there are $m'$ crossing operations ($m' < m$), we can select two disjoint subsets of operations, denoted as $J_B = \{i_1, \dots, i_{\tilde{m}}\}$ and $J_A = \{j_1, \dots, j_{\tilde{m}}\}$. This selection ensures that
<figure><img src="image_9.png" /><figcaption>FIGURE 8. Energy Theorem – Case without crossing operations.</figcaption></figure>

the following energy equality holds:

$$ \mathrm{LB}_3 = \frac{1}{\tilde{m}} \left[ (r_{i_1} + r_{i_2} + \dots + r_{i_{\tilde{m}}}) + \sum_{i \in J^*(\alpha^*, \delta^*)} p_i + (q_{j_1} + q_{j_2} + \dots + q_{j_{\tilde{m}}}) \right] $$

where $\tilde{m} = m - m'$ and $J^*(\alpha^*, \delta^*)$ is the set of non-crossing operations belonging to $J(\alpha^*, \delta^*)$.

In addition, the critical interval $[\alpha^*, \delta^*]$ belongs to $\Omega_A$, $\Omega_B$, or $\Omega_C$.

*Proof.* In the scenario where there are $m'$ crossing operations (where $m'$ cannot be equal to $m$), the switching operations may be related to either $\alpha = d_i - p_i$ or $\delta = r_i + p_i$. The proof can be trivially generalized, since the $m'$ crossing operations will occupy $m'$ machines. However, there is now a difference, since we may have $\alpha = d_i - p_i$ or $\delta = r_j + p_j$. For a given $\alpha$ equal to $r_i$ or $d_i - p_i$, we may have $\delta$ equal to $d_j$, $r_j + p_j$, or $r_j + d_j - \alpha$. Similarly, for a given $\delta$ in the form of $d_j$ or $r_j + p_j$, we may have $\alpha$ equal to $r_i$, $d_i - p_i$, or $r_i + d_i - \delta$ (Fig. 9). $\square$

## 7. AN ANALYTICAL CHARACTERIZATION FOR THE PREEMPTIVE BOUND

The aim of this section is to state, in the extension of JPPS and ER lower bounds, an analytical characterization of the preemptive bound. As pointed out in Section 3.2, given a trial value of $C_{max}$, we can associate with each operation $i$ a deadline $d_i(C_{max}) = C_{max} - q_i$. Sorting the release dates and deadlines by increasing order, we get $K \le 2n$ distinct values $u_1 < u_2 < \dots < u_K$ from which we form the $K-1$ time intervals $T_k = [u_k, u_{k+1}]$ with amplitude $l_k = u_{k+1} - u_k$. We make the assumption that $d_i(C_{max}) \ge r_i$ and $C_{max} \ge \mathrm{LB}_2$, since otherwise there would be no preemptive schedules. For convenience, we invert the network described in Section 3.2 as follows.
<figure><img src="image_10.png" /><figcaption>FIGURE 9. Energy Theorem – General case.</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>FIGURE 10. The inverted network.</figcaption></figure>

We build the graph $G(C_{\max}) = [X, U]$ with $X = \{s, p\} \cup \{1, 2, \dots, n\} \cup \{T_1, T_2, \dots, T_{K-1}\}$. An arc connects the source $s$ to each node associated with a time interval $T_k$ with a capacity upper bound equal to $m \times l_k$, and each node associated with an operation $i$ is connected to the sink $p$ with a capacity upper bound equal to $p_i$. An arc connects an interval node $T_k$ to an operation node $i$ if operation $i$ can be processed within the time interval $T_k$, i.e., $T_k \subseteq [r_i, d_i]$. Its corresponding capacity upper bound is equal to $\min(p_i, l_k)$ (see Fig. 10). Notice that formally, the interval nodes $T_k$, the associated amplitudes $l_k$ and arcs connecting nodes $T_k$ to certain operation nodes depend on the trial makespan $C_{\max}$. For a seek of readability, we refer to $G(C_{\max})$ as the graph implicitly built on the basis of the trial makespan $C_{\max}$.

Clearly, a preemptive schedule for the trial value of $C_{\max}$ exists if we can find a flow of value $\sum_{i \in I} p_i$ from $s$ to $p$ in $G$ and conversely. Let LBP denote the optimal makespan associated with a preemptive schedule (of course a lower bound to the makespan associated with any optimal non preemptive schedule). Obviously, each arc $(i, p)$ is saturated in this kind of optimal solution, since the operation $i$ is entirely processed. Using the
Ford-Fulkerson marking procedure [16], we first establish the following results (recall that in this algorithm, and for the current flow, a node is said to be marked if there exists a non-saturated path between $s$ and $i$ in the residual network associated with $G(\text{LBP})$, an arc being saturated if the associated flow is equal to its capacity upper bound). In the extension of JPPS and ER lower bounds, we state an analytical formulation of the preemptive bound. Its main interest is to better understand the difference of the three lower bounds on the basis of their respective analytical formulations. Let us suppose that $\text{LBE} = \text{LB}_4 > \text{LB}_2$. This indicates that there are no preemptive schedules where the makespan ($C_{\max}$) is equal to $\text{LB}_2$.

**Lemma 7.1.** In an optimal solution to the max flow problem associated with $G(\text{LBP})$, all the interval nodes cannot be marked simultaneously.

*Proof.* Reasoning by reduction ad absurdum, we show that if all the interval nodes are simultaneously marked by Ford-Fulkerson algorithm in an optimal solution to the max flow problem associated with $G(\text{LBP})$, then LBP can be decreased, which contradicts the optimality of the preemptive bound. Let $T_k = [u_k, u_{k+1}]$ be a saturated interval node. If $T_k$ is marked, then there exists a path connecting the source $s$ to the node $T_k$ in the residual network. By extending this path with the arc $(T_k, s)$, we get a circuit with a residual capacity denoted as $\epsilon_k > 0$ in the residual network. Adjusting the flow of $\epsilon < \epsilon_k$ units along this circuit clearly has the effect of reducing the flow crossing the node $T_k$ without saturating any other interval nodes, and the interval node $T_k$ is no longer saturated. Let us now consider the collection $\Phi$ of all the interval nodes which are marked in the optimal solution associated with makespan LBP, and let $\eta$ be the cardinality of $\Phi$. By considering a sufficiently small quantity $\epsilon$ (for instance, $\epsilon = \frac{1}{\eta+1} \min_{T_k \in \Phi} \epsilon_k > 0$), and revising the flow of units along all the circuits associated with the nodes belonging to $\Phi$ has the effect of reducing the flow crossing these nodes without saturating any other interval nodes, and all the interval nodes $T_k \in \Phi$ are no longer saturated. Consequently, all the interval nodes $T_k$, ($k \in \{1, \dots, K-1\}$) are no longer saturated and LBP can be decreased (recall that we have $d_i = \text{LBP} - q_i$, ($i \in I$), which contradicts the optimality of the considered preemptive schedule. $\square$

**Lemma 7.2.** In an optimal solution to the max flow problem associated with $G(\text{LBP})$, all the operation nodes ($i \in I$) cannot be marked simultaneously.

*Proof.* First, it will be remarked that in an optimal solution to the max flow problem associated with $G(\text{LBP})$, any arc $(i, p)$ will be saturated, since its capacity upper bound is equal to $p_i$ and the operation $i$ is entirely processed in the preemptive solution. Consequently, the sink $p$ is not marked. Let us now assume that all the operation nodes $i \in I$ are marked. In this case, there exists a path connecting the source $s$ and each operation node $i$ ($i \in I$) in the residual network with a residual capacity that we denote as $\epsilon_i > 0$. Let us consider a sufficiently small quantity $\epsilon$ (for instance $\epsilon = \frac{1}{n} \min_{i \in I} \epsilon_i > 0$). By extending each such path with the arc $(i, p)$ and by adding the return arc $(p, s)$, we can increase the flow by $\epsilon$ units along each circuit involving an operation $i$ ($i \in I$) by adjusting the upper bound capacity associated with arcs $(i, p)$, ($i \in I$), which increases the processing time of each operation by the quantity $\epsilon$, in respect of the upper bound capacities associated with the interval nodes $T_k$, ($k \in K$). Correlatively, we can decrease the load of all the interval nodes $T_k$, ($k \in K$) by a sufficiently small quantity $\epsilon'$ and all these intervals become non-saturated, meaning that once again LBP can be decreased (recall that we have $d_i = \text{LBP} - q_i$, ($i \in I$)), which contradicts the optimality of the considered preemptive schedule. $\square$

Let us now consider the subset $\bar{J}$ of all the operation nodes which are not marked in the optimal solution to the max flow problem associated with $G(\text{LBP})$, and define $\bar{K} \subseteq \{1, 2, \dots, K-1\}$ as the subset of interval node indexes on which at least one unit of an operation in $\bar{J}$ is processed. We state the following result:

**Proposition 7.3.** Any interval node of $T_k$ with $k \in \bar{K}$:

- either is an interval which is saturated by the only operations of $\bar{J}$,

- or is an interval such that all the arcs $(T_k, j)$, ($j \in \bar{J}$) belonging to graph $G(\text{LBP})$ are saturated.
<figure><img src="image_12.png" /><figcaption>FIGURE 11. LBP lower bound.</figcaption></figure>

In the first case, the status of $T_k$ is said to be “saturated”, while in the second case, its status is said to be “blocked”.

*Proof.* Let $k \in \bar{K}$. Of course, $T_k$ may be saturated. Assume that this interval node is not marked in the optimal solution to the max flow problem, and that there exists an operation $j \notin \bar{J}$ which is partially (or totally) processed in $T_k$. In this case, $j$ allows the interval node $T_k$ to be marked in backward, which leads to a contradiction. If now $T_k$ is marked, all the arcs $(T_k, j)$, $(j \in \bar{J})$ are saturated, otherwise $j$ can be marked, which leads to a contradiction with $j \in \bar{J}$. So, to summarize, any interval node $T_k$ with $k \in \bar{K}$ is either an interval which is saturated by the only operations of $\bar{J}$, or an interval such that all the arcs $(T_k, j)$, $(j \in \bar{J})$ belonging to graph $G$ (LBP) are saturated. $\square$

Below we denote as $\text{MH}_k$ (MH stands for Mandatory Hole) the part of the processing capacity of the interval node $T_k$ ($m \times l_k$) that is not used for executing the operations of $\bar{J}$. We have $\text{MH}_k = 0$ if $T_k$ is saturated, and $\text{MH}_k > 0$ if $T_k$ is blocked.

**Theorem 7.4.**

$$ \text{LBP} = \text{LB}_4 = \frac{1}{m} \sum_{j \in \bar{J}_b} r_j + \frac{1}{m} \left\{ \sum_{j \in \bar{J}} p_j + \sum_{k \in \bar{K}} \text{MH}_k \right\} + \frac{1}{m} \sum_{j \in \bar{J}_a} q_j. $$

*Proof.* Let LBP the makespan of an optimal preemptive schedule and $J^*$ a minimal subset of operations with makespan LBP. Let us suppose that LBP is strictly larger than $\max_{i \in I}(r_i + p_i + q_i)$. So there exists at least one saturated interval. $J^*$ is minimal so the saturated intervals and unsaturated intervals are consecutive. Let us denote $\alpha$ as the starting time of the first saturated interval and $\delta$ the completion time of the last saturated interval. Let us denote $i_1, i_2, \dots, i_m$, bridge operations going over $\alpha$, completed by operations processed in the interval $[\alpha, \alpha + 1]$ and $j_1, j_2, \dots, j_m$, bridge operations going over $\delta$, completed by operations processed in the interval $[\delta - 1, \delta]$. The two sets $J_a = \{i_1, i_2, \dots, i_m\}$ and $J_b = \{j_1, j_2, \dots, j_m\}$ are not necessarily disjoint. We have (Fig 11):

$(\delta - \alpha) \times m$ is equal to the sum of partial processing times of operations processed in interval $[\alpha, \delta] + \text{sums of mandatory holes}$, which is equal to the sum of processing times $p_i + (r_{i_1} - \alpha) + (r_{i_2} - \alpha) + \dots + (r_{i_m} - \alpha) + \text{sum of mandatory holes} + (q_{j_1} - \gamma) + (q_{j_2} - \gamma) + \dots + (q_{j_m} - \gamma)$.
<figure><img src="image_13.png" /><figcaption>FIGURE 12. LBJ, LBE and LBP analytical formulations.</figcaption></figure>

Considering the occupations of the interval nodes $T_k$, ($k \in \bar{K}$) by the operations of $\bar{J}$, and taking their respective status into account, we have

$$ \sum_{k \in \bar{K}} l_k = \frac{1}{m} \left\{ \sum_{j \in \bar{J}} p_j + \sum_{k \in \bar{K}} \mathrm{MH}_k \right\}. $$

Thus, we obtain:

$$ \mathrm{LBP} = \frac{1}{m_b} \sum_{j \in \bar{J}_b} r_j + \frac{1}{m} \left\{ \sum_{j \in \bar{J}} p_j + \sum_{k \in \bar{K}} \mathrm{MH}_k \right\} + \frac{1}{m_a} \sum_{j \in \bar{J}_a} q_j. $$

□

## 8. COMPARING THE THREE BOUNDS LBJ, LBE AND LBP

In this section, we aim to compare the three lower bounds in light of their respective analytical formulations, and report some computational experiments rating their relative performances.

### 8.1. A rather strong similarity between the analytical formulations of LBJ, LBE and LBP

Figure 12 summarizes the analytical characterizations stated in the previous sections. For comprehensive formulations, we of course refer to Sections 3.3, 6.3 and 7.
<figure><img src="image_14.png" /><figcaption>FIGURE 13. Superiority of LBE over LBP.</figcaption></figure>

Clearly, a rather strong similarity appears between the mathematical formulations associated with these three lower bounds. Contrariwise, we can highlight the following differences that can partly explain their relative performances:

- Sets $J_B$ and $J_A$ are disjoint for ER while this result does not hold for JPPS. This is due to the fact that apart of the crossing operations, the operations involved in the critical set are implicitly shifted either left or right. In JPPS, based on a list algorithm whose priority dispatching rule is the complete tail, operations may be preempted and appear in both sets $J_B$ and $J_A$. Moreover, and discarding the crossing operations, when there are more than $2 \times m$ operations, there are two different operations on each machine positioned at the beginning and at the end of the critical interval in LBE. Notice that it is connected to the non-preemptive case by the dominance property of Lemma 4.3.

- A structural difference between LBP and LBJ as well as LBE is that idle periods are required in an optimal preemptive schedule (mandatory holes) and are explicitly taken into account in the calculation of LBP.

- Both $LB_3$ and $LB_4$ (subset bounds) rely on the definition of a critical interval $[\alpha, \delta]$. For $LB_3$, its length is exactly equal to the sum of the mandatory parts associated with the operation which have to be processed in the interval divided by the number of machines that are not monopolized by crossing operations which have to occupy exactly the interval.

- From the analytical characterization of the three bounds, it is clear that preemptive and energetic bounds outperform JPPS bounds, although in practice the difference is small when $n$ is large and $m$ small (see for instance the computational experiments reported in [18]). On the other hand, no dominance can be established between LBE and LBP as shown in the following two instances (see Examples 8.1 and 8.2).

**Example 8.1 (LBE dominates LBP).** Let us consider the following instance: $m = 2$ machines, $n = 4$ operations with the parameters given in Figure 13:

In this instance (Fig. 13), the energetic bound is given by $LBE = LB_3 = 7$. The saturated interval is $[1, 5]$. The critical subset consists of operations $\{1, 2, 3, 4\}$ with $i_1 = 1, i_2 = 2; j_1 = 3, j_4 = 4$. Sets $J_A$ and $J_B$ are disjoint, and there are no crossing operations. The preemptive bound is smaller, specifically $LBP = 6 = r_3 + p_3 + q_3$. Here, operation 3 alone determines the preemptive bound.

**Example 8.2 (LBP dominates LBE).** Let us consider the following instance: $m = 2$ machines, $n = 9$ operations with the parameters given in Figure 13:

In this instance (Fig. 14), the energetic bound is $LBE = LB_3 = 6.5$, and the saturated interval is $[0, 6.5]$. The critical subset consists of operations $\{1, 2, 3, 4, 5, 6, 7, 8, 9\}$, with $i_1 = 1, i_2 = 2, j_1 = 7$, and $j_4 = 8$. The sets $J_A$ and $J_B$ are disjoint, and there are no crossing operations. The preemptive bound is larger, equal to $LB_4 = 7$. Notably, operation 9 acts as a bridge.
<table><thead><tr><th></th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th></tr></thead><tbody><tr><th>r<sub>i</sub></th><td>0</td><td>0</td><td>0</td><td>0</td><td>4</td><td>4</td><td>4</td><td>4</td><td>1</td></tr><tr><th>p<sub>i</sub></th><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>5</td></tr><tr><th>q<sub>i</sub></th><td>4</td><td>4</td><td>4</td><td>4</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td></tr></tbody></table>

$m = 2$

<table><tr><td>1</td><td>4</td><td>9</td><td>5</td><td>7</td></tr><tr><td>2</td><td>3</td><td>9</td><td>6</td><td>8</td></tr><tr><td>0</td><td>1</td><td></td><td>5</td><td>6.5</td></tr></table>

Energetic bound $LBE = 6.5$

<table><tr><td>S</td><td>S</td><td>S</td><td>B</td><td>S</td><td>S</td><td>S</td></tr><tr><td>1</td><td>9</td><td>9</td><td>9</td><td>9</td><td>9</td><td>7</td></tr><tr><td>2</td><td>3</td><td>4</td><td></td><td>6</td><td>5</td><td>8</td></tr><tr><td>0</td><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>6</td><td>7</td></tr></table>

Preemptive bound $LBP = 7$

<caption>FIGURE 14. Superiority of LBP over LBE.</caption>

## 8.2. Computational experiments

We have done computational experiments to compare $LB_0$, $LB_2$, LBE, LBJ, and LBP. These lower bounds have been coded in C++ and tested first on instances of CuSP obtained from instances of RCPSP of the PSPLib (J30, J60, J90 and J120). It appears that these data are not interesting because they are not “cumulative” data: in most cases, $LB_0$ which is the critical path bound is nearly the same than LBE and the mean deviation between $LB_0$ and LBE is lower than 2.5%. So, we have also tested these lower bounds on 300 randomly generated instances consisting of scheduling $n = 20, 40, 60, 80$ or 100 operations using $m = 3, 5$ or $7$ resources. The generation process is based on integer uniform distributions and is similar to the one used by Gharbi and Haouari [18]. The instances have been generated in the following way:

- The processing times, heads, and tails are generated between 1 and $n$.

- The resource consumptions $c_i$ are generated between 1 and $[0.8 \times m]$.

- For each combination of $n$ and $m$, 20 instances are generated.

It has been observed by Gharbi and Haouari [17], that this generation process yields very challenging instances. Table 2 displays a summary of the computational results that were obtained on the generated instances. For each lower bound, we provide:

- %Gap: the average deviation from the best lower bound obtained in percent. Specifically, the best lower bound is defined as: $max(LB_0, LB_2, LBE, LBJ, LBP)$.

- %Opt: the percentage of best lower bounds found.

Not surprisingly, the values of LBJ, LBP and LBE are very close. In fact, the difference between them is 0.48%. Moreover, these three bounds dominate $LB_2$ which dominates $LB_0$.

## 9. CONCLUSION

In this paper we have compared three simple classical lower bounds for the $m$ machine parallel problem: Jackson's Pseudo preemptive schedule bound (LBJ), the preemptive bound (LBP), and Energetic Reasoning bound (LBE). They are composed of the conjunctive bound and three different subset bounds (with LBP and LBE also including the cumulative bound). LBJ is dominated by the two other bounds but can be computed
<table><caption>TABLE 2. Results of the bounds on the generated instances.</caption><thead><tr><th rowspan="2">n</th><th rowspan="2">m</th><th colspan="2">LB<sub>0</sub></th><th colspan="2">LBE<sub>2</sub></th><th colspan="2">LBJ</th><th colspan="2">LBE</th><th colspan="2">LBP</th></tr><tr><th>%Opt</th><th>%Gap</th><th>%Opt</th><th>%Gap</th><th>%Opt</th><th>%Gap</th><th>%Opt</th><th>%Gap</th><th>%Opt</th><th>%Gap</th></tr></thead><tbody><tr><td rowspan="3">20</td><td>3</td><td>00.0</td><td>32.26</td><td>00.0</td><td>28.18</td><td>80.0</td><td>0.31</td><td>100.0</td><td>0.00</td><td>80.0</td><td>0.31</td></tr><tr><td>5</td><td>00.0</td><td>26.80</td><td>00.0</td><td>26.20</td><td>95.0</td><td>0.07</td><td>100.0</td><td>0.00</td><td>95.0</td><td>0.07</td></tr><tr><td>7</td><td>00.0</td><td>22.34</td><td>00.0</td><td>22.23</td><td>80.0</td><td>0.34</td><td>100.0</td><td>0.00</td><td>80.0</td><td>0.34</td></tr><tr><td rowspan="3">40</td><td>3</td><td>00.0</td><td>62.31</td><td>01.0</td><td>58.16</td><td>95.0</td><td>0.02</td><td>100.0</td><td>0.00</td><td>95.0</td><td>0.02</td></tr><tr><td>5</td><td>00.0</td><td>58.62</td><td>00.0</td><td>56.33</td><td>90.0</td><td>0.05</td><td>100.0</td><td>0.00</td><td>90.0</td><td>0.05</td></tr><tr><td>7</td><td>00.0</td><td>56.84</td><td>00.0</td><td>55.68</td><td>85.0</td><td>0.09</td><td>100.0</td><td>0.00</td><td>85.0</td><td>0.09</td></tr><tr><td rowspan="3">60</td><td>3</td><td>00.0</td><td>74.49</td><td>00.0</td><td>70.17</td><td>85.0</td><td>0.03</td><td>100.0</td><td>0.00</td><td>85.0</td><td>0.03</td></tr><tr><td>5</td><td>00.0</td><td>70.96</td><td>00.0</td><td>68.94</td><td>90.0</td><td>0.02</td><td>100.0</td><td>0.00</td><td>90.0</td><td>0.02</td></tr><tr><td>7</td><td>00.0</td><td>70.45</td><td>00.0</td><td>69.50</td><td>90.0</td><td>0.02</td><td>100.0</td><td>0.00</td><td>90.0</td><td>0.02</td></tr><tr><td rowspan="3">80</td><td>3</td><td>00.0</td><td>80.87</td><td>00.0</td><td>77.29</td><td>85.0</td><td>0.01</td><td>100.0</td><td>0.00</td><td>85.0</td><td>0.01</td></tr><tr><td>5</td><td>00.0</td><td>78.29</td><td>00.0</td><td>75.86</td><td>95.0</td><td>0.00</td><td>100.0</td><td>0.00</td><td>95.0</td><td>0.00</td></tr><tr><td>7</td><td>00.0</td><td>77.84</td><td>00.0</td><td>76.13</td><td>95.0</td><td>0.01</td><td>100.0</td><td>0.00</td><td>95.0</td><td>0.01</td></tr><tr><td rowspan="3">100</td><td>3</td><td>00.0</td><td>84.00</td><td>00.0</td><td>80.99</td><td>95.0</td><td>0.00</td><td>100.0</td><td>0.00</td><td>95.0</td><td>0.00</td></tr><tr><td>5</td><td>00.0</td><td>82.85</td><td>00.0</td><td>80.52</td><td>100.0</td><td>0.00</td><td>100.0</td><td>0.00</td><td>100.0</td><td>0.00</td></tr><tr><td>7</td><td>00.0</td><td>81.87</td><td>00.0</td><td>80.39</td><td>95.0</td><td>0.00</td><td>100.0</td><td>0.00</td><td>95.0</td><td>0.00</td></tr></tbody></table>

in $O(n \log n)$. But in practice, their difference is marginal as it is confirmed by our computational results. LBP is better than LBJ but interestingly, Theorem 7.4 permits to better understand why. It is also due to idle times which are imposed by the optimal value of makespan, but these idle times seems unlikely. It is confirmed in practice by the paper of Gharbi and Haouari [18]. The analytical characterization stated by the Energy Theorem (Thm. 6.11) helps to elucidate the difference between ER and JPPS. Discarding the crossing operations, it is because when there are more than $2 \times m$ operations, there are two different operations on each machine positioned at the beginning and at the end of the critical interval, and in the Energy Theorem $J_B$ and $J_A$ are disjoint while this result does not hold for JPPS. It is connected to the non-preemptive case by the dominance property of Lemma 4.3. Our results can be immediately extended to the cumulative scheduling problem, by splitting any operation requiring $c_i$ units of a resource into $c_i$ operations, each requiring one unit of the resource. Nevertheless, these complexities are not affected in most cases, when computing lower bounds, even it seems to be rather counterintuitive. This is in particular the case for two literature checkers: the $O(n^2)$ algorithm of Baptiste et al. [1], and the $O(n \log^2 n)$ algorithm of Ouellet and Quimper. It relies on the fact that ER does not take into account the integrity of the resource requirements $c_i$. So, an operation $i$ can be split into two suboperations: the first is processed at the beginning of the interval $[\alpha, \delta]$, the second one at the end of the interval. Our analytical characterization of the energetic bound is also very useful from the analytical point of view. Indeed, it permits us in the prolongation of this work to propose a new checker which is better than the previous ones from the practical and theoretical point of view [11].

## ACKNOWLEDGMENTS

The authors would like to thank Professor Claire Hanen for her useful comments about this paper. We also wish to express our deep gratitude to the two anonymous reviewers for their constructive feedback and insightful suggestions, which have significantly contributed to the improvement of the manuscript.

## DATA AVAILABILITY STATEMENT

No new data/codes were created or analyzed in this study.
REFERENCES

[1] P. Baptiste, C. Le Pape and W. Nuijten, Satisfiability tests and time-bound adjustments for cumulative scheduling problems. *Ann. Oper. Res.* **92** (1999) 305–333.

[2] P. Baptiste, C. Le Pape and W. Nuijten, Constraint-Based Scheduling: Applying Constraint Programming to Scheduling Problems. Vol. 39. Springer Science & Business Media (2001).

[3] N. Beldiceanu and M. Carlsson, A new multi-resource cumulatives constraint with negative heights, in International Conference on Principles and Practice of Constraint Programming. Springer (2002) 63–79.

[4] N. Bonifas, *Geometric and dual approaches to cumulative scheduling*. Theses, Université Paris-Saclay (Dec. 2017).

[5] J. Carlier, Disjonctions dans les ordonnancements. *Revue française d'automatique, informatique, recherche opérationnelle. Recherche opérationnelle* **9** (1975) 83–100.

[6] J. Carlier, The one-machine sequencing problem. *Eur. J. Oper. Res.* **11** (1982) 42–47. Third EURO IV Special Issue.

[7] J. Carlier and E. Pinson, Adjustment of heads and tails for the job-shop problem. *Eur. J. Oper. Res.* **78** (1994) 146–161.

[8] J. Carlier and E. Pinson, Jackson's pseudo preemptive schedule for the $Pm/r_i, p_i/C_{max}$ scheduling problem. *Ann. Oper. Res.* **83** (1998) 41–58.

[9] J. Carlier and E. Pinson, Jackson's pseudo-preemptive schedule and cumulative scheduling problems. *Discrete Appl. Math.* **145** (2004) 80–94.

[10] J. Carlier, E. Pinson, A. Sahli and A. Jouglet, An $O(n^2)$ algorithm for time-bound adjustments for the cumulative scheduling problem. *Eur. J. Oper. Res.* **286** (2020) 468–476.

[11] J. Carlier, A. Sahli, A. Jouglet and E. Pinson, A faster checker of the energetic reasoning for the cumulative scheduling problem. *Int. J. Prod. Res.* **60** (2022) 3419–3434.

[12] J. Carlier, A. Jouglet and A. Sahli, Algorithms to compute the energetic lower bounds of the cumulative scheduling problem. *Ann. Oper. Res.* **337** (2024) 683–713.

[13] M. Dell'Amico and S. Martello, Optimal scheduling of tasks on identical parallel processors. *ORSA J. Comput.* **7** (1995) 191–200.

[14] A. Derrien and T. Petit, A new characterization of relevant intervals for energetic reasoning, in International Conference on Principles and Practice of Constraint Programming, edited by B. O'Sullivan. Springer, Springer International Publishing, Lyon, France (2014) 289–297.

[15] J. Erschler, P. Lopez and C. Thuriot, Raisonnement temporel sous contraintes de ressource et problèmes d'ordonnancement. *Revue d'intelligence artificielle* **5** (1991) 7–32.

[16] L.R. Ford and D.R. Fulkerson, Flows in networks, in *Flows in Networks*. Princeton University Press (1962).

[17] A. Gharbi and M. Haouari, Minimizing makespan on parallel machines subject to release dates and delivery times. *J. Scheduling* **5** (2002) 329–355.

[18] A. Gharbi and M. Haouari, An approximate decomposition algorithm for scheduling on parallel machines with heads and tails. *Comput. Oper. Res.* **34** (2007) 868–883.

[19] R. Graham, E. Lawler, J. Lenstra and A. Kan, Optimization and approximation in deterministic sequencing and scheduling: a survey, in *Discrete Optimization II*. Vol. 5 of *Annals of Discrete Mathematics*, edited by P. Hammer, E. Johnson and B. Korte. Elsevier (1979) 287–326.

[20] M. Haouari and A. Gharbi, An improved max-flow-based lower bound for minimizing maximum lateness on identical parallel machines. *Oper. Res. Lett.* **31** (2003) 49–52.

[21] L. Hidri, A. Gharbi and M. Haouari, Energetic reasoning revisited: application to parallel machine scheduling. *J. Scheduling* **11** (2008) 239–252.

[22] W. Horn, Some simple scheduling algorithms. *Nav. Res. Logistics Q.* **21** (1974) 177–185.

[23] J. Labetoulle, E.L. Lawler, J.K. Lenstra and A.R. Kan, Preemptive scheduling of uniform machines subject to release dates, in *Progress in Combinatorial Optimization*. Academic Press (1984) 245–261.

[24] Y. Ouellet and C.-G. Quimper, A $O(n \log^2 n)$ checker and $O(n^2 \log n)$ filtering algorithm for the energetic reasoning, in *International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research*, edited by W.-J. van Hoeve. Delft, The Netherlands (2018) 477–494.

[25] F. Tercinet, C. Lenté and E. Néron, Mixed satisfiability tests for multiprocessor scheduling with release dates and deadlines. *Oper. Res. Lett.* **32** (2004) 326–330.

[26] F. Tercinet, E. Néron and C. Lenté, Energetic reasoning and bin-packing problem, for bounding a parallel machine scheduling problem. *4OR* **4** (2006) 297–317.
[27] A. Tesch, A nearly exact propagation algorithm for energetic reasoning in o(n² log n), in International Conference on Principles and Practice of Constraint Programming, edited by M. Rueher. Springer International Publishing (2016) 493–519.

[28] A. Tesch, Improving energetic propagations for cumulative scheduling, in International Conference on Principles and Practice of Constraint Programming, edited by J. Hooker. Springer, Springer International Publishing, Lille, France (2018) 629–645.

[29] A. Vandevelde, *Minimizing the makespan in a multiprocessor flowshop*. Master thesis, Eindhoven University of Technology (1994).

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

Please help to maintain this journal in open access!

This journal is currently published in open access under the **Subscribe to Open model** (S2O). We are thankful to our subscribers and supporters for making it possible to publish this journal in open access in the current year, free of charge for authors and readers.

Check with your library that it subscribes to the journal, or consider making a personal donation to the S2O programme by contacting subscribers@edpsciences.org.

More information, including a list of supporters and financial transparency reports, is available at https://edpsciences.org/en/subscribe-to-open-s2o.