# Green scheduling with time-of-use tariffs and machine states: Optimizing energy cost via branch-and-bound and bin packing strategies

Ondřej Benedikt, István Módos, Antonin Novak, Zdeněk Hanzálek

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

## ► To cite this version:

Ondřej Benedikt, István Módos, Antonin Novak, Zdeněk Hanzálek. Green scheduling with time-of-use tariffs and machine states: Optimizing energy cost via branch-and-bound and bin packing strategies. European Journal of Operational Research, In press, 10.1016/j.ejor.2025.06.026. hal-05155764

HAL Id: hal-05155764

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

Submitted on 10 Jul 2025

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published 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_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Green Scheduling with Time-of-Use Tariffs and Machine States: Optimizing Energy Cost via Branch-and-Bound and Bin Packing Strategies

Ondřej Benediktª, István Módosª, Antonin Novakª,*, Zdeněk Hanzálekª

ªCzech Institute of Informatics, Robotics and Cybernetics, Czech Technical University in Prague, Czech Republic

## Abstract

This paper presents a branch-and-bound algorithm, enhanced with bin packing strategies, for scheduling under variable energy pricing and power-saving states. The proposed algorithm addresses the 1, TOU| states |TEC problem, which involves scheduling jobs to minimize total energy cost (TEC) while considering time-of-use (TOU) electricity prices and different machine states (e.g., processing, idle, off). Key innovations include instance pre-processing for rapid lower bound calculations, a novel branching scheme combined with initializations, a block-finding primal heuristic, and a tighter lower bound for jobs with non-coprime processing times. These enhancements result in an efficient algorithm capable of solving benchmark instances with real energy prices with 200 jobs more than 100 times faster than existing state-of-the-art methods.

**Keywords:** Scheduling, Single machine, Time of Use, Machine states, Variable energy costs, Total energy cost minimization, Branch and Bound.

## 1. Introduction

Optimizing the efficient use of energy in manufacturing facilities is crucial in today's world for several reasons. First, energy costs are rising continuously, and producing products and providing services is becoming more expensive. Therefore, businesses must find ways to lower their energy bills to remain competitive and increase profitability. This is especially important for the automotive or glass and steel industries, which rely on furnaces (Benedikt et al., 2021), industrial robots (Bukata et al., 2019), and similar machines that require a lot of energy. Second, energy consumption is a major contributor to greenhouse gas emissions, which are the leading cause of climate change. By reducing energy consumption, businesses can lower their carbon footprint and help mitigate the effects of climate change. Moreover, some governments, e.g., EU member states, are implementing regulations and incentives to encourage businesses to reduce their carbon emissions (Maris & Flouros, 2021). Further, rising energy costs, utility companies, and policymakers incen-

<footnote>*Corresponding author</footnote>

<footnote>Email addresses: ondrej.benedikt@cvut.cz (Ondřej Benedikt), istvan.modos@cvut.cz (István Módos), antonin.novak@cvut.cz (Antonin Novak), zdenek.hanzalek@cvut.cz (Zdeněk Hanzálek)</footnote>
tivize businesses to participate in demand-response programs and to plan their operations according to the use of their high-consumption machines to hedge against challenges in the energy market (Eid et al., 2016).

With demand response programs such as Time-Of-Use (TOU) (Chen & Zhang, 2019; Minh Hung et al., 2020) tariffs and Real-Time Pricing (RTP) (Abikarram et al., 2019), businesses can lower their costs by rescheduling their production to hours with cheaper energy or by changing the speeds of the machines. Furthermore, efficient use of the alternative processing modes of the machines or turning them off altogether decreases energy consumption. Nevertheless, the turn-on of a machine also requires a considerable amount of energy; thus, keeping the machine idling is sometimes the right choice.

Therefore, production scheduling with variable energy pricing and power-saving modes represents a very complex optimization problem that requires greater investigation.

To address these challenges, we study a single-machine scheduling problem with time-of-use tariffs defining the cost of energy in each time interval. The scheduling resource is stateful and is described by a transition diagram, defining the duration and consumption of transits between off, processing, and idle states, as well as the consumption in these states. The goal is to process the set of jobs during processing states so that the total energy cost (TEC) consumed by job processing and transitions between the machine states is minimized. The problem denoted in an extended three-field notation as 1, TOU|states|TEC was originally introduced in Shrouf et al. (2014). Later on, it was shown to be strongly NP-hard in Aghelinejad et al. (2019).

## 1.1. Paper Contributions and Outline

We revisit the problem 1, TOU|states|TEC with new insights with the goal of developing a scalable, exact branch-and-bound algorithm called B&B-SPACES that achieves state-of-the-art results, outperforming the former mixed-integer linear programming models both of Shrouf et al. (2014) and Benedikt et al. (2020) by two orders of magnitude. Among these insights, recognizing the bin-packing structure of the problem (Grus et al., 2024) and utilizing it in different aspects of B&B-SPACES proves to be the major source of increased efficiency.

More specifically, the main contributions are:

1. a fast branch-and-bound algorithm able to solve instances with hundreds of jobs over more than a thousand time intervals, outperforming the former state-of-the-art method (see Section 4),

2. employing instance pre-processing for lower bound computation, improving the complexity of the algorithm for a fixed sequence by Aghelinejad et al. (2019) (see Section 4.2),

3. proposing a tighter lower bound for non-coprime processing times (see Section 4.3),

4. new bin-packing primal heuristics for computing upper bounds inside the search tree (see Section 4.4),
5. new initialization heuristics based on the *bin-finding* problem (see Section 4.5).

The rest of the paper is structured as follows. In Section 2, we formally define the statement of the scheduling problem under study together with the key notation and symbols used. The relevant literature surveying the related problem is given in Section 3. The two key concepts—the optimal switching problem and computing TEC for a given fixed sequence of the jobs are explained in Appendix A and Section 4.1. Further algorithmic components, i.e., lower and upper bounds of B&B-SPACES algorithm, are described in Section 4. Finally, we demonstrate the efficiency of the resulting method on the benchmark instances of various parameters in Section 5.

## 2. Problem Statement

We consider a scheduling problem whose horizon is divided into a set of $h \in \mathbb{Z}_{>0}$ non-overlapping intervals $\mathcal{I} = \{1, 2, \dots, i, \dots, h\}$. It is assumed that every interval is one unit long.

The physical representation of the time unit length can be different depending on the desired granularity. For example, most typically, a single interval will resemble 15-minute or 1-hour long intervals, as the energy markets operate on these scales. Scheduling over one thousand intervals resembles operations spanning over more than a week-long horizon, matching the real conditions commonly encountered on the market (such as OTE in the Czech Republic) regarding the forecast and auctions. For every interval $i$, the energy cost $c_i \in \mathbb{Q}$ is given. The vector of energy costs is denoted by $\mathbf{c}$, where $\mathbf{c} = (c_1, c_2, \dots, c_h)$.

Note that we assume that the energy cost can be even negative. Although this is likely not to be the realistic case with, e.g., natural gas, with electricity, the situation is different. For example, due to the increasing amount of power deployed in renewable sources every year, from April to August 2024 in the Czech Republic, there were nearly 50 days with intervals having negative electricity cost—up to 3 times more than the year before.

<figure><img src="image_3.png" /><figcaption>Figure 1: Example of a schedule to illustrate the notation; optimal solution with the objective 342.</figcaption></figure>

During each interval, the machine operates in one of its states $s \in S$ or transits from one state to another. We assume the existence of at least two states: the *off state* $\mathbf{off} \in S$ and the *processing state* $\mathbf{proc} \in S$.
The machine is assumed to be operating in off state during the first and the last interval. Also, when a job is processed, the machine must be operating in proc state.

The transition time function and the transition power function are denoted by $T: S \times S \to \mathbb{Z}_{\ge 0} \cup \{\infty\}$ and $P: S \times S \to \mathbb{Q}_{\ge 0} \cup \{\infty\}$, respectively. The symbol $\infty$ is used to denote that the direct transition between states $(s, s') \in S \times S$ does not exist. The transition from state $s$ to state $s'$ lasts $T(s, s')$ intervals and has power consumption $P(s, s')$, which is the constant rate of the consumed energy at every time unit. Further, we assume that $T(s, s) = 1$, meaning that the power consumption of the machine while remaining in state $s$ for the duration of one interval is $P(s, s)$. Note that the transition time and power functions are general enough to represent different kinds of manufacturing machines, e.g., those studied in (Aghelinejad et al., 2018; Benedikt et al., 2020; Mouzon et al., 2007; Shrouf et al., 2014).

Let $\mathcal{J}$ be a set of $n$ jobs $\{J_1, J_2, \dots, J_j, \dots, J_n\}$ to be scheduled. Each job $J_j$ is characterized by its processing time $p_j \in \mathbb{Z}_{>0}$, given in the number of intervals. The cost of processing a job inside an interval $i$ is the same for all jobs. Jobs are non-preemptive, and the machine can process at most one job at a time. All the jobs are available at the beginning of the scheduling horizon.

A solution is defined by a pair $(\sigma, \Omega)$, where $\sigma = (\sigma_1, \sigma_2, \dots, \sigma_n) \in \mathbb{Z}_{\ge 0}^n$ represents start times of the jobs, and $\Omega = (\Omega_1, \Omega_2, \dots, \Omega_h) \in (S \times S)^h$ captures the active state or transition in each interval, where $\Omega_i = (\text{off}, \text{proc})$ represents turning on, $\Omega_i = (\text{proc}, \text{proc})$ represents staying in the processing state, $\Omega_i = (\text{proc}, \text{idle})$ represents transition from processing into an idle state, $\Omega_i = (\text{idle}, \text{idle})$ staying in an idle state, $\Omega_i = (\text{idle}, \text{proc})$ is transition from idle to processing state while $\Omega_i = (\text{proc}, \text{off})$ represents the transition from the processing state to the off state.

The solution is feasible if the following four conditions are satisfied:

1. the machine processes at most one job at a time,

2. the jobs are processed only when the machine is in proc state,

3. the machine is in off state during the first and the last interval,

4. transition between states $s$ and $s'$ takes $T(s, s')$ time intervals.

The total energy cost (TEC) of solution $(\sigma, \Omega)$ is calculated as

$$ \sum_{i \in \mathcal{I}} c_i \cdot P(\Omega_i), \qquad (2.1) $$

where $P(\Omega_i)$ represents $P(s, s')$ for $\Omega_i = (s, s')$. The goal of the scheduling problem is to find a feasible solution such that the total energy cost (2.1) is minimized.

During the first and the last interval, the machine is assumed to be in off state $\text{off} \in S$ (see 3. above). The machine has a single processing state $\text{proc} \in S$, which must be active during the processing of the
jobs (see 2. above). Due to the transition time from/to the initial/last off state, the machine cannot be
in the proc state during (several) early/late intervals. Hence, we denote the earliest and the latest interval
during which the machine can be in proc state by early and late, respectively. Consequently, the set of
processing intervals is denoted as $\mathcal{I}^{\text{proc}} = \{\text{early}, \text{early} + 1, \dots, \text{late}\}$. The definition of the earliest and the
latest processing intervals becomes useful later in the problem of the optimal TEC computation for a fixed
job sequence in Section 4.1.

**Example 1:** Let us consider a small example with three jobs, $\mathcal{J} = \{J_1, J_2, J_3\}$ with processing times $p_1 = 1$, $p_2 = 2$, and $p_3 = 4$, respectively. Let the scheduling horizon contain 20 intervals, $\mathcal{I} = \{1, \dots, 20\}$, with energy costs $\mathbf{c} = (9, 7, 9, 13, 3, 11, 3, 13, 6, 7, 60, 4, 10, 6, 9, 3, 14, 0, 4, 6)$. Considering the machine states and transitions, let us use the transition graph proposed in Shrouf et al. (2014), which is also depicted in Fig. 2. The optimal solution to this instance is depicted in Fig. 1. Its TEC is equal to 342.

<figure><img src="image_4.png" /><figcaption>Figure 2: Parameters of the transition power function $P(s, s')$ and transition time function $T(s, s')$, and the corresponding transition graph, where every edge from $s$ to $s'$ is labeled by $T(s, s')/P(s, s')$.</figcaption></figure>

Note that the transition graph in Fig. 2 considers transitions between **proc** and **idle** states to take
zero time and to consume zero energy while doing so. We argue that this is a rather physically unrealistic
case that we follow from Shrouf et al. (2014), but it serves as an example of extreme behavior that can be
modeled with transition graphs. In general, including an **idle** state into the model of a machine may be
beneficial depending on the values of transition power and time functions, as demonstrated in the following
example.

**Example 2:** Consider an example of a machine modeled with two different transition diagrams. The option in Fig. 3a resembles a simplified model of the machine that neglects the possibility of utilizing its **idle** state, while the option Fig. 3b explicitly contains it. Each respective plot above the transition diagram displays TEC isolines (i.e., the areas with identical TEC values), depending on the values of the transition power function between {off, proc} states. The values are computed by sampling 20 × 20 pairs of parameter values in the considered range while constructing an optimal schedule for a set of 5 jobs with processing times {1, 2, 2, 4, 5} under the energy cost profile shown in Fig. 3c. The example shows (besides overall lower TEC in Fig. 3b) how introducing an **idle** state can change the landscape of TEC isolines, affecting trade-offs of
transition power function values between off and proc states.

<figure><img src="image_5.png" /><figcaption>Figure 3: TEC isolines of a machine including and neglecting idle state.</figcaption></figure>

The above-defined problem was introduced in Shrouf et al. (2014) and is denoted in an extended Graham's notation as 1, TOU|states|TEC. The problem was shown to be strongly NP-hard in Aghelinejad et al. (2019).

## 3. Related work

The scheduling literature on energy-efficient scheduling and sustainable manufacturing concentrates primarily on the problems concerning Time-of-Use energy tariffs and the minimization of total energy costs (Catanzaro et al., 2023). The fundamental setting in these problems is that we are given a finite time horizon discretized into time intervals (e.g., 15 minutes), each associated with a cost for processing jobs inside the interval. Jobs have processing time expressed in terms of an integer number of intervals. The goal is to schedule all jobs on a single machine such that the total energy consumption is minimized, possibly
subject to a constraint on the schedule makespan. This basic scheduling problem with the time-of-use costs was coined by Wan & Qi (2010).

Even the basic problem is quite practical and can be used to obtain some cost savings. However, to match more complex use cases, many different variants were proposed. In that respect, the most prominent research lines consider developing more complex machine environments, such as parallel identical machines (Anghinolfi et al., 2021; Tian & Zheng, 2024; Gaggero et al., 2023), unrelated machines (Rego et al., 2022; Pei et al., 2021), storage resources (Ngueveu et al., 2022), flow shops (Ho et al., 2022; Aghelinejad et al., 2020b) or job shops (Park & Ham, 2022).

Other extensions of the problem consider different objective functions beyond TEC, mostly to express also the timelines of the schedule. Among the most popular are bi-criteria and multi-objective approaches combining TEC with the makespan (Chen et al., 2021; Pei et al., 2021) and total (weighted) tardiness (Rocholl et al., 2020; Ding et al., 2021).

Different approaches for bringing the scheduling models closer to reality consider more complex models of the job. For example, considering non-uniform energy consumption (Cheng et al., 2018), speed (Nattaf et al., 2017; Fatih Tasgetiren et al., 2018) (i.e., faster processing of the jobs in exchange for larger energy consumption), non-integer start times (Chen & Zhang, 2019), release times (Wu et al., 2023) or scheduling with disjoint setup operations of energy-demanding machine reconfigurations (Gnatowski et al., 2022). Typically, these were investigated in a single-machine setting first and later extended to more complex resource environments (Wang et al., 2020).

The complexity of particular problems also depends on the assumed properties of the energy cost vector *c*. For example, if *c* takes a "pyramidal" shape (i.e., increasing and then decreasing), then the problem can become solvable in polynomial time (Fang et al., 2016). However, in realistic costs, this shape typically does not occur. Further results of Chen & Zhang (2019) show that the problem complexity can depend on the number of "valleys" of the energy cost vector *c*. The basic problem with makespan minimization, where energy consumption represents a hard constraint, does admit a 1.34-approximation algorithm (Li & Ou, 2024).

However, all the above extensions of the basic time-of-use scheduling problem disregard the fact that often the manufacturing resources are stateful machines (Aghelinejad et al., 2018; Benedikt et al., 2020; Mouzon et al., 2007; Shrouf et al., 2014)—meaning the machine has several operational modes, such as off, power saving, and processing mode. The transitions between machine states are governed by the control logic and machine dynamics. The operations on the jobs are performed only when the machine is in one of its processing states, while significant energy savings can be achieved by switching the machine to idle mode or even turning it off when the energy price is high. Switching between machine operational modes adds another layer of complexity to the already NP-hard scheduling problem with time-of-use costs. In this sense, the previous works that disregarded machine dynamics and operation modes can be seen as simplified
problems where one assumes that the machine operates only in its processing state uninterrupted over the
whole scheduling horizon.

The problem with simultaneous scheduling of jobs and switching operational states of the machine was
first introduced by Shrouf et al. (2014), denoted in three-field scheduling notation as 1, TOU|states|TEC.
The authors proposed an Integer Linear Programming (ILP) model for a single-machine environment and
fixed order of the jobs. Later, Aghelinejad et al. (2019) proved the problem without fixed order is hard, but
under the fixed order of the jobs, it becomes polynomial-time solvable. The restriction on the fixed order of
jobs was lifted in Aghelinejad et al. (2018), where an ILP model was proposed to finally solve the original
problem. However, this approach was able to solve instances with up to 35 jobs to optimality. Different
variants of the problems were further studied. A case of the problem with preemptive jobs was studied in
Aghelinejad et al. (2017) or extensions of the problem into flow shop setting (Aghelinejad et al., 2020a,c).

Later, Benedikt et al. (2020) realized that the performance of ILP and Constraint Programming (CP)
models can be greatly enhanced by utilizing a pre-processing technique called SPACES that precomputes
the optimal switching behavior of the machine between different intervals (since the costs differ) in advance
and using these precomputed sequences inside the ILP and CP models. This led to a new state-of-the-
art performance, and the proposed algorithms were able to solve instances with 190 jobs that were up to
optimality. However, some of the problem structures were under-utilized and unexplored due to the limited
flexibility of the mathematical programming models. For example, their ILP model could not exploit the
result of Aghelinejad et al. (2019) that the problem is polynomially solvable under the fixed order of the
jobs. However, perhaps more importantly, the way in which the SPACES algorithm determines the optimal
switching behavior between every pair of intervals and states suggests that, although not apparent at first
sight, the precomputed switching creates so-called *spaces* that can be used to form bins for a kind-of bin
packing problem. Thus, the problem inherently consists of a packing problem that can be typically solved
very efficiently in practice.

In this paper, we further explore the properties of the 1, TOU|states|TEC problem. To exploit them
inside an optimization algorithm fully, instead of formulating a new mathematical programming model, we
design a custom branch-and-bound algorithm utilizing techniques of Aghelinejad et al. (2019); Benedikt
et al. (2020) and new observations made in this work that gave us enough flexibility to reach 100× speedup
over the former state-of-the-art algorithm (Benedikt et al., 2020). Furthermore, the proposed techniques are
not only tied to this specific problem; thus, we believe they can be applied to similar problems considering
time-of-use scheduling.
## 4. Branch-and-Bound Algorithm for 1, TOU|states|TEC

For the scheduling problem 1, TOU|states|TEC defined in Section 2, we develop a fast, exact branch-and-bound algorithm called B&B-SPACES. Generally, a Branch and Bound is an exact algorithm for solving combinatorial problems. It recursively partitions the solution space into a tree using specific branching rules. By employing a lower bound, parts of the solution space with an objective value that is worse than the currently best value can be pruned and excluded from the search.

Before explaining details of B&B-SPACES, we discuss important properties of the problem required for designing the algorithm, namely the optimal TEC computation for a fixed jobs sequence presented in Section 4.1. Further, we rely on the technique of pre-processing the optimal state switching of Benedikt et al. (2020), with its details briefly summarized in Appendix A.

To design an efficient branch-and-bound algorithm, multiple parts of the algorithm are important, especially (i) an efficient branching rule, (ii) a tight lower bound that can be obtained in a reasonable time, and (iii) a good initialization upper bound with primal heuristics to prune the tree as soon as possible. The rest of the section explains the individual components of B&B-SPACES.

### 4.1. Optimal TEC Computation for a Fixed Jobs Sequence

In Aghelinejad et al. (2019), the problem of computing the optimal TEC with machine states for a fixed sequence of jobs was shown to be polynomial. The authors solve this problem by finding the shortest path in a job-interval graph that models both the cost of scheduling the jobs and the cost of transiting between the machine states.

In this work, instead of modeling the transitions between the machine states explicitly, we improve the approach proposed in Aghelinejad et al. (2019) by incorporating only the optimal switching costs found by solving the optimal switching problem by a technique called SPACES (Benedikt et al., 2020). This way, we obtain a job-interval graph with a size independent of the size of the transition graph. Thus, the optimal TEC can be found in a shorter time, which is critical for its usage inside a branch-and-bound algorithm, where it needs to be evaluated in every search node. See Appendix A for more details about the optimal switching problem and SPACES technique.

Let $\pi: \{1, \dots, n\} \to \{1, \dots, n\}$ be a bijective function representing a fixed jobs sequence on the machine, i.e., $\pi(\ell)$ maps position $\ell$ in the sequence to job index $j$. Given fixed jobs sequence $\pi$, the set of intervals in which job on position $\ell \in \{1, \dots, n\}$ can be scheduled, is denoted as

$$ \mathcal{I}_{\ell}^{\text{proc}} = \{i \in \mathcal{I}^{\text{proc}} : \textit{early} + \sum_{\ell'=1}^{\ell-1} p_{\pi(\ell')} \le i \le \textit{late} - \sum_{\ell'=\ell}^{n} p_{\pi(\ell')} + 1\}. \quad (4.1) $$

where early and late are indices of early and late, respectively. The definition of $\mathcal{I}_{\ell}^{\text{proc}}$ takes into account early/late proc intervals (to start up and turn off the machine) and the time required for scheduling the jobs on positions before/after $\ell$.
To find the optimal TEC for fixed jobs sequence $\pi$, let us define a job-interval graph $G^{ji}$ by a triplet $G^{ji} = (V^{ji}, E^{ji}, w^{ji})$, where $V^{ji}$ is the set of vertices, $E^{ji}$ is the set of edges and $w^{ji}: E^{ji} \to \mathbb{Z}_{\ge 0}$ are the weights of the edges. The set of the vertices and edges of the job-interval graph are defined as follows:

$$V^{ji} = \{v_0^{ji}\} \cup \{v_{\ell,i}^{ji}: \ell \in \{1, \dots, n\}, i \in \mathcal{I}_{\ell}^{\text{proc}}\} \cup \{v_{n+1}^{ji}\}, \quad (4.2)$$

$$E^{ji} = \{(v_0^{ji}, v_{1,i}^{ji}): i \in \mathcal{I}_1^{\text{proc}}\} \\ \cup \{(v_{\ell,i}^{ji}, v_{\ell+1,i'}^{ji}): \ell \in \{1, \dots, n-1\}, i \in \mathcal{I}_{\ell}^{\text{proc}}, i' \in \mathcal{I}_{\ell+1}^{\text{proc}}, i+p_{\pi(\ell)} \le i'\}, \quad (4.3) \\ \cup \{(v_{n,i}^{ji}, v_{n+1}^{ji}): i \in \mathcal{I}_n^{\text{proc}}\}.$$

Informally, each edge $(v_{\ell,i}^{ji}, v_{\ell+1,i'}^{ji})$ represents a scheduling of job $J_{\pi(\ell)}$ at the beginning of interval $i$ and job $J_{\pi(\ell+1)}$ at beginning of interval $i'$. Vertices $v_0^{ji}$ and $v_{n+1}^{ji}$ correspond to the first and the last off state of the machine, respectively.

The weights of the edges take both the jobs processing costs and the optimal switching costs into account, which is in contrast to the original idea presented in Aghelinejad et al. (2019), where the costs of transitions between machine states are considered. Different edge types have different weights:

* edges from the first off state to the first job:

$$w^{ji}(v_0^{ji}, v_{1,i}^{ji}) = c_1 \cdot P(\text{off}, \text{off}) + c^*(1, i); \quad (4.4)$$

* edges between two consecutive jobs:

$$w^{ji}(v_{\ell,i}^{ji}, v_{\ell+1,i'}^{ji}) = c_{j,\pi(\ell)}^{(\text{job})} + c^*(i + p_{\pi(n)} - 1, i'), \quad (4.5)$$

where

$$c_{j,i}^{(\text{job})} = \sum_{i'=i}^{i+p_j-1} c_{i'} \cdot P(\text{proc}, \text{proc}) \quad (4.6)$$

is the cost of scheduling job $J_j$ at the beginning of interval $i$;

* edges from the last job to the last off state:

$$w^{ji}(v_{n,i}^{ji}, v_{n+1}^{ji}) = c_{\pi(n),i}^{(\text{job})} + c^*(i + p_{\pi(n)} - 1, h) + c_h \cdot P(\text{off}, \text{off}). \quad (4.7)$$

To obtain the optimal TEC for the fixed jobs sequence, it suffices to find the cost of the shortest path from $v_0^{ji}$ to $v_{n+1}^{ji}$. For a given sequence $\pi$, we denote the optimal TEC by $c^{\text{TEC}}(\pi)$. Notice that the job-interval graph is topologically ordered according to the lexicographic ordering of the labels $(\ell, i)$ of the vertices. Therefore, the shortest path can be found by processing the vertices along this topological ordering, which can be done in $O(h^2 \cdot n)$ time by using, e.g., Bellman-Ford algorithm for DAGs that runs in $O(|V^{ji}| + |E^{ji}|)$ time. The complexity of the pre-processing for obtaining the optimal switching costs
<figure><img src="image_6.png" /><figcaption>Figure 4: Example job-interval graph.</figcaption></figure>

by SPACES is $O(h^2 \cdot |S| \cdot (|S| + \log h + \log |S|))$ (for non-negative energy costs $c$, see Appendix A for more details). Hence, when added up, this represents an improvement over the job-interval graph proposed in Aghelinejad et al. (2019), where finding the shortest path takes $O(h^2 \cdot \sum_{J_j \in \mathcal{J}} p_j)$, since here we avoid the pseudo-polynomial factor in terms of the processing times. Also, note that since the graph is acyclic, we can still handle instances with negative energy costs as these are encapsulated inside weights $w^{ji}$ of the job-interval graph.

## 4.2. The branching strategy and the lower bound

B&B-SPACES progressively constructs the jobs sequence $\pi$. In each node of the search tree, B&B-SPACES keeps the current *partial job sequence* $\hat{\pi} : \{1, \dots, |\hat{\mathcal{J}}|\} \to \hat{\mathcal{J}}$ for some jobs subset $\hat{\mathcal{J}} \subseteq \mathcal{J}$. The algorithm branches on the remaining un-fixed jobs $\mathcal{J} \setminus \hat{\mathcal{J}}$, i.e., a new branch is created by appending one of the remaining jobs to the end of $\hat{\pi}$. To break the symmetries arising from the jobs having equal processing times, only one branch per unique remaining processing time is created in each node. To understand the branching, see an example of a branching subtree in Fig. 5 corresponding to the example in Section 2 with
three jobs $J_1, J_2, J_3$ with processing times $\{1, 2, 4\}$, respectively.

The lower bound for each node of the branching tree is computed using the method for a fixed sequence utilizing the job-interval graph described in Section 4.1. Let $\hat{\pi} : \{1, \dots, |\hat{\mathcal{J}}|\} \to \hat{\mathcal{J}}$ be the partial job sequence in a search tree node for some jobs subset $\hat{\mathcal{J}} \subseteq \mathcal{J}$. To compute the lower bound, a new set of jobs $\mathcal{J}^{\text{lb}}$ is created by splitting the remaining un-fixed jobs into unit processing times jobs, i.e.,

$$ \mathcal{J}^{\text{lb}} = \hat{\mathcal{J}} \cup \{J_j^1 : j \in \{1, \dots, \sum_{J_{j'} \in \mathcal{J} \setminus \hat{\mathcal{J}}} p_{j'}\}\}, \quad (4.8) $$

where $J_j^1$ is a new job with unit processing time. From $\mathcal{J}^{\text{lb}}$, a jobs sequence $\hat{\pi}^{\text{lb}}$ is defined as follows

$$ \hat{\pi}^{\text{lb}}(\ell) = \begin{cases} \hat{\pi}(\ell) & \ell \le |\hat{\mathcal{J}}|, \\ J_{\ell-|\hat{\mathcal{J}}|}^1 & |\hat{\mathcal{J}}| < \ell \le |\mathcal{J}^{\text{lb}}|. \end{cases} \quad (4.9) $$

The lower bound $lb = c^{\text{TEC}}(\hat{\pi}^{\text{lb}})$ in the search tree node is then obtained by running the method from Section 4.1 on jobs sequence $\hat{\pi}^{\text{lb}}$. See an example of the branching tree with computed lower bounds values in Fig. 5. The tree is traversed in a depth-first search, starting with the leftmost child. At the leaves of the search tree, we obtain a feasible solution with the objective value equal to $ub$, representing an upper bound on the optimal objective value that is used to prune subtrees with the lower bound $lb \ge ub$. The following proposition formally states the lower bound.

**Proposition 1.** Let $\hat{\pi} : \{1, \dots, |\hat{\mathcal{J}}|\} \to \hat{\mathcal{J}}$ be a partial sequence of jobs $\hat{\mathcal{J}} \subseteq \mathcal{J}$, and $\hat{\pi}^{\text{lb}}$ be the relaxed sequence defined by (4.9). Then, for any permutation $\pi : \{1, \dots, |\mathcal{J}|\} \to \mathcal{J}$ satisfying $\pi(\ell) = \hat{\pi}(\ell), \forall \ell \in \{1, \dots, |\hat{\mathcal{J}}|\}$ it holds that $c^{\text{TEC}}(\pi) \ge c^{\text{TEC}}(\hat{\pi}^{\text{lb}})$.

Later in Section 4.3, we will prove a slightly stronger version of this proposition.

*Implementation remarks.* The computation of the lower bound between the nodes can be performed efficiently using only a two-dimensional array of the costs. The rows of the array are called *levels*, and the array contains $\sum_{J_j \in \mathcal{J}} p_j$ levels. The number of columns corresponds to $|\mathcal{I}^{\text{proc}}|$. Each element of the array can be seen as a corresponding vertex from the set $V^{\text{ji}}$ of the job-interval graph, where each job has a processing time of 1.

When a job $J_j \in \mathcal{J} \setminus \hat{\mathcal{J}}$ is appended to the end of the $\hat{\pi}$ in a search tree node, the levels $\{\sum_{J_{j'} \in \hat{\mathcal{J}}} p_{j'}', \dots, p_j + \sum_{J_{j'} \in \hat{\mathcal{J}}} p_{j'}'\}$ are *joined* together, i.e., as if the edges in the job-interval graph between these levels were removed. On the other hand, on backtracking from a node, the levels are *split*, i.e., as if the edges in the job-interval graph between these levels are included again. For the better utilization of the data structures, i.e., no copies of the memory-intensive objects, the B&B-SPACES is implemented as a depth-first search.
<figure><img src="image_7.png" /><figcaption>Figure 5: Branch-and-bound tree with lower bound $\hat{\pi}^{lb}$. The numbers on the edges correspond to the processing time of the job selected during the branching.</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>Figure 6: Branch-and-bound with lower bound $\hat{\pi}_{gcd}^{lb}$ improved with gcd of the unfixed jobs. Bounds that were improved with respect to Fig. 5 are highlighted in a rectangle.</figcaption></figure>
### 4.3. Tightening the Lower Bound for Non-coprime Processing Times

The lower bound introduced in Section 4.2 relies on the relaxation of the non-preemptive jobs into a set of jobs with unit processing times. Since these jobs are interchangeable, they can be scheduled optimally using the job-interval graph under an arbitrary permutation. The idea for improving this lower bound builds on the observation that particular sets of un-fixed jobs $\mathcal{J} \setminus \hat{\mathcal{J}}$ can be relaxed into jobs with processing times greater than one, thus improving the relaxation. We say that a set of positive integers is non-coprime if their greatest common divisor is greater than 1. In this section, we explain how a tighter lower bound for jobs having non-coprime processing times can be obtained.

The idea of obtaining a tighter lower bound is similar to the one of $c^{\text{TEC}}(\hat{\pi}^{\text{lb}})$. Let $\mathcal{J} \setminus \hat{\mathcal{J}}$ be a set of un-fixed jobs in some node of the search tree. Further, let

$$ \text{gcd}(\mathcal{J} \setminus \hat{\mathcal{J}}) = \text{gcd}(\{p_{j'} : J_{j'} \in \mathcal{J} \setminus \hat{\mathcal{J}}\}) $$

be the greatest common divisor of processing times of all un-fixed jobs. We define a set of jobs

$$ \mathcal{J}_{\text{gcd}}^{\text{lb}} = \hat{\mathcal{J}} \cup \{J_{j}^{\text{gcd}} : j \in \{1, \dots, \text{gcd}(\mathcal{J} \setminus \hat{\mathcal{J}})^{-1} \cdot \sum_{J_{j'} \in \mathcal{J} \setminus \hat{\mathcal{J}}} p_{j'}\}\}, \quad (4.10) $$

where $J_{j}^{\text{gcd}}$ is a new job with processing time equal to $\text{gcd}(\mathcal{J} \setminus \hat{\mathcal{J}})$. Finally, the sequence $\hat{\pi}_{\text{gcd}}^{\text{lb}}$ of jobs $\mathcal{J}_{\text{gcd}}^{\text{lb}}$ is defined similarly as (4.9), that is

$$ \hat{\pi}_{\text{gcd}}^{\text{lb}} = \begin{cases} \hat{\pi}(\ell) & \ell \le |\hat{\mathcal{J}}|, \\ J_{\ell-|\hat{\mathcal{J}}|}^{\text{gcd}} & |\hat{\mathcal{J}}| < \ell \le |\mathcal{J}_{\text{gcd}}^{\text{lb}}|. \end{cases} \quad (4.11) $$

Finally, a lower bound on TEC with respect to the partial solution $\hat{\mathcal{J}}$ is obtained by solving the problem with the set of jobs $\mathcal{J}_{\text{gcd}}^{\text{lb}}$ under sequence $\hat{\pi}_{\text{gcd}}^{\text{lb}}$ on job-interval graph by a procedure given in Section 4.1.

**Proposition 2.** Let $\hat{\pi} : \{1, \dots, |\hat{\mathcal{J}}|\} \to \hat{\mathcal{J}}$ be a partial sequence of jobs $\hat{\mathcal{J}} \subseteq \mathcal{J}$, and $\hat{\pi}^{\text{lb}}$, $\hat{\pi}_{\text{gcd}}^{\text{lb}}$ be the relaxed sequences defined by (4.9) and (4.11). Then, for any permutation $\pi : \{1, \dots, |\mathcal{J}|\} \to \mathcal{J}$ satisfying $\pi(\ell) = \hat{\pi}(\ell), \forall \ell \in \{1, \dots, |\hat{\mathcal{J}}|\}$ it holds that $c^{\text{TEC}}(\pi) \stackrel{(a)}{\ge} c^{\text{TEC}}(\hat{\pi}_{\text{gcd}}^{\text{lb}}) \stackrel{(b)}{\ge} c^{\text{TEC}}(\hat{\pi}^{\text{lb}})$ with inequality (b) being strict for some inputs.

*Proof.* The inequality (a) follows from the observation that $\mathcal{J}_{\text{gcd}}^{\text{lb}}$ represents the problem that relaxes on the condition of non-preemptive jobs. To show $c^{\text{TEC}}(\hat{\pi}_{\text{gcd}}^{\text{lb}})$ is indeed a lower bound on $c^{\text{TEC}}(\pi)$, one needs to ensure that sequence $\hat{\pi}_{\text{gcd}}^{\text{lb}}$ is the optimal solution of the relaxed problem, that is whether

$$ \hat{\pi}_{\text{gcd}}^{\text{lb}} \in \arg \min_{\pi' \in \Pi(\mathcal{J}_{\text{gcd}}^{\text{lb}})} c^{\text{TEC}}(\pi'), $$

where $\Pi(\mathcal{J}_{\text{gcd}}^{\text{lb}})$ is the set of all permutations of jobs $\mathcal{J}_{\text{gcd}}^{\text{lb}}$. Focusing on the unfixed part of the jobs $\mathcal{J}_{\text{gcd}}^{\text{lb}} \setminus \hat{\mathcal{J}}$, one can see that all jobs $J_{j}^{\text{gcd}}$ are identical with processing time equal to $\text{gcd}(\mathcal{J} \setminus \hat{\mathcal{J}})$. Thus, all unfixed
jobs are completely interchangeable. Therefore, we can employ the method from Section 4.1 applied to a job-interval graph with a fixed sequence to obtain the optimal solution of the relaxed problem.

Similarly, for inequality (b), sequence $\hat{\pi}^{lb}$ can be seen as an optimal solution of a relaxed problem with $\mathcal{J}_{gcd}^{lb}$ into unit-processing time jobs $J_j^1$ and the same arguments as above apply. To see why the inequality (b) is strict for some instances (namely the ones with short sequences of intervals with low costs) when gcd > 1, see, e.g., example branching trees in Fig. 5 and Fig. 6. An illustrative example would consider an instance where gcd = 2, with one interval $i$ having cost significantly smaller than its neighborhood intervals, i.e., $\min\{c_{i-1}, c_{i+1}\} \gg c_i$. The unit processing time lower bound $\hat{\pi}^{lb}$ would exploit cheap interval $i$, whereas $\hat{\pi}_{gcd}^{lb}$ avoids it, leading to a stronger bound. $\square$

### 4.4. Bin-packing Primal Heuristic

In order to find a good upper bound $ub$ as soon as possible, so-called primal heuristics are often used during the search. These heuristics try to reconstruct a feasible solution early in the search tree (possibly in each node of the tree), hoping to further prune the branches that do not contain any better solution. In B&B-SPACES, we introduce a similar idea based on the observation that the solution to the relaxed problem can be, in some cases, used to recover a solution for the original problem that does not preempt the jobs. In such cases, the cost of the recovered solution matches the lower bound value, efficiently pruning the search subtree.

In each node of the search tree, we first compute a lower bound for either jobs sequence given by $\hat{\pi}^{lb}$ or $\hat{\pi}_{gcd}^{lb}$ using the method described in Section 4.2. From the solution of the relaxed instance, we extract the maximal sequences of consecutive intervals during which the machine operates in the proc state. Let us denote these sequences by $(\Lambda_1, \Lambda_2, \dots, \Lambda_k, \dots, \Lambda_{n(\hat{\pi}^{lb})})$, where $\Lambda_k \subseteq \mathcal{I}^{proc}$ and $n(\hat{\pi}^{lb})$ is the number of these maximal sequences in the optimal solution of the relaxed problem for $\hat{\pi}^{lb}$ (or $\hat{\pi}_{gcd}^{lb}$). Now, we may formulate the following $\mathcal{P}_{Bin-Pack}$ bin-packing problem:

**$\mathcal{P}_{Bin-Pack}$ problem.** Given the maximal processing intervals sequences $(\Lambda_1, \dots, \Lambda_k, \dots, \Lambda_{n(\hat{\pi}^{lb})})$ and given the jobs $\mathcal{J}$, find a partition of $\mathcal{J}$ into disjoint sets $\mathcal{J}_1, \dots, \mathcal{J}_k, \dots, \mathcal{J}_{n(\hat{\pi}^{lb})}$ such that

$$ \forall k \in \{1, \dots, n(\hat{\pi}^{lb})\}: \sum_{J_j \in \mathcal{J}_k} p_j \le |\Lambda_k|, \quad (4.12) $$

where $|\Lambda_k|$ is the length of $k$-th sequence of consecutive processing intervals.

The $\mathcal{P}_{Bin-Pack}$ problem resembles the decision version of a bin-packing problem with unequal bin sizes, which is known to be NP-complete. If the $\mathcal{P}_{Bin-Pack}$ problem instance is solved in a node of the branch and bound tree and is feasible, we obtain a feasible solution to $1, TOU$ states |TEC with the objective value $ub$. The $ub$ value is the total energy cost of that solution and is equal to the lower bound $c^{TEC}(\hat{\pi}^{lb})$. Therefore,
<figure><img src="image_9.png" /><figcaption>Figure 7: Branch-and-bound tree with the bin-packing primal heuristic. Feasible solutions are found earlier in the search tree.</figcaption></figure>

the whole sub-tree rooted in the current node can be pruned since the lower bound may only increase within the sub-tree. On the other hand, if the $P_{Bin-Pack}$ problem is not solved, the B&B-SPACES continues branching.

**Example 3:** Consider the node highlighted by a green rectangle in the branch and bound tree in Fig. 7. When computing a lower bound for the unfixed job with original processing times $\{1,4\}$ relaxed into five unit-sized jobs $J_j^1$ since $\gcd\{1,4\} = 1$. The shortest path on the job-interval graph from Section 4.1 leads to a solution considering the optimal switching behavior

$$ \Omega^*(1, 20) = ((\text{off}, \text{off}), (\text{off}, \text{off}), (\text{off}, \text{off}), (\text{off}, \text{proc}), (\text{proc}, \text{proc}), (\text{proc}, \text{proc}), (\text{proc}, \text{off}), (\text{off}, \text{proc}), (\text{proc}, \text{proc}), (\text{proc}, \text{proc}), (\text{proc}, \text{idle}), (\text{idle}, \text{proc}), (\text{proc}, \text{off}), (\text{off}, \text{off})) $$

with the cost of 339. This induces an instance of $P_{Bin-Pack}$ problem with $(\Lambda_1, \Lambda_2, \Lambda_3)$ having $|\Lambda_1| = 3$, $|\Lambda_2| = 3$ and $|\Lambda_3| = 1$. Such an instance is infeasible. Thus, branching continues with the sequence $(J_2, J_1)$, where $\gcd$ of unfixed jobs is 4. Computing the lower bound at this node, i.e., the optimal solution for sequence $\hat{\pi}_{gcd}^{lb}$, yields a relaxed solution with blocks $|\Lambda_1| = 2$ and $|\Lambda_2| = 5$ (identical to the one shown in Fig. 1), which can be used to pack all jobs with processing times $\{1, 2, 4\}$, producing a feasible solution with $c^{TEC}$ equal to $ub = 342$, matching a lower bound value $c^{TEC}(\hat{\pi}_{gcd}^{lb})$.

**Implementation remarks.** The packing problem $P_{Bin-Pack}$ can be tackled by any standard approach, including the heuristics or the exact algorithms. In our case, we solve $P_{Bin-Pack}$ using IBM CP Optimizer with a single PACK global constraint. Since the bin-packing problem is NP-complete in general, the time limit has to be set for the solver to avoid stalling, although in practice, such problems are solved quickly.
### 4.5. Initial Heuristic based on the Blocks Found in the Root

B&B-SPACES algorithm can initialized with an arbitrary feasible solution, allowing it to prune unpromising branches earlier in the tree. We propose a heuristic algorithm that provides such a feasible solution based on the root node relaxation performed by the lower bound calculation described in Section 4.3.

The heuristic algorithm works on the following premise. Consider that the relaxation of the problem is solved in the root node, i.e., a lower bound sequence $\hat{\pi}^{lb}$ is computed. At each node, we attempt to solve the $\mathcal{P}_{\text{Bin-Pack}}$ problem, aiming to pack the jobs within the set of consecutive processing intervals $(\Lambda_1, \Lambda_2, \dots, \Lambda_{n(\hat{\pi}^{lb})})$ that were computed for the relaxed solution $\hat{\pi}^{lb}$. If such a solution is found, then its objective value matches $c^{\text{TEC}}(\hat{\pi}^{lb})$, and the problem is already solved at the root node. If this is not the case, then the set of intervals $(\Lambda_1, \Lambda_2, \dots, \Lambda_{n(\hat{\pi}^{lb})})$ cannot pack the jobs $\mathcal{J}$ and thus represents an infeasible instance of the $\mathcal{P}_{\text{Bin-Pack}}$ problem. Therefore, one could attempt to enlarge some of the processing intervals to accommodate all the jobs $\mathcal{J}$, hoping that if the enlargement is done in a sensitive way, then the resulting packing should lead to a solution of a similar quality as the optimal solution found for the relaxed problem. We treat the enlargement of the original bins $(\Lambda_1, \Lambda_2, \dots, \Lambda_{n(\hat{\pi}^{lb})})$ as an optimization problem that we call the *Bin-Finding problem*:

$\mathcal{P}_{\text{Bin-Find}}$ problem. Given block sizes $b_1, \dots, b_k$ solve the following ILP problem:

$$ \min z \tag{4.13} $$

subject to

$$ z \geq b_i - s_i, \quad \forall i \in \{1, \dots, k\} \tag{4.14} $$

$$ z \geq s_i - b_i, \quad \forall i \in \{1, \dots, k\} \tag{4.15} $$

$$ s_i = \sum_{j \in \mathcal{J}} x_{i,j} \cdot p_j, \quad \forall i \in \{1, \dots, k\} \tag{4.16} $$

$$ \sum_{i=1}^{k} x_{i,j} = 1, \quad \forall j \in \mathcal{J} \tag{4.17} $$

where

$$ z \in \mathbb{R}, \tag{4.18} $$

$$ s_i \in \mathbb{R}_{\ge 0} \quad \forall i \in \{1, \dots, k\}, \tag{4.19} $$

$$ x_{i,j} \in \{0, 1\} \quad \forall i \in \{1, \dots, k\}, \forall j \in \mathcal{J}. \tag{4.20} $$

The model assigns the jobs to blocks such that the maximal difference between the suggested block size $b_i$ and enlarged block size $s_i$ found is minimized. Variable $s_i$ represents the new size of the block $i$, considering all jobs $J_j$ with $x_{i,j} = 1$. To compute an initial upper bound for the B&B-SPACES, we use lengths of processing intervals $|\Lambda_1|, \dots, |\Lambda_{n(\hat{\pi}^{lb})}|$ as block sizes $b_1, \dots, b_{n(\hat{\pi}^{lb})}$ obtained from the relaxed solution $\hat{\pi}^{lb}$
computed in the root node. This way, we obtain new 'aggregated jobs', which greatly reduce the size of the problem that can be then solved efficiently by finding an optimal schedule of *aggregated jobs* with processing times $s_1, \dots, s_n(\hat{\pi}^{\text{lb}})$ using the job-interval graph from Section 4.1 under the sequence $(1, \dots, n(\hat{\pi}^{\text{lb}}))$.

# 5. Experiments

In this section, we perform numerical experiments to evaluate the efficiency of the proposed B&B-SPACES introduced above. Specifically, in Section 5.1, we compare B&B-SPACES with the ILP model of Aghelinejad et al. (2018) that does not exploit optimal state switching described in Appendix A and the former state-of-the-art ILP model introduced in Benedikt et al. (2020). Furthermore, in Section 5.2, we design larger and more complex instances with historical energy price profiles, and we investigate the effect of the different groups of the processing times.

The experiments were conducted on Intel Xeon Silver 4110 CPU 2.10 GHz processor with 100 GB of RAM. The construction of the ILP models is done in Python 3.7, and the models are solved using the Gurobi solver. The algorithm for optimal state switching is written in C# while B&B-SPACES algorithm is written in C++. Please note that only the construction of the ILP model is performed in Python, whose runtime is negligible, while the actual solution of the model is carried out using the C++ code of the Gurobi solver. Furthermore, the C# implementation of the optimal state switching problem uses a Just-in-Time (JIT) compiler, so its performance is close to the native code.

The instance generator, the specific problem instances, and source codes of the algorithms are available at https://github.com/CTU-IIG/green-scheduling-bab.

## 5.1. *Comparison to the state-of-the-art*

In this experiment, we compare our B&B-SPACES algorithm with two former state-of-the-art ILP models. The first model in this comparison is ILP-REF proposed by Aghelinejad et al. (2018), which is the former state-of-the-art model that does not use pre-processing techniques described in Appendix A. Later, an ILP model utilizing the interval-state graph for pre-processing, denoted as ILP-SPACES, was coined by Benedikt et al. (2020) and currently represents the state-of-the-art solution method.

For the comparison, we used instances with two different machine state diagrams. First, the NOSBY (i.e., no stand-by mode, depicted in Fig. 2) instances were proposed by Shrouf et al. (2014) and correspond to the state diagrams without a standby mode. Second, more complex instances with two different stand-by modes are denoted as TWOSBY, containing a total of 5 states (Benedikt et al., 2020, p. 12). For each type of machine state diagram, we generate instances with $n \in \{150, 170, 190\}$ jobs, as this is roughly the frontier of the limit of efficient computations of ILP models ILP-REF (Aghelinejad et al., 2018) and ILP-SPACES (Benedikt et al., 2020). The scheme for the generation of the dataset follows standard benchmarks (Shrouf et al., 2014; Aghelinejad et al., 2018), i.e., processing times being drawn from the discrete
<table><caption>Table 1: Comparison of upper bound ub, lower bound lb and runtime t between the algorithms.</caption><caption>Machine state transition diagram: NOSBY</caption><thead><tr><th colspan="3">Instance</th><th colspan="3">ILP-REF (Aghelinejad et al., 2018)</th><th colspan="3">ILP-SPACES (Benedikt et al., 2020)</th><th colspan="3">B&B-SPACES</th><th>P-P</th></tr><tr><th>n</th><th>h</th><th></th><th>ub [-]</th><th>lb [-]</th><th>t [s]</th><th>ub [-]</th><th>lb [-]</th><th>t [s]</th><th>ub [-]</th><th>lb [-]</th><th>t [s]</th><th>t [s]</th></tr></thead><tbody><tr><td>150</td><td>527</td><td></td><td><b>8 582</b></td><td>8 567</td><td>TLR</td><td><b>8 582</b></td><td><b>8 582</b></td><td>188</td><td><b>8 582</b></td><td><b>8 582</b></td><td>0.6</td><td>1.0</td></tr><tr><td>150</td><td>647</td><td></td><td>8 726</td><td>8 247</td><td>TLR</td><td><b>8 409</b></td><td><b>8 409</b></td><td>279</td><td><b>8 409</b></td><td><b>8 409</b></td><td>0.9</td><td>2.9</td></tr><tr><td>150</td><td>767</td><td></td><td>8 557</td><td>7 787</td><td>TLR</td><td><b>8 132</b></td><td><b>8 132</b></td><td>619</td><td><b>8 132</b></td><td><b>8 132</b></td><td>0.8</td><td>5.5</td></tr><tr><td>150</td><td>888</td><td></td><td>8 976</td><td>6 780</td><td>TLR</td><td><b>8 078</b></td><td><b>8 078</b></td><td>521</td><td><b>8 078</b></td><td><b>8 078</b></td><td>1.1</td><td>9.1</td></tr><tr><td>170</td><td>650</td><td></td><td>10 596</td><td>9 628</td><td>TLR</td><td><b>10 068</b></td><td><b>10 068</b></td><td>289</td><td><b>10 068</b></td><td><b>10 068</b></td><td>0.7</td><td>2.3</td></tr><tr><td>170</td><td>799</td><td></td><td>10 794</td><td>8 832</td><td>TLR</td><td><b>9 820</b></td><td><b>9 820</b></td><td>939</td><td><b>9 820</b></td><td><b>9 820</b></td><td>0.8</td><td>4.6</td></tr><tr><td>170</td><td>948</td><td></td><td>10 940</td><td>8 343</td><td>TLR</td><td><b>9 637</b></td><td><b>9 637</b></td><td>822</td><td><b>9 637</b></td><td><b>9 637</b></td><td>1.7</td><td>9.3</td></tr><tr><td>170</td><td>1 097</td><td></td><td>11 189</td><td>8 124</td><td>TLR</td><td><b>9 620</b></td><td><b>9 620</b></td><td>1 281</td><td><b>9 620</b></td><td><b>9 620</b></td><td>2.4</td><td>13.4</td></tr><tr><td>190</td><td>757</td><td></td><td>12 555</td><td>11 206</td><td>TLR</td><td><b>12 008</b></td><td><b>12 008</b></td><td>243</td><td><b>12 008</b></td><td><b>12 008</b></td><td>0.7</td><td>3.9</td></tr><tr><td>190</td><td>930</td><td></td><td>12 882</td><td>10 521</td><td>TLR</td><td><b>11 758</b></td><td><b>11 758</b></td><td>951</td><td><b>11 758</b></td><td><b>11 758</b></td><td>1.1</td><td>6.9</td></tr><tr><td>190</td><td>1 104</td><td></td><td>12 791</td><td>9 949</td><td>TLR</td><td><b>11 611</b></td><td><b>11 611</b></td><td>3 095</td><td><b>11 611</b></td><td><b>11 611</b></td><td>2.4</td><td>13.3</td></tr><tr><td>190</td><td>1 277</td><td></td><td>12 757</td><td>0</td><td>TLR</td><td><b>11 465</b></td><td><b>11 465</b></td><td>1 319</td><td><b>11 465</b></td><td><b>11 465</b></td><td>2.0</td><td>22.7</td></tr></tbody><tfoot><tr><td colspan="3">Average time [s]:</td><td colspan="3">&gt;3600</td><td colspan="3">879</td><td colspan="3">1.3</td><td>7.9</td></tr><tr><td colspan="3">Average optimality gap [%]:</td><td colspan="3">7.58</td><td colspan="3">0.00</td><td colspan="3">0.00</td><td></td></tr></tfoot></table>

<table><caption>Machine state transition diagram: TWOSBY</caption><thead><tr><th colspan="3">Instance</th><th colspan="3">ILP-REF (Aghelinejad et al., 2018)</th><th colspan="3">ILP-SPACES (Benedikt et al., 2020)</th><th colspan="3">B&B-SPACES</th><th>P-P</th></tr><tr><th>n</th><th>h</th><th></th><th>ub [-]</th><th>lb [-]</th><th>t [s]</th><th>ub [-]</th><th>lb [-]</th><th>t [s]</th><th>ub [-]</th><th>lb [-]</th><th>t [s]</th><th>t [s]</th></tr></thead><tbody><tr><td>150</td><td>529</td><td></td><td><b>21 910</b></td><td>21 562</td><td>TLR</td><td><b>21 910</b></td><td><b>21 910</b></td><td>133</td><td><b>21 910</b></td><td><b>21 910</b></td><td>0.9</td><td>1.1</td></tr><tr><td>150</td><td>649</td><td></td><td>29 425</td><td>20 685</td><td>TLR</td><td><b>21 821</b></td><td><b>21 821</b></td><td>705</td><td><b>21 821</b></td><td><b>21 821</b></td><td>1.2</td><td>3.1</td></tr><tr><td>150</td><td>769</td><td></td><td>37 764</td><td>18 140</td><td>TLR</td><td><b>21 353</b></td><td><b>21 353</b></td><td>957</td><td><b>21 353</b></td><td><b>21 353</b></td><td>1.3</td><td>5.2</td></tr><tr><td>150</td><td>890</td><td></td><td>43 929</td><td>16 799</td><td>TLR</td><td><b>21 266</b></td><td><b>21 266</b></td><td>718</td><td><b>21 266</b></td><td><b>21 266</b></td><td>1.4</td><td>8.5</td></tr><tr><td>170</td><td>651</td><td></td><td>27 862</td><td>25 015</td><td>TLR</td><td><b>25 807</b></td><td><b>25 807</b></td><td>811</td><td><b>25 807</b></td><td><b>25 807</b></td><td>0.8</td><td>2.6</td></tr><tr><td>170</td><td>799</td><td></td><td>39 095</td><td>21 981</td><td>TLR</td><td><b>25 518</b></td><td><b>25 518</b></td><td>1 250</td><td><b>25 518</b></td><td><b>25 518</b></td><td>1.1</td><td>5.0</td></tr><tr><td>170</td><td>948</td><td></td><td>46 083</td><td>20 709</td><td>TLR</td><td><b>25 279</b></td><td><b>25 279</b></td><td>2 925</td><td><b>25 279</b></td><td><b>25 279</b></td><td>2.2</td><td>8.5</td></tr><tr><td>170</td><td>1 096</td><td></td><td>53 177</td><td>20 091</td><td>TLR</td><td><b>25 279</b></td><td><b>25 279</b></td><td>2 088</td><td><b>25 279</b></td><td><b>25 279</b></td><td>2.0</td><td>14.1</td></tr><tr><td>190</td><td>756</td><td></td><td>38 471</td><td>27 984</td><td>TLR</td><td><b>30 563</b></td><td><b>30 563</b></td><td>808</td><td><b>30 563</b></td><td><b>30 563</b></td><td>0.9</td><td>4.2</td></tr><tr><td>190</td><td>929</td><td></td><td>46 319</td><td>26 166</td><td>TLR</td><td><b>30 224</b></td><td><b>30 224</b></td><td>1 086</td><td><b>30 224</b></td><td><b>30 224</b></td><td>2.3</td><td>7.5</td></tr><tr><td>190</td><td>1 102</td><td></td><td>53 751</td><td>24 630</td><td>TLR</td><td><b>30 224</b></td><td><b>30 224</b></td><td>2 050</td><td><b>30 224</b></td><td><b>30 224</b></td><td>1.9</td><td>13.6</td></tr><tr><td>190</td><td>1 275</td><td></td><td>61 547</td><td>0</td><td>TLR</td><td><b>30 071</b></td><td><b>30 071</b></td><td>2 490</td><td><b>30 071</b></td><td><b>30 071</b></td><td>4.5</td><td>23.7</td></tr></tbody><tfoot><tr><td colspan="3">Average time [s]:</td><td colspan="3">&gt;3600</td><td colspan="3">1 335</td><td colspan="3">1.7</td><td>8.1</td></tr><tr><td colspan="3">Average optimality gap [%]:</td><td colspan="3">34.23</td><td colspan="3">0.00</td><td colspan="3">0.00</td><td></td></tr></tfoot></table>

uniform distribution $p_j \sim U[1, 5]$ and the energy costs in each interval follows $c_i \sim U[1, 10]$ distribution. Note that even though processing times $p_j$ may seem very small, they, in fact, represent the number of intervals that are typically 15 minutes long, thus resembling a realistic benchmark. The number of intervals $\mathcal{I} = \{1, 2, \dots, h\}$ in each instance is given as $\lambda \cdot (T(\text{off}, \text{proc}) + \sum_{j \in \mathcal{I}} p_j + T(\text{proc}, \text{off}))$ where the term inside the brackets represents a lower bound on horizon length $h$ (measured in the number of equidistant intervals) and $\lambda \in \{1.3, 1.6, 1.9, 2.2\}$ is a scaling factor to inflate the scheduling horizon and to provide a room for optimization.

The results are reported in Table 1. Each row corresponds to one problem instance. In the first column *Instance*, we report the specific parameters of the particular instance, and the following three columns account for the state-of-the-art methods included in the comparison. The last column P-P denotes the
time spent in the pre-processing step involving the shortest path algorithm on the interval-state graph, as
described in Appendix A. This time, although negligible, needs to be included in the runtimes of algorithms
ILP-SPACES and B&B-SPACES as these two utilize the pre-processing step. The time limit for one instance
was set to 3600 s, TLR stands for the time limit reached. Optimal bound values are denoted in bold.

The results clearly demonstrate the power of the pre-processing step—for the NOSBY state transition di-
agram, the model ILP-REF (Aghelinejad et al., 2018) cannot solve the considered instances up to optimality,
reaching an average proved optimality gap 7.58%, whereas the algorithms ILP-SPACES and B&B-SPACES
utilizing the pre-processing (P-P) solve all instances up to optimality. More significantly, the number of
states |S| in the machine state transition diagram heavily affects the performance of ILP-REF. For example,
in instances TWOSBY, the average optimality gap of ILP-REF increases to 34.23%, while the other algo-
rithms are still able to solve all instances up to optimality within the time limit. However, it can be seen that
compiling all possible state transitions into the optimal switching problem slightly increases the complexity
of the resulting problem instance, reflected in increased runtime of ILP-SPACES wheres B&B-SPACES is
largely unaffected.

Comparing the runtimes, it can be seen that our proposed algorithm B&B-SPACES clearly improves on
the result of ILP-SPACES about a factor of 10-100×. This demonstrates the efficiency of utilizing the bin-
packing structure of the problem, heavily exploited by B&B-SPACES. However, we note that the benchmark
results reveal that, in fact, the existing strategy for dataset generation does not provide instances that are
challenging enough since all of the instances were solved in less than 10s by B&B-SPACES. Therefore, in the
following sections, we focus on understanding which combination of instance parameters makes the problem
difficult to solve, and we explore the empirical complexity of the instances utilizing real-life energy prices.

5.2. *Processing time groups with real energy costs*

In this section, we study the effect of different groups of jobs’ processing times on the computational
times required by ILP-SPACES model and B&B-SPACES algorithm. In Section 5.1, we worked with the
standard benchmark instances that assume the set of possible processing times is {1, 2, 3, 4, 5} (Shrouf et al.,
2014). Here, we also test different groups of processing times, for example, all odd {2, 4, 6, 8, 10}, two primes
{3, 7} or primes with unit job {1, 2, 3, 5, 7}. All tested processing time groups can be seen in Table 2. The
state diagram of the resource used is TWOSBY (i.e., two stand-by states, five states in total, see description
in Section 5.1). In addition, we also use real energy (electricity) prices extracted from the independent
market operator (OTE) in the Czech Republic. A part of such profile that was used is shown in Fig. 8.

The aggregated results for all instances with a fixed number of jobs *n* and processing time groups
can be seen in Table 2. First, note that ILP model ILP-SPACES solves all instances with *n* = 50 jobs
up to optimality but cannot solve all instances with *n* = 100 jobs. This also shows that former standard
benchmarks used in Section 5.1 were not that challenging since there ILP-SPACES was able to solve instances
<figure><img src="image_10.png" /><figcaption>Figure 8: Example of a 48-hour part of the energy profile with real electricity costs.</figcaption></figure>

with $n = 190$. Next, the results also suggest that the set of jobs' processing times has a significant effect on the complexity of the instances, even for ILP-SPACES. For example, with $n = 100$ jobs, all instances with $p_j \in \{2, 4\}$ were solved up to optimality, whereas for $p_j \in \{3, 7\}$ just 7 out of 20. The computational times of B&B-SPACES remain almost unaffected, except the group of processing times $\{8, 10\}$ with $n \in \{150, 200\}$ jobs, where 10 instances could not be solved up to the optimality. This surprising difficulty of these instances is also reflected in the performance of ILP-SPACES that could not find a feasible solution for any instance with $p_j \in \{8, 10\}$. The detailed look on the instances where B&B-SPACES could not prove the optimality is given in Table 3. There, for each specific unsolved instance, we see the best objective found $ub$, best proven lower bound $lb$, and a number of expanded nodes by B&B-SPACES. In all cases, the found solutions are typically provably within 0.02% of the optimality. In any case, the observed difficulty of these instances is quite remarkable—for example, in instance id=348, the absolute gap between the proven lower bound and the best solution found was only 19 units of cost. We assume that one of the sources of the difficulty would be the fact that $\{8, 10\}$ are two of the larger processing times used; thus, the relaxation procedure in lower bound computation from Section 4.3 has larger relaxation gap on average, even though $\gcd\{8, 10\} = 2 > 1$. On the other hand, instances with $p_j \in \{1, 2, \dots, 10\}$ were solved up to the optimality even when $\gcd\{1, 2, \dots, 10\} = 1$. It appears that these instances are, in fact, easier since larger variability in processing times allows us to solve the $P_{Bin-Pack}$ problem involved in primal upper bound computation more frequently, thus obtaining primal solutions matching the spaces produced by the lower bound procedure and closing the search subtrees, which is a phenomenon described further in the following section.

### 5.3. Instance hardness

The varying difficulty of instances influenced by the specific processing time group revealed in Table 2 motivates us to study average-case instance complexity in more detail. We created a new set of instances under the same protocol as in Section 5.2, however this time with $n \in \{100, 150, 200\}$ and the following new groups of processing times: $\{9, 10\}$, $\{8, 9, 10\}$, $\{8, 9\}$, $\{7, 8, 9, 10\}$, $\{7, 8\}$, $\{10\}$, $\{7, 9\}$, $\{1, 2, 10\}$. For each value of $n$ and a processing time group, we generated 20 instances. The resulting runtimes of B&B-SPACES with a time limit of 10 minutes are displayed in Fig. 9 with the logaritmic scale of the vertical axis. Each
<table><caption>Table 2: Comparison between ILP-SPACES and B&B-SPACES with respect to different processing times groups and numbers of jobs; *t* denotes the average runtime, \#o is the number of optimally solved instances, \#s is the number of instances for which a solution was found but was not proven optimal, and *gap* is the optimality gap for instances counted in \#s column; P-P denotes the pre-processing used for both compared methods.</caption><thead><tr><th colspan="2">Instance</th><th colspan="4">ILP-SPACES (Benedikt et al., 2020)</th><th colspan="4">B&B-SPACES</th><th>P-P</th></tr><tr><th>n</th><th>processing times</th><th>t [s]</th><th>#o [-]</th><th>#s [-]</th><th>gap [%]</th><th>t [s]</th><th>#o [-]</th><th>#s [-]</th><th>gap [%]</th><th>t [s]</th></tr></thead><tbody><tr><td rowspan="7">50</td><td>{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}</td><td>79.13</td><td>20</td><td>0</td><td>-</td><td>0.21</td><td>20</td><td>0</td><td>-</td><td>0.4</td></tr><tr><td>{1, 2, 3, 5, 7}</td><td>21.05</td><td>20</td><td>0</td><td>-</td><td>0.18</td><td>20</td><td>0</td><td>-</td><td>0.1</td></tr><tr><td>{2, 4, 6, 8, 10}</td><td>52.72</td><td>20</td><td>0</td><td>-</td><td>0.21</td><td>20</td><td>0</td><td>-</td><td>0.5</td></tr><tr><td>{2, 4}</td><td>6.31</td><td>20</td><td>0</td><td>-</td><td>0.18</td><td>20</td><td>0</td><td>-</td><td>0.1</td></tr><tr><td>{3, 5, 6, 7}</td><td>46.00</td><td>20</td><td>0</td><td>-</td><td>0.24</td><td>20</td><td>0</td><td>-</td><td>0.4</td></tr><tr><td>{3, 7}</td><td>46.17</td><td>20</td><td>0</td><td>-</td><td>0.24</td><td>20</td><td>0</td><td>-</td><td>0.3</td></tr><tr><td>{8, 10}</td><td>77.35</td><td>20</td><td>0</td><td>-</td><td>0.33</td><td>20</td><td>0</td><td>-</td><td>1.6</td></tr><tr><td rowspan="7">100</td><td>{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}</td><td>444.72</td><td>11</td><td>9</td><td>0.16</td><td>0.48</td><td>20</td><td>0</td><td>-</td><td>3.0</td></tr><tr><td>{1, 2, 3, 5, 7}</td><td>134.42</td><td>20</td><td>0</td><td>-</td><td>0.29</td><td>20</td><td>0</td><td>-</td><td>0.8</td></tr><tr><td>{2, 4, 6, 8, 10}</td><td>315.68</td><td>17</td><td>2</td><td>0.01</td><td>0.48</td><td>20</td><td>0</td><td>-</td><td>3.7</td></tr><tr><td>{2, 4}</td><td>136.14</td><td>20</td><td>0</td><td>-</td><td>0.24</td><td>20</td><td>0</td><td>-</td><td>0.5</td></tr><tr><td>{3, 5, 6, 7}</td><td>471.05</td><td>9</td><td>11</td><td>0.19</td><td>0.44</td><td>20</td><td>0</td><td>-</td><td>2.9</td></tr><tr><td>{3, 7}</td><td>483.35</td><td>7</td><td>13</td><td>0.16</td><td>0.40</td><td>20</td><td>0</td><td>-</td><td>2.5</td></tr><tr><td>{8, 10}</td><td>525.80</td><td>5</td><td>15</td><td>0.07</td><td>0.89</td><td>20</td><td>0</td><td>-</td><td>10.6</td></tr><tr><td rowspan="7">150</td><td>{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}</td><td>543.10</td><td>4</td><td>11</td><td>1.23</td><td>0.76</td><td>20</td><td>0</td><td>-</td><td>7.9</td></tr><tr><td>{1, 2, 3, 5, 7}</td><td>466.84</td><td>9</td><td>11</td><td>0.10</td><td>0.43</td><td>20</td><td>0</td><td>-</td><td>3.1</td></tr><tr><td>{2, 4, 6, 8, 10}</td><td>514.14</td><td>8</td><td>12</td><td>0.29</td><td>0.91</td><td>20</td><td>0</td><td>-</td><td>10.4</td></tr><tr><td>{2, 4}</td><td>278.49</td><td>14</td><td>6</td><td>0.03</td><td>0.40</td><td>20</td><td>0</td><td>-</td><td>1.8</td></tr><tr><td>{3, 5, 6, 7}</td><td>539.66</td><td>4</td><td>11</td><td>0.85</td><td>0.73</td><td>20</td><td>0</td><td>-</td><td>6.8</td></tr><tr><td>{3, 7}</td><td>581.41</td><td>2</td><td>18</td><td>0.29</td><td>0.69</td><td>20</td><td>0</td><td>-</td><td>6.1</td></tr><tr><td>{8, 10}</td><td>TLR</td><td>0</td><td>0</td><td>-</td><td>143.74</td><td>15</td><td>5</td><td>0.02</td><td>31.8</td></tr><tr><td rowspan="7">200</td><td>{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}</td><td>TLR</td><td>0</td><td>7</td><td>7.66</td><td>1.30</td><td>20</td><td>0</td><td>-</td><td>21.1</td></tr><tr><td>{1, 2, 3, 5, 7}</td><td>565.26</td><td>2</td><td>18</td><td>0.61</td><td>0.61</td><td>20</td><td>0</td><td>-</td><td>5.3</td></tr><tr><td>{2, 4, 6, 8, 10}</td><td>577.29</td><td>1</td><td>3</td><td>9.39</td><td>1.46</td><td>20</td><td>0</td><td>-</td><td>25.2</td></tr><tr><td>{2, 4}</td><td>425.80</td><td>12</td><td>8</td><td>0.15</td><td>0.52</td><td>20</td><td>0</td><td>-</td><td>3.7</td></tr><tr><td>{3, 5, 6, 7}</td><td>576.54</td><td>1</td><td>15</td><td>2.74</td><td>1.17</td><td>20</td><td>0</td><td>-</td><td>19.7</td></tr><tr><td>{3, 7}</td><td>TLR</td><td>0</td><td>19</td><td>1.32</td><td>1.09</td><td>20</td><td>0</td><td>-</td><td>17.7</td></tr><tr><td>{8, 10}</td><td>TLR</td><td>0</td><td>0</td><td>-</td><td>132.99</td><td>15</td><td>5</td><td>0.02</td><td>78.7</td></tr></tbody></table>

color represents one group of processing times, where all 60 instances belonging to each group are ordered with the increasing length of the horizon *h*, i.e., the number of intervals.

Under visual inspection, the dependence of the runtime on the length of the horizon *h* can be seen in the form of a staircase function. This is due to how the instances are generated, i.e., *h* = 1.3 times the sum of all processing times. Thus, the three steps visible in each group correspond to instances with *n* = 100, 150, and 200 jobs. However, when focusing on the instance group containing processing times 8, 9 and 10, we observe more frequently the sudden spikes in the runtime with the greatest intensity around processing time group {8, 9, 10}. The exact proportion of the instances that were not solved to the optimality (i.e., time limit reached – TLR) is shown in Fig. 10.

It appears to us that this phenomenon has an explanation following from a bin-packing structure of the problem. The real-life energy price profiles share a structure with more or less periodically repeating areas with lower average costs, interleaved by areas with intervals having higher average costs, as can be seen
<table><caption>Table 3: Detailed view the instances that were not solved by B&B-SPACES to optimality.</caption><thead><tr><th colspan="3">Instance</th><th colspan="4">B&B-SPACES</th></tr><tr><th>id</th><th>n</th><th>proc. times</th><th>ub [-]</th><th>lb [-]</th><th>gap [%]</th><th>#nodes [-]</th></tr></thead><tbody><tr><td>292</td><td>150</td><td>{8, 10}</td><td>12 352 437</td><td>12 349 218</td><td>0.026</td><td>57 457</td></tr><tr><td>320</td><td>150</td><td>{8, 10}</td><td>12 330 437</td><td>12 328 008</td><td>0.020</td><td>60 355</td></tr><tr><td>348</td><td>150</td><td>{8, 10}</td><td>12 288 440</td><td>12 288 421</td><td>0.000</td><td>52 854</td></tr><tr><td>376</td><td>150</td><td>{8, 10}</td><td>12 330 437</td><td>12 328 008</td><td>0.020</td><td>61 988</td></tr><tr><td>404</td><td>150</td><td>{8, 10}</td><td>12 074 142</td><td>12 071 713</td><td>0.020</td><td>55 328</td></tr><tr><td>432</td><td>200</td><td>{8, 10}</td><td>16 413 555</td><td>16 411 549</td><td>0.012</td><td>27 259</td></tr><tr><td>460</td><td>200</td><td>{8, 10}</td><td>16 293 105</td><td>16 290 676</td><td>0.015</td><td>30 450</td></tr><tr><td>488</td><td>200</td><td>{8, 10}</td><td>16 433 290</td><td>16 430 776</td><td>0.015</td><td>20 572</td></tr><tr><td>516</td><td>200</td><td>{8, 10}</td><td>16 123 137</td><td>16 120 217</td><td>0.018</td><td>26 673</td></tr><tr><td>544</td><td>200</td><td>{8, 10}</td><td>16 554 373</td><td>16 551 944</td><td>0.015</td><td>25 287</td></tr></tbody></table>

<figure><img src="image_11.png" /><figcaption>Figure 9: Running times sorted by horizon length, split by processing time group for $n \in \{100, 150, 200\}$ jobs.</figcaption></figure>

in Fig. 8. The algorithm that optimizes TEC avoids areas with high-priced intervals. Depending on the specific values of transition time and power functions of the machine, the solution switches between off-peak intervals, in which the resource is typically in proc state, and peak intervals, where the resource is often in idle/off states. The sets of consecutive intervals where the machine is in proc state then form bins, as it was introduced in Section 4.4. The combinatorial nature of the problem is then hidden within the task of how to fit jobs with given processing times into the bins. This aspect shows that the considered problem has deeper connections to number partitioning and bin packing problems.

Instance hardness in the context of the average-case complexity of the number partition problem (NPP) was studied by Mertens (2003). Mertens shows that NPP admits a sharp phase transition of the instances, where we quickly transition from instances that almost surely have a perfect partitioning to instances that very likely do not have one, which influences the empirical runtime of the algorithm. This transition is not directly related to the amount of the number itself, but to the specific structure of the numbers. Paradoxically, even larger problems may become easier to solve. Our problem better matches the similar analysis for parallel machine scheduling problem by Bauke et al. (2003). For $P \parallel C_{max}$ or bin-packing problem, it is notoriously known that, e.g., the presence of short jobs (items) leads to easier instances since it is easy
<figure><img src="image_12.png" /><figcaption>Figure 10: Proportion of instances that were not solved up to the optimality.</figcaption></figure>

to fill up the remaining space by the short jobs. The same applies to our problem — having larger variability in jobs' processing times, especially combined with the presence of short jobs, increases the probability of perfect partitions, i.e., situations where primal upper bound heuristic based on a packing problem matches the bins proposed by the lower bound, allowing to close nodes in the search tree earlier. In our setting, the phase transition appears to be around the group {8, 9, 10}, where the probability of encountering a hard instance increases. On the opposite extreme, when all processing times are equal (i.e., the group $p_j \in \{10\}$), all jobs become interchangeable, and since $gcd = 10$, the problem instances are easy again. Therefore, we conclude that the number of jobs $n$ in the instance is not the main limiting factor of B&B-SPACES algorithm, but rather it is the presence of long jobs with low processing time variability within the group.

# 6. Conclusion

In this work, we addressed the problem of total energy cost minimization on a single machine with different states under time-of-use tariffs. This problem, arising in production scheduling with energy-intensive manufacturing operations, plays a critical role in reducing energy bills. The importance of the problem was recognized by Shrouf et al. (2014), who coined the problem with several authors to follow (Aghelinejad et al., 2018, 2019; Benedikt et al., 2020) to follow. The breakthrough came when Benedikt et al. (2020) showed that one can simplify state transitions of the machine by solving the optimal switching problem and use precomputed switching between any pair of intervals inside an ILP model without an explicit modeling.

In this work, we took this idea one step further. We realized that the spaces suggested by the optimal switching problem could be seen as a kind of bins to which we allocate the jobs. This led to the design of a branch-and-bound algorithm B&B-SPACES that utilizes the bin packing structure by applying initial and primal heuristics and also a lower bound computation based on the polynomial-time solution of the problem for the fixed order of the jobs. We improved on the approach proposed in Aghelinejad et al. (2019) by incorporating only the optimal switching costs, leading to a much smaller job-interval graph, therefore
enabling fast lower bound computations. These insights and improvements led to achieving a new state-of-the-art performance on the standard benchmark set by two orders of magnitude, enabling the solutions of larger instances than ever possible. Furthermore, we have observed that the standard benchmark set is extremely well-suited for the bin packing structure utilized by B&B-SPACES; thus, we also designed new, much harder benchmarks considering true historical energy price profiles.

The increased efficiency of B&B-SPACES algorithm enables its use in practice where we can solve problems with horizon well over a week considering a non-trivial number of jobs quickly, enabling online recalculation of the schedule when energy prices change. Nevertheless, we acknowledge one of the limitations of our approach, which is that the considered problem statement and our algorithm assume that the energy requirements of the jobs are proportional to their processing time, i.e., the uniform energy consumption. However, we believe that our approach might be extended to support these considerations—lower bound procedure could be recovered for non-uniform energy consumption (Fang et al., 2016; Aghelinejad et al., 2019), but the bigger challenge seems to be designing an efficient primal heuristic such that it frequently finds a solution matching the lower bound, which is the key to the efficiency of B&B-SPACES.

We believe that other research may benefit from our results as well. For example, the idea of exposing the bin packing structure of the problem via the optimal switching problem and lower bound computation, suggesting the spaces that act as bins for the jobs, is particularly useful. Considering how well the bin packing problem is solvable in practice, similar problems could be accelerated as well, even when the packing structure of the problem is not exposed at first sight. Moreover, our idea of incorporating optimal switching costs into the job-interval graph led to improved complexity of the algorithm for the fixed ordering of the jobs, which could be applied to similar problems.

Finally, we outline some ideas for the extension of the problem and the methods proposed.

First, if the jobs have release times and deadlines, these would be reflected by pruning some of the edges in the job-interval graph, but some adjustments should be made to the lower and upper bound computation. Moreover, it seems to us that our approach could be extended to model machines with multiple dedicated processing states and job families, where each family could be processed only in its dedicated state (e.g., workpieces requiring different hardening temperatures). These would likely require extending the interval-state graph, but they also would introduce extra edges and vertices into the job-interval graph to model transitions between pairs of different processing states.

## Acknowledgement

This work was co-funded by the European Union under the project ROBOPROX (reg. no. CZ.02.01.01/00/22_008/0004590) and the Grant Agency of the Czech Republic under the Project GACR 25-17904S. Moreover, we would like to thank Theodor Krocan for his insightful comments.
# Appendix

## A. Computation of the Optimal State Switching

This section describes the problem of pre-computing the optimal switching between the machine states in given intervals while minimizing the power consumption introduced in Benedikt et al. (2020). After introducing the problem, we summarize the algorithm that computes the optimal switching costs in a polynomial time by finding the shortest paths in the so-called interval-state graph.

**Optimal switching problem.** Given the state $s$ in interval $i$ and state $s'$ in interval $i'$ such that $i < i'$, the problem finds the optimal transitions from $(s, i)$ to $(s', i')$ over all possible states $S$ with respect to the energy cost $c$. Formally, it represents the following optimization problem

$$ \min_{\Omega_{i+1}, \Omega_{i+2}, \dots, \Omega_{i'-1}} \sum_{j=i+1}^{i'-1} c_j \cdot P(\Omega_j). \qquad (A1) $$

such that $((s, s), \Omega_{i+1}, \Omega_{i+2}, \dots, \Omega_{i'-1}, (s', s'))$ form permissible transitions according to transition time function $T$.

**Interval-state graph.** It was shown that the optimal switching problem can be solved in polynomial time by finding the shortest path in an interval-state graph (Benedikt et al., 2020). The interval-state graph $G^{\text{is}}$ is defined by a triplet $G^{\text{is}} = (V^{\text{is}}, E^{\text{is}}, w^{\text{is}})$, where $V^{\text{is}}$ is the set of vertices, $E^{\text{is}}$ is the set of edges and $w^{\text{is}}: E^{\text{is}} \to \mathbb{Z}$ are the weights of the edges. Given time horizon $h$, the sets $V^{\text{is}}$ and $E^{\text{is}}$ are given as:

$$ V^{\text{is}} = \{v_{1,\text{off}}^{\text{is}}, v_{h+1,\text{off}}^{\text{is}}\} \cup \{v_{i,s}^{\text{is}} : i \in \mathcal{I} \setminus \{1\}, s \in S\}, \qquad (A2) $$

$$ E^{\text{is}} = \{(v_{1,\text{off}}^{\text{is}}, v_{2,\text{off}}^{\text{is}})\} \cup \{(v_{h,\text{off}}^{\text{is}}, v_{h+1,\text{off}}^{\text{is}})\} \qquad (A3) \\ \cup \{(v_{i,s}^{\text{is}}, v_{i+T(s,s'),s'}^{\text{is}}) : s, s' \in S, i \in \mathcal{I} \setminus \{1\}, T(s, s') \neq \infty, (i-1) + T(s, s') \leq h-1\}. $$

Each vertex $v_{i,s}^{\text{is}} \in V^{\text{is}}$ represents that at the beginning of interval $i$ the machine is in state $s$. Each edge $(v_{i,s}^{\text{is}}, v_{i',s'}^{\text{is}}) \in E^{\text{is}}$ corresponds to the direct transition from state $s$ to state $s'$ that lasts $T(s, s') = (i' - i)$ intervals. The condition $(i - 1) + T(s, s') \leq h - 1$ ensures, that only transitions completing at most at the beginning of interval $h$ are present in the interval-state graph. Weight of edge $(v_{i,s}^{\text{is}}, v_{i',s'}^{\text{is}}) \in E^{\text{is}}$ is defined as

$$ w^{\text{is}}(v_{i,s}^{\text{is}}, v_{i',s'}^{\text{is}}) = \sum_{j=i}^{i'-1} c_j \cdot P(s, s'), \qquad (A4) $$

i.e., the total energy cost of the corresponding transition with respect to the costs of energy in intervals.

The optimal transitions from $(s, i)$ to $(s', i')$ with respect to the energy cost can be obtained by finding the shortest path from $v_{i+1,s}^{\text{is}}$ to $v_{i',s'}^{\text{is}}$ in the interval-state graph. We denote the cost of the optimal switching by function $l^{\text{is}}: V^{\text{is}} \times V^{\text{is}} \to \mathbb{Z} \cup \{\infty\}$, where the value $\infty$ is used whenever the path between the two vertices does not exist. Basically, the interval-state graph is a layered graph that can be seen as a time expansion
of the transition time function $T$ along the horizon defined by intervals $\mathcal{I}$, with weights derived from power function $P$ and energy cost $c$. See (Benedikt et al., 2020) for an example of an interval-state graph.

**Example 4:** Consider an interval-state graph representing problem instance from Fig. 1 with a transition graph from Example 1. For example, the optimal transition of the machine from proc state at interval 8 to proc state at interval 14 looks as follows. At first, the machine is turned off (during 9), then it remains off (during intervals 10 and 11), and finally, it is turned on (intervals 12, 13). The cost for this whole path is $l^{\text{is}}(v_{9,\text{proc}}^{\text{is}}, v_{14,\text{proc}}^{\text{is}}) = 76$.

The values of $l^{\text{is}}$ can be computed using the Floyd-Warshall algorithm that computes all-pairs shortest path between $n$ vertices of the given directed graph in $O(n^3)$ steps by iteratively updating the length of the shortest path between every pair of vertices $i$ and $j$, using only vertices $\{1, 2, \dots, k\}$. When $k = n$, the algorithm finishes with the optimal values of all-pairs shortest path. The interval-state graph $G^{\text{is}}$ has at most $h \cdot |S|$ vertices, where $h$ is the length of the horizon (number of considered intervals) and $|S|$, is the number of the states of the resource; therefore, the total running time can be upper bounded as $O(h^3 \cdot |S|^3)$.

However, only some of the switchings can be considered for scheduling decisions. Since all the jobs need to be scheduled in the proc state of the machine, the optimal switchings have to be resolved only in (i) between two consecutive intervals with proc; (ii) between the first off and the first proc; and (iii) the last proc and the last off. The cost of the switchings between $s, s' \in \{\text{off}, \text{proc}\}^2$ are specified by function $c^*(i, i') : \mathcal{I}^2 \to \mathbb{Z}$ defined as

$$c^*(i, i') = \begin{cases} l^{\text{is}}(v_{i+1,\text{proc}}^{\text{is}}, v_{i',\text{proc}}^{\text{is}}) & i > 1, i' < h \quad \text{case (i)} \\ l^{\text{is}}(v_{2,\text{off}}, v_{i',\text{proc}}^{\text{is}}) & i = 1, i' < h \quad \text{case (ii)} \\ l^{\text{is}}(v_{i+1,\text{proc}}^{\text{is}}, v_{h,\text{off}}^{\text{is}}) & i > 1, i' = h \quad \text{case (iii)} \end{cases} \quad (A5)$$

for each pair of intervals $i < i'$. The vector of states corresponding to $c^*(i, i')$, i.e., the optimal switching behavior of the machine between $i$ and $i'$, is denoted by $\Omega^*(i, i')$.

**Example 4 (continued):** For the illustration, see the Fig. 1. There, intervals $\{9, 10, \dots, 13\}$ represent the space between two jobs $J_2, J_1$ with cost $c^*(8, 14) = l^{\text{is}}(v_{9,\text{proc}}^{\text{is}}, v_{14,\text{proc}}^{\text{is}}) = 76$.

The optimal switching behavior is

$$\Omega^*(8, 14) = ((\text{proc}, \text{off}), (\text{off}, \text{off}), (\text{off}, \text{off}), (\text{off}, \text{proc}), (\text{off}, \text{proc})). \quad (A6)$$

Values of $c^*$ can be computed efficiently using the algorithm called the Shortest Path Algorithm for Cost Efficient Switchings (SPACES) (Benedikt et al., 2020). For each value $i \in \mathcal{I} \setminus \{h\}$, SPACES computes all values $c^*(i, i+1), c^*(i, i+2), \dots, c^*(i, h)$ by computing the shortest paths tree from $v_{i+1,\text{proc}}^{\text{is}}$ (or $v_{2,\text{off}}^{\text{is}}$ if $i=1$) to all other vertices in the interval-state graph. If all weights $w^{\text{is}}$ happen to be nonnegative (e.g., when energy cost $c \ge 0$), then the shortest path tree is obtained with the Dijkstra algorithm that runs in
$O(|E^{is}| + |V^{is}| \cdot \log |V^{is}|)$. Since the Dijkstra algorithm is started $h$ times, the total complexity is

$$O(h \cdot (|E^{is}| + |V^{is}| \cdot \log |V^{is}|)) = O(h^2 \cdot |S| \cdot (|S| + \log h + \log |S|)). \quad (A7)$$

In case of the presence of negative weights $w^{is}$, one has to resort to the Bellman-Ford algorithm with complexity $O(|V^{is}| \cdot |E^{is}|)$, thus in total, the complexity would be $O(h^3 \cdot |S|^3)$.

## References

Abikarram, J. B., McConky, K., & Proano, R. (2019). Energy cost minimization for unrelated parallel machine scheduling under real time and demand charge pricing. *Journal of Cleaner Production*, 208, 232–242. doi:https://doi.org/10.1016/j.jclepro.2018.10.048.

Aghelinejad, M., Ouazene, Y., & Yalaoui, A. (2018). Production scheduling optimisation with machine state and time-dependent energy costs. *International Journal of Production Research*, 56, 5558–5575. doi:10.1080/00207543.2017.1414969.

Aghelinejad, M. et al. (2019). Complexity analysis of energy-efficient single machine scheduling problems. *Operations Research Perspectives*, 6, 100105. URL: https://www.sciencedirect.com/science/article/pii/S2214716018301702. doi:https://doi.org/10.1016/j.orp.2019.100105.

Aghelinejad, M. M., Masmoudi, O., Ouazene, Y., & Yalaoui, A. (2020a). Multi-state two-machine permutation flow shop scheduling optimisation with time-dependent energy costs. *IFAC-PapersOnLine*, 53, 11156–11161. URL: https://www.sciencedirect.com/science/article/pii/S2405896320305711. doi:https://doi.org/10.1016/j.ifacol.2020.12.291. 21st IFAC World Congress.

Aghelinejad, M. M., Ouazene, Y., & Yalaoui, A. (2017). Preemptive scheduling of a single machine with finite states to minimize energy costs. In A. Sforza, & C. Sterle (Eds.), *Optimization and Decision Science: Methodologies and Applications* (pp. 591–599). Cham: Springer International Publishing.

Aghelinejad, M. M., Ouazene, Y., & Yalaoui, A. (2020b). Energy-cost-aware flow-shop scheduling systems with state-dependent energy consumptions. In *IOP Conference Series: Earth and Environmental Science* (p. 012163). IOP Publishing volume 463.

Aghelinejad, M. M., Ouazene, Y., & Yalaoui, A. (2020c). Energy-cost-aware flow-shop scheduling systems with state-dependent energy consumptions. *IOP Conference Series: Earth and Environmental Science*, 463, 012163. URL: https://dx.doi.org/10.1088/1755-1315/463/1/012163. doi:10.1088/1755-1315/463/1/012163.

Anghinolfi, D., Paolucci, M., & Ronco, R. (2021). A bi-objective heuristic approach for green identical parallel machine scheduling. *European Journal of Operational Research*, 289, 416–434.

Bauke, H., Mertens, S., & Engel, A. (2003). Phase transition in multiprocessor scheduling. *Physical review letters*, 90, 158701.

Benedikt, O., Alikoç, B., Šúcha, P., Čelikovský, S., & Hanzálek, Z. (2021). A polynomial-time scheduling approach to minimise idle energy consumption: An application to an industrial furnace. *Computers & Operations Research*, 128, 105167. URL: https://www.sciencedirect.com/science/article/pii/S0305054820302847. doi:https://doi.org/10.1016/j.cor.2020.105167.

Benedikt, O., Módos, I., & Hanzálek, Z. (2020). Power of pre-processing: production scheduling with variable energy pricing and power-saving states. *Constraints*, 25, 300–318.

Bukata, L., Šúcha, P., & Hanzálek, Z. (2019). Optimizing energy consumption of robotic cells by a branch & bound algorithm. *Computers & Operations Research*, 102, 52–66. URL: https://www.sciencedirect.com/science/article/pii/S0305054818302533. doi:https://doi.org/10.1016/j.cor.2018.09.012.

Catanzaro, D., Pesenti, R., & Ronco, R. (2023). Job scheduling under time-of-use energy tariffs for sustainable manufacturing:
a survey. *European Journal of Operational Research*, **308**, 1091–1109. URL: https://www.sciencedirect.com/science/article/pii/S0377221723000474. doi:https://doi.org/10.1016/j.ejor.2023.01.029.

Chen, B., & Zhang, X. (2019). Scheduling with time-of-use costs. *European Journal of Operational Research*, **274**, 900–908.
URL: https://www.sciencedirect.com/science/article/pii/S0377221718309275. doi:https://doi.org/10.1016/j.ejor.2018.11.002.

Chen, L., Megow, N., Rischke, R., Stougie, L., & Verschae, J. (2021). Optimal algorithms for scheduling under time-of-use tariffs. *Annals of Operations Research*, **304**, 85–107.

Cheng, J., Chu, F., & Zhou, M. (2018). An improved model for parallel machine scheduling under time-of-use electricity price. *IEEE Transactions on Automation Science and Engineering*, **15**, 896–899. doi:10.1109/TASE.2016.2631491.

Ding, J., Schulz, S., Shen, L., Buscher, U., & Lü, Z. (2021). Energy aware scheduling in flexible flow shops with hybrid particle swarm optimization. *Computers & Operations Research*, **125**, 105088. URL: https://www.sciencedirect.com/science/article/pii/S0305054820302057. doi:https://doi.org/10.1016/j.cor.2020.105088.

Eid, C., Koliou, E., Valles, M., Reneses, J., & Hakvoort, R. (2016). Time-based pricing and electricity demand response: Existing barriers and next steps. *Utilities Policy*, **40**, 15–25.

Fang, K. et al. (2016). Scheduling on a single machine under time-of-use electricity tariffs. *Annals of Operations Research*, **238**, 199–227. URL: https://doi.org/10.1007/s10479-015-2003-5. doi:10.1007/s10479-015-2003-5.

Fatih Tasgetiren, M., Öztop, H., Eliiyi, U., Eliiyi, D. T., & Pan, Q.-K. (2018). Energy-efficient single machine total weighted tardiness problem with sequence-dependent setup times. In *Intelligent Computing Theories and Application: 14th International Conference, ICIC 2018, Wuhan, China, August 15-18, 2018, Proceedings, Part I* 14 (pp. 746–758). Springer.

Gaggero, M., Paolucci, M., & Ronco, R. (2023). Exact and heuristic solution approaches for energy-efficient identical parallel machine scheduling with time-of-use costs. *European Journal of Operational Research*, **311**, 845–866.

Gnatowski, A., Rudy, J., & Idzikowski, R. (2022). Scheduling disjoint setups in a single-server permutation flow shop manufacturing process. *Processes*, **10**, 1837.

Grus, J., Hanen, C., & Hanzálek, Z. (2024). Packing-inspired algorithms for periodic scheduling problems with harmonic periods. In *Proceedings of the 13th International Conference on Operations Research and Enterprise Systems - ICORES* (pp. 101–112). INSTICC SciTePress. doi:10.5220/0012325800003639.

Ho, M. H., Hnaien, F., & Dugardin, F. (2022). Exact method to optimize the total electricity cost in two-machine permutation flow shop scheduling problem under time-of-use tariff. *Computers & Operations Research*, **144**, 105788.

Li, W., & Ou, J. (2024). Approximation algorithms for scheduling parallel machines with an energy constraint in green manufacturing. *European Journal of Operational Research*, **314**, 882–893. URL: https://www.sciencedirect.com/science/article/pii/S0377221723008470. doi:https://doi.org/10.1016/j.ejor.2023.11.008.

Maris, G., & Flouros, F. (2021). The green deal, national energy and climate plans in Europe: Member States' compliance and strategies. *Administrative Sciences*, **11**, 75.

Mertens, S. (2003). The easiest hard problem: Number partitioning. URL: https://arxiv.org/abs/cond-mat/0310317. arXiv:cond-mat/0310317.

Minh Hung, H., Hnaien, F., & Dugardin, F. (2020). Electricity cost minimisation for optimal makespan solution in flow shop scheduling under time-of-use tariffs. *International Journal of Production Research*, (pp. 1–27). doi:10.1080/00207543.2020.1715504.

Mouzon, G., Yildirim, M. B., & Twomey, J. (2007). Operational methods for minimization of energy consumption of manufacturing equipment. *International Journal of Production Research*, **45**, 4247–4271. doi:10.1080/00207540701450013.

Nattaf, M., Artigues, C., & Lopez, P. (2017). Cumulative scheduling with variable task profiles and concave piecewise linear processing rate functions. *Constraints*, **22**, 530–547.

Ngueveu, S. U., Artigues, C., Absi, N., & Kedad-Sidhoum, S. (2022). Lower and upper bounds for scheduling energy-consuming
tasks with storage resources and piecewise linear costs. *Journal of Heuristics*, **28**, 93–120.

Park, M.-J., & Ham, A. (2022). Energy-aware flexible job shop scheduling under time-of-use pricing. *International Journal of Production Economics*, **248**, 108507.

Pei, Z., Wan, M., Jiang, Z.-Z., Wang, Z., & Dai, X. (2021). An approximation algorithm for unrelated parallel machine scheduling under time-of-use tariffs. *IEEE Transactions on Automation Science and Engineering*, **18**, 743–756. doi:10.1109/TASE.2020.2995078.

Rego, M. F., Pinto, J. C. E., Cota, L. P., & Souza, M. J. (2022). A mathematical formulation and an nsga-ii algorithm for minimizing the makespan and energy cost under time-of-use electricity price in an unrelated parallel machine scheduling. *PeerJ Computer Science*, **8**, e844.

Rocholl, J., Mönch, L., & Fowler, J. (2020). Bi-criteria parallel batch machine scheduling to minimize total weighted tardiness and electricity cost. *Journal of Business Economics*, **90**, 1345–1381.

Shrouf, F., Ordieres-Meré, J., García-Sánchez, A., & Ortega-Mier, M. (2014). Optimizing the production scheduling of a single machine to minimize total energy consumption costs. *Journal of Cleaner Production*, **67**, 197–207. doi:10.1016/j.jclepro.2013.12.024.

Tian, Z., & Zheng, L. (2024). Single machine parallel-batch scheduling under time-of-use electricity prices: New formulations and optimisation approaches. *European Journal of Operational Research*, **312**, 512–524.

Wan, G., & Qi, X. (2010). Scheduling with variable time slot costs. *Naval Research Logistics (NRL)*, **57**, 159–171.

Wang, L. et al. (2020). Multi-objective optimization based on decomposition for flexible job shop scheduling under time-of-use electricity prices. *Knowledge-Based Systems*, **204**, 106177.

Wu, P. et al. (2023). Energy-efficient single-machine scheduling with release dates under time-of-use electricity tariffs. *Journal of Cleaner Production*, **393**, 136228. URL: https://www.sciencedirect.com/science/article/pii/S0959652623003864. doi:https://doi.org/10.1016/j.jclepro.2023.136228.