# Synchronising Lot Sizing and Job Scheduling

Aurélien Mombelli, Alain Quilliot

► To cite this version:

Aurélien Mombelli, Alain Quilliot. Synchronising Lot Sizing and Job Scheduling. SOICT 2023: The 12th International Symposium on Information and Communication Technology, School of Information and Communication Technology – Hanoi University of Science and Technology, Hochiminh University of Science – Vietnam National University, Dec 2023, Ho Chi Minh Vietnam, France. pp.647-654, 10.1145/3628797.3628803 . hal-05042007

HAL Id: hal-05042007

https://cnrs.hal.science/hal-05042007v1

Submitted on 23 Apr 2025

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

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

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

Distributed under a Creative Commons Attribution 4.0 International License
# Synchronising Lot Sizing and Job Scheduling

Aurélien Mombelli, Alain Quilliot

Université Clermont Auvergne, CNRS, Clermont Auvergne INP, Mines Saint-Etienne, LIMOS

63000 Clermont-Ferrand, France

firstname.lastname@uca.fr

## ABSTRACT

We deal here with the production by a subcontractor of resources that a final job scheduler will use to achieve a sequence of jobs. Both are provided with limited storage capacities and must synchronise respective production and consumption processes. The resulting scheduling problem appears, from the point of view of the resource producer, as a multi-stage Lot Sizing problem, where every stage has to be delimited by transfers, which become the core of the decision. Such a problem may typically arise in contexts when the resource is some renewable energy (hydrogen, photo-voltaic, ...) required by the jobs and stored inside tanks or batteries. We first set the SLSS: Synchronised Lot Sizing/Scheduling problem in the MILP format and handle it through branch and cut. Next, we get rid of the non {0, 1} decision variables by applying Benders' cut generation. Finally, we reformulate the SLSS problem as a path search problem set in a specific Transfer space and handle it through an adaptation of the A* algorithm.

## CCS CONCEPTS

* Applied computing → Transportation; Supply chain management; Computing methodologies → Discrete space search; Heuristic function construction; Planning for deterministic actions.

## KEYWORDS

Lot Sizing, Scheduling, MILP, Benders' Decomposition, Path Search, A* Algorithm

### ACM Reference Format:

Aurélien Mombelli, Alain Quilliot. 2023. Synchronising Lot Sizing and Job Scheduling. In *The 12th International Symposium on Information and Communication Technology (SOICT 2023), December 7–8, 2023, Ho Chi Minh, Vietnam*. ACM, New York, NY, USA, 8 pages. https://doi.org/10.1145/3628797.3628803

## 1 INTRODUCTION

Lot Sizing arises when one actor schedules production while taking care of avoiding strong activation costs (see [3, 5]). Part of a Lot Sizing strategy is to concentrate production on well-chosen periods in order to minimise those activation costs. In standard contexts, production is delivered to customers at the end of some fixed periods. Meanwhile, it is stored under capacity constraints

<figure><img src="image_2.png" /><figcaption>Figure 1: Feeder/Eater interaction process</figcaption></figure>

and storage costs. The resulting problems look like Knapsack problems involving a temporal dimension (see [13]). One often handles them through dynamic programming, which may yield FPTAS: Fully Polynomial Time Approximation Scheme. Multi-dimensional Lot Sizing (see [20]) means a heterogeneous production and different kinds of capacity constraints (weight, volume, ...). Multi-level Lot Sizing (see [4, 8, 10]) means several players acting on the same system (for instance a main resource producer and several subcontractors). Those players may be partially independent of each other, raising the collaborative issue and leading to Cooperative Games or multi-objective reformulations. In addition, one may have to take care of contextual changes as in multi-stage Lot Sizing (see [12]). In all those cases, the resulting problems are NP-Hard.

Now it may happen that such a process involves an interaction between the resource producer and a (several) job scheduler(s), both provided with their own agenda. It will be the case if the resource producer is a sub-contractor which provides the job scheduler(s) with resources that this job scheduler needs in order to achieve his own tasks. Let us for instance consider (see Figure 1) a local energy producer Feeder which produces energy all along N periods i = 0, ..., N − 1 with identical duration but different production levels Ri and costs Ci. This energy producer interacts with a job scheduler Eater who must perform jobs j = 0, ..., M − 1, each job requiring some energy and some time units. Feeder must decide about a production activation vector z = (z$_{i}$ ∈ {0, 1}, i = 0, ..., N − 1), solution of the following model:

$$ \{\text{Minimise} \sum_{i} C_{i} \cdot z_{i} \text{ such that } \sum_{i} R_{i} \cdot z_{i} \geq \text{Total\_Cons}\} $$

where Total\_Cons is the total amount of energy requested by Eater.

<footnote>Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org.</footnote>

<footnote>SOICT 2023, December 7–8, 2023, Ho Chi Minh, Vietnam</footnote>

<footnote>© 2023 Copyright held by the owner/author(s). Publication rights licensed to ACM.</footnote>

<footnote>ACM ISBN 979-8-4007-0891-6/23/12...$15.00</footnote>

<footnote>https://doi.org/10.1145/3628797.3628803</footnote>
On the other side, Eater's must schedule the jobs $j = 0, \dots, M-1$, while optimizing its own criterion (for instance the makespan), meeting temporal constraints and, every time it starts performing a job $j$, providing this job with some energy amount.

In order to implement this production/consumption process, Feeder and Eater must agree about a period $i$ and a job $j$ after when Feeder transfers some energy amount $m$ to Eater. Such a transfer $\omega = (i, j, m)$ usually requires an additional cost, together with additional time and energy amount from both players. Also, in many cases, it forbids energy production or job processing. Therefore, the production period $i$ is fully used for the transfer and a waiting time between the end of job $j$ and the start of period $i$ may be needed to synchronise the two actors. According to this, we get a full description of our process if we know, besides Feeder production vector $z$ and Eater schedule, the collection of all transfers $\omega = (i, j, m)$ which make both players meet.

Since both Feeder and Eater are most often constrained by limited storage capacities, Feeder's and Eater's decision problems decompose themselves into a sequence Lot Sizing and scheduling stages, delimited by the periods $i$ and the jobs $j$ when transfers take place. Thus, synchronising related Feeder and Eater processes becomes the key issue.

Resulting complex bi (multi-)level Lot Sizing and Job Scheduling problem with synchronization constraints may arise in contexts related not only to energy management (see [2, 11, 17, 18]), but also to real-time cooperation between sensors and robots, between electric vehicles and recharge facilities (see [6, 16]) or to supply chain planning and asset management (see [1, 15, 19, 21]). It does not always identify in a natural way a leader and a follower, and raises the centralized versus collaborative issue.

Because of the complexity of our problem, we restrict ourselves to the resource producer's point of view and suppose that jobs $j = 0, \dots, M-1$ are scheduled according to this order so that the only scheduling decision is about their starting times. This simplification can modelize some real world assembly like applications where operations must be done in a specific order. The simplification can also be used as a sub-problem with fixed schedule and used in a bi-level optimisation scheme. Resulting SLSS: Synchronised Lot Sizing/Scheduling problem, becomes a core problem for the synchronised management of multi-players processes such as previously described. Though the centralized versus collaborative issue is crucial in practice, we stick here to the centralized paradigm and focus on the structural features of our model. We make first appear the central role played by the transfers that define chains inside some partially ordered set and induce some No-Antichain constraints inside MILP: Mixed Integer Linear Programming formulations. Next, we get rid of non-combinatorial variables while relying on Benders' decomposition (see [4, 14]). Finally, we reformulate our SLSS problem as a path search problem inside some transfer network.

So the paper is organised as follows. We first provide a formal description of the SLSS problem, and briefly discuss some variants. In Section 3, we propose a branch and cut-oriented MILP formulation of SLSS which requires the separation of some No-Antichain constraints. We introduce in Section 4 additional valid constraints, restricted to the decision variables and handled through the application of Benders' decomposition. Section 5 is devoted to a path search algorithm which allows us to show that SLSS can be solved

in pseudo-polynomial. We conclude with a brief discussion about the collaborative issue.

## 2 THE SLSS: SYNCHRONISED LOT SIZING/SCHEDULING PROBLEM

We implicitly refer here to the above energy example, with similar notations. So we consider:

* A Job Scheduler: It must perform $M$ jobs $j = 0, \dots, M-1$, according to this order. Running a job $j$ requires $r_j$ resource units and $t_j$ time units. It is provided with a resource storage facility, with capacity $C^E$ and an initial load equal to $C_0^E$. It must end with a load at least equal to $C_0^E$. It wants to minimise the ending time of job $M-1$.

* A Resource Producer: The time horizon is divided into $N$ periods, all with equal duration $p$. During a period $i$, this resource producer may be active or idle. If it is active, then it produces $R_i$ resources, under a variable running cost $Cost_i^{prod}$. If it is idle, then turning it into active induces an additional fixed activation cost $Cost_i^{act}$. It is provided with a resource storage facility, with capacity $C^F$ and initial load $C_0^F$. It cannot produce if the resulting load exceeds $C^F$. It must end with a load at least equal to $C_0^F$ and wants to minimise its production cost.

* Resource Transfers: From time to time, the resource producer must transfer resources to the job scheduler. Such a transfer takes place between the end of some job $j$ and the beginning of its successor $j+1$ and requires from the job scheduler $\epsilon_j$ additional resources, $d_j$ additional time and a potential waiting time to be spent before the transfer takes place. In order to allow transfers before job 0 or after job $M-1$, we introduce 2 fictitious jobs $-1$ and $M$. Performing a transfer requires a full period $i$, during which production is forbidden. So a transfer $\omega$ comes as a 3-tuple $(i, j, m)$, where $m \le Inf(C^E, C^F)$ is the related number of resources. $m$ values are integers if all production amounts and stock capacities are integers. We denote by $\Omega$ the set of all possible transfers.

Solving the SLSS: Synchronised Lot Sizing/Scheduling problem means, in a natural way, computing the resource production periods, the starting times of the jobs, and the transfers which link both players in such a way that:

* All jobs are done.

* Capacity constraints, job resource requirements and final state constraints are met.

* Some generalised cost $\alpha.ProdCost + \beta.T$ is minimised, where ProdCost means the total production cost and $T$ the ending time of job $M-1$.

Before keeping on with a MILP setting and its structural analysis, let us present an example and briefly discuss possible variants.

### 2.1 An Example

Let us set $M = 5$, $N = 7$, $p = 5$, $C^E = 6$, $C^F = 10$, $C_0^E = 3$, $C_0^F = 2$, $\alpha = 2$, $\beta = 1$, and vectors $t, \tau, r, \epsilon, R, Cost^{act}, Cost^{prod}$ as in Table 1. Then, we get a feasible solution with:
<table><caption>Job Scheduler</caption><thead><tr><th>j</th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th></tr></thead><tbody><tr><th>r<sub>j</sub></th><td>2</td><td>4</td><td>1</td><td>2</td><td>3</td></tr><tr><th>&epsilon;<sub>j</sub></th><td>1</td><td>1</td><td>2</td><td>1</td><td>2</td></tr><tr><th>t<sub>j</sub></th><td>3</td><td>4</td><td>2</td><td>1</td><td>7</td></tr><tr><th>d<sub>j</sub></th><td>1</td><td>2</td><td>1</td><td>1</td><td>2</td></tr></tbody></table>

<table><caption>Resource Producer</caption><thead><tr><th>i</th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th></tr></thead><tbody><tr><th>R<sub>i</sub></th><td>5</td><td>2</td><td>4</td><td>5</td><td>4</td><td>2</td><td>5</td></tr><tr><th>Cost<sup>act</sup><sub>i</sub></th><td>4</td><td>1</td><td>5</td><td>2</td><td>6</td><td>1</td><td>8</td></tr><tr><th>Cost<sup>prod</sup><sub>i</sub></th><td>5</td><td>5</td><td>6</td><td>5</td><td>3</td><td>4</td><td>6</td></tr></tbody></table>

<table><caption>Transfers</caption><thead><tr><th>i</th><th>1</th><th>4</th></tr></thead><tbody><tr><th>j</th><td>0</td><td>2</td></tr><tr><th>m</th><td>7</td><td>8</td></tr></tbody></table>

<caption>**Table 1:** An instance of the problem and a feasible solution</caption>

* Two transfers (1, 0, 7), (4, 2, 8):
  At period 1, the resource producer transfers 7 resource units to the job scheduler at the end of job 0, and at period 4, it transfers 8 resource units at the end of job 2.

* The production vector $z = (1, 0, 1, 1, 0, 1, 0)$.

* The job starting time vector $T = (0, 10, 14, 25, 32)$.

This solution induces the activation cost $Cost^{act} = 4 + 5 + 1 = 10$, production cost $Cost^{prod} = 5 + 6 + 5 + 4 = 20$ and the ending time $T = 39$. The global cost $\alpha.(Cost^{act} + Cost^{prod}) + \beta.T = 2(10+20)+39 = 99$.

## 2.2 SLSS Variants: Discussion

Depending on the application context, the above model may have to be adapted:

**Lot Sizing Production modes:** The lot sizing feature is contained in the fixed activation cost $Cost_i^{act}$, which induces an incentive to produce resources according to consecutive periods. But we might have used standard lot sizing mode, where the production level at any active period is part of the decision, inducing a cost equal to a fixed cost augmented with a concave cost function of this production level. Also, we could have involved purchases and sales operations, as in the management of a photo-voltaic power platform.

**Transfer modes:** A transfer may require less than a period or, conversely, several periods (case of power into batteries). Also, transfer and production may not be exclusive.

**job scheduler modes:** Here, we restrict the job scheduler's decision to the jobs' starting times. Of course, in practice, scheduling the jobs is part of the problem. Also, it may happen that the jobs are linked with stations to be visited in a pre-determined order. Then, the job scheduler's decision consists in performing or not those jobs with the purpose of achieving some kind of utility threshold.

# 3 A MILP FORMULATION OF THE SLSS PROBLEM

Transfers $(i, j, m)$ are going to be the key point inside any SLSS algorithmic solution. In order to better identify eligible pairs $(i, j)$ we need some additional definitions.

## 3.1 Additional Notations and Definitions

**3.1.1 Resource consumption and time between two transfers:** For any job pair $(j_1, j_2)$ s.t. $0 \le j_1 < j_2 \le M - 1$ we denote by

$\mu(j_1, j_2) = \epsilon_{j_2} + \sum_{j_1+1 \le j \le j_2} r_j$ the resource required between two transfers respectively related to $j_1$ (just after $j_1$) and $j_2$ (just after $j_2$). We extend this definition to $j_1 = -1$ and $j_2 = M$:

* $\mu(-1, j)$ expresses the resource consumed between the start of the process and the first transfer in case this transfer occurs just after $j$. It involves the term $\epsilon_j$:

$$ \mu(-1, j) = \epsilon_j + \sum_{j'=0}^{j} r_{j'} $$

* $\mu(j, M)$ expresses the resource consumed between the last transfer in case this transfer occurs just after $j$ and the end of the process. It does not involve the term $\epsilon_j$:

$$ \mu(j, M) = \sum_{j'=j+1}^{M-1} r_{j'} $$

By the way, $\Delta(j_1, j_2) = d_{j_2} + \sum_{j_1+1 \le j \le j_2} t_j$ means the time required between two transfers respectively related to $j_1$ and $j_2$. We extend this definition to $j_1 = -1$ and $j_2 = M$:

* $\Delta(-1, j)$ expresses the minimal time between the start of the process and the first transfer in case this transfer occurs just after $j$. It involves the term $d_j$:

$$ \Delta(-1, j) = d_j + \sum_{j'=0}^{j} t_{j'} $$

* $\Delta(j, M)$ expresses the time required between the last transfer in case this transfer occurs just after $j$ and the end of the process. It does not involve the term $d_j$:

$$ \Delta(j, M) = \sum_{j'=j+1}^{M-1} t_{j'} $$

**3.1.2 Ordered set ($\Lambda$, $\ll$):** This set represents all period-job pairs. We set $(i_1, j_1) \ll (i_2, j_2)$ if and only if a transfer related to period $i_2$ and job $j_2$ can be preceded by a transfer between period $i_1$ and job $j_1$. That means if $(i_2 - i_1 - 1).p \ge \Delta(j_1, j_2)$. The $\ll$ relation defines a partial order relation on $\Lambda$. We complete $\Lambda$ and $\ll$ in a natural way with the pairs $(-1, -1)$ and $(N, M)$, respectively minimum and maximum elements in $\Lambda$ for $\ll$. A $\ll$-Antichain is any subset of $\Lambda$ made of pairs $(i, j)$ pairwise incomparable in the sense of $\ll$. In such a subset, only one pair $(i, j)$ can be involved in an SLSS solution. For example, for any instances, two pairs $(i_1, j_1)$ and $(i_2, j_2)$ such that $i_1 > i_2$ and $j_1 < j_2$ are incomparable in the sense of $\ll$ and cannot be used in the same SLSS solution.

### 3.1.3 Additional notations:

* We set $\tau_m(j) = \left\lfloor \frac{\sum_{k \le j} t_k + d_j}{p} \right\rfloor$ = First possible period for a transfer involving job $j$.

* We set $\tau_M(j) = (N - 1) - \left\lfloor \frac{\Delta(j, M)}{p} \right\rfloor$ = Last possible period for a transfer involving job $j$.

* We set $C^T = \min(C^F, C^E)$ = Maximum feasible value for $m$ involved into a transfer.
* If a transfer involves *j*, Γ means the jobs that can be performed before another transfer: $\Gamma(j) = \{k > j | \mu(j, k) \le C^E\}$ and $\Gamma(-1) = \{k | \mu(-1, k) \le C_0^E\}$.

## 3.2 Structural Variables and Constraints

We are now going to decompose our problem into core {0, 1} structural variables and rational non-structural variables related to the quantities *m* involved in transfers, with the purpose of later getting rid of those non-structural variables.

Structural variables are, naturally, the following boolean variables:

* $y = (y_i, i = 0, \dots, N-1)$ that represents resource production activation.

* $z = (z_i, i = 0, \dots, N-1)$ that represents resource production activity.

* $x = (x_{i,j}, i = 0, \dots, N-1, j = 0, \dots, M-1)$, that represents the transfers.

These are the core variables, which we complete with auxiliary variables:

* $T$ that represents the ending time of the process.

* $\delta = (\delta_i, i = 0, \dots, N-1)$ that equals 1 if period *i* is related to a transfer and 0 otherwise.

* $\gamma = (\gamma_j, j = 0, \dots, M-1)$ that equals 1 if job *j* is related to a transfer and 0 otherwise.

Then, related Structural Constraints come as follows:

$$ \text{Min} \quad \alpha \sum_{i} (Cost_{i}^{\text{Prod}} \cdot z_{i} + Cost_{i}^{\text{Act}} \cdot y_{i}) + \beta \cdot T \quad (*) $$

$$ \text{s.t.} \quad \forall j, T \ge \sum_{i} x_{i,j} \cdot (p(i+1) + \Delta(j, M)) \quad (S.1) $$

$$ y_0 - z_0 \ge 0 \quad (S.2) $$

$$ \forall i \ge 1, y_i \ge z_i - z_{i-1} \quad (S.3) $$

$$ \forall i \ge 0, z_i + \delta_i \le 1 \quad (S.4) $$

$$ \forall i, \delta_i = \sum_{j} x_{i,j} \quad (S.5) $$

$$ \forall j, \gamma_j = \sum_{i} x_{i,j} \quad (S.6) $$

$$ \forall (i, j) \text{ s.t. } (i > \tau_M(j)) \lor (i < \tau_m(j)), x_{i,j} = 0 \quad (S.7) $$

$$ \forall A \text{ a } \ll \text{-Antichain, } \sum_{(i,j) \in A} x_{i,j} \le 1 \quad (S.8) $$

Explanation of the structural constraints:

(S.1) and (*) mean that we minimise a weighted sum of the production cost and of the time when all jobs are done (α and β are time versus money coefficients). Since at least one transfer must take place, (S.1) means that ending time *T* is the time when the last transfer (*i*, *j*) is over, augmented with the time required in order to perform jobs *j* + 1 to *M* - 1. (S.2) and (S.3) mean that if we do not produce at period *i* - 1 and if we produce at period *i*, then we must activate the production at period *i* and pay related activation cost. (S.4) means that production and transfers exclude themselves. (S.5) and (S.6) tell us that a given period (job) may be involved in no more than 1 transfer. (S.7) means that if (*i*, *j*) induces a transfer then there must remain enough time to perform jobs scheduled after (before) *j*. (S.8) says that transfers must define a chain in the partially ordered subset ($\Lambda$, $\ll$).

## 3.3 Separation of No-Antichain Constraints

Of course, No-Antichain constraints (S.8) must be separated inside a Branch&Cut process [7]. Let *x* be some rational (or integral) feasible solution of (S.1, ..., S.7). Separating (S.8) means searching for an antichain *A* in the partially ordered set ($\Lambda$, $\ll$) such that $\sum_{(i,j) \in A} x_{i,j} > 1$. Theoretically, it can be done by constructing an auxiliary network $G^{\Lambda, \ll}$ with the same nodes as $\Lambda$. Arcs of $G^{\Lambda, \ll}$ are arcs $((i_1, -1), (i, j))$, $((i, j), (N, M))$, augmented with arcs $((i_1, j_1), (i_2, j_2))$ if $(i_1, j_1) \ll (i_2, j_2)$. Then, searching for an antichain *A* in ($\Lambda$, $\ll$) such that $\sum_{(i,j) \in A} x_{i,j} > 1$ means checking on this network for a particular flow vector. No antichain constraints are violated if there does exist a flow transporting no more than 1 flow units from $(-1, -1)$ to $(N, M)$ and such that the sum of flows entering into every $(i, j)$ is at least equal to $x_{i,j}$. Still, there are too many arcs in $G^{\Lambda, \ll}$ for an efficient separation procedure. Instead, we proceed in a heuristic way, through partial tree search with fixed depth (depth of 5 arbitrarily in our case). Related *backtracking* nodes correspond to sequences $(i_1, j_1), \dots, (i_k, j_k)$ whose elements define an antichain in $\Lambda$. If *x* is integral, then we only need to scan the transfers and check that 2 consecutive transfers agree with $\ll$. The time consuming part of this heuristic is the sorting of *x* values whereas the exact algorithm solves a maximum flow problem.

## 3.4 non-structural Variables and Constraints

In order to get a full SLSS-MILP model, we must introduce a rational vector *m* = ($m_{i,j}, i = 0, \dots, N-1, j = 0, \dots, M-1$) which provides us with the quantities of resources associated with every transfer. Related constraints are:

$$ \forall i, j, \quad m_{i,j} \le x_{i,j} \cdot C^T \quad (\text{NS.1}) $$

$$ \forall i, \quad \sum_{j,k \le i} m_{k,j} - \sum_{k \le i} z_k \cdot R_k \le C_0^F \quad (\text{NS.2}) $$

$$ \forall i, \quad \sum_{k \le i} z_k \cdot R_k - \sum_{j,k \le i} m_{k,j} \le C^F - C_0^F \quad (\text{NS.3}) $$

$$ \forall 1 \le j < M, \quad \sum_{i,k<j} m_{i,k} + C_0^E \ge \mu(-1, j) + \sum_{k<j} \gamma_k \cdot \epsilon_k \quad (\text{NS.4}) $$

$$ \sum_{i,j} m_{i,j} \ge \mu(-1, M) + \sum_{j} \gamma_j \cdot \epsilon_j \quad (\text{NS.5}) $$

$$ \forall j, \quad \sum_{i,k \le j} m_{i,k} \le C^E - C_0^E + \mu(-1, j) + \sum_{k<j} \gamma_k \cdot \epsilon_k \quad (\text{NS.6}) $$

**THEOREM 3.1.** The MILP program SLSS-MILP model defined by function (*) and constraints (S.1, ..., S.7, NS.1, ..., NS.6) solves the SLSS problem in an exact way.

**PROOF.** We already provided the meaning of (*) and (S.1, ..., S.7). Let us explain the constraints on vector *m*. (NS.1) says that the amount of resource involved in a transfer can exceed neither the storage capacity of the resource producer nor the storage capacity of the job scheduler. (NS.2) means that the resources transferred during periods 0, ..., *i* cannot exceed the resources produced during the same periods augmented with the initial load of the resource producer. (NS.3) means that the resources stored by the resource producer once he performed those transfers must not exceed its storage capacity. (NS.4) tells us that for any job *j*, the resources needed in order to perform jobs 1, ..., *j* together with the transfers taking place before job *j*, must not exceed the resources transferred before *j*, augmented with the initial load of the job scheduler. (NS.5) says that the resources transferred during the whole process
must cover both the needs of the jobs and the resource transfers. Finally, (NS.6) means that for any job j, the resources stored by the job scheduler after j has been performed must not exceed its storage capacity. So (S.1, ..., S.7, NS.1, ..., NS.6) are necessary conditions for (x, y, z, T, m) to define a feasible **SLSS** schedule. We prove sufficiency by introducing variables $t_j, V_j^E, j = 0, ..., M-1$ and $V_i^F, i = 0, ..., N-1$, which respectively represent the date after j is performed, the resource quantity stored by the job scheduler once j has been performed, and the resource quantity stored by the resource producer at the end of period i. Then we proceed by induction in order to provide those variables with values that make them define a feasible schedule. The time consistency of this schedule will derive from the (S.1) and the No-Antichain constraints. □

# 4 GETTING RID OF THE NON-STRUCTURAL VARIABLES

« Big M » constraints (NS.1) between structural and non-structural variables tend to yield poor rational relaxations. So our purpose here is to get rid of non-structural variables.

## 4.1 Reinforcement of Structural Constraints

The following additional constraints are valid constraints:

$$ \forall j < M-1, \sum_{k \in \Gamma(j)} \gamma_k \ge 1 \qquad (R.1) $$

$$ \forall j, C_0^F + \sum_{k<\tau_M(j)} z_k \cdot R_k \ge \sum_{k<j} \gamma_k \cdot \epsilon_k + \mu(-1, j+1) - C_0^E \quad (R.2) $$

$$ \forall i, C_0^F + \sum_{k \le i} z_k \cdot R_k - C^T \cdot \sum_{k \le i} \delta_k \le C^F \quad (R.3) $$

$$ \forall i_1, i_2 \text{ s.t. } i_1 < i_2, \sum_{i_1 \le k \le i_2} z_k \cdot R_k - C^T \cdot \sum_{i_1 \le k \le i_2} \delta_k \le C^F \quad (R.4) $$

$$ \sum_i z_i \cdot R_i \ge \sum_j (r_j + \epsilon_j \cdot \gamma_j) \quad (R.5) $$

Explanation:

(R.1) says that if there is a transfer at the end of job j, then there must be another transfer before the job scheduler runs out of resources. (R.2) means that for any job j, the resources produced before job j + 1 starts, augmented with the initial loads of both the resource producer and the job scheduler, must be enough to do jobs 0 to j + 1. (R.3) says that for any period i, the resources produced by the resource producer cannot exceed its storage capacity. Those resources are bounded by the production during periods 1, ..., i, augmented with $C_0^F$, and decreased by an upper bound on the resources transferred during periods 0 to i. (R.4) means the same thing, with a focus on a restricted set of consecutive periods $\{i_1, ..., i_2\}$. (R.5) says that global production must cover the requirements of both the jobs and the transfers.

## 4.2 Handling non-structural Constraints With Benders' Cuts

As told at the beginning of this section, our purpose here is to get rid of the vector m and manage it in an implicit way. Clearly, constraints (R.1, ..., R.5) will help us, but they are not enough. So, in order to perform our Branch&Cut process with only the structural variables x, y, z, T, we deal with **SLSS** according to Benders' decomposition scheme. Let us first recall what a Benders' decomposition is. It applies to a MILP **P** of the form:

**P:** {Compute an integral non-negative vector V and a rational non-negative vector m s.t.:

* C.V is the smallest possible, where C is a cost vector

* A.V ≥ a, where A is some constraint matrix and a is a lower bound vector

* B.V + Q.m ≥ b, where B and Q are constraint matrices and b is a lower bound vector}

Then we get rid of vector m by applying duality to the constraint B.V + Q.m ≥ b, and using the fact that, some vector V being given, this constraint is feasible if and only if there does not exist any non-negative dual vector λ such that $λQ ≤ 0$ and $λ(b - B.V) ≥ 1$. Those constraints are called Benders' cuts. **P** may be now rewritten as:

**P:** {Compute an integral non-negative vector V such that:

* C.V is the smallest possible, where C is a cost vector

* A.V ≥ a, and, for any non-negative dual vector λ s.t. $λQ ≤ 0$, we have $λ(b - B.V) ≤ 0$}

The problem reformulated this way may be handled through Branch&Cut: For any current solution V, the process searches for λ such that $λQ ≤ 0$ and $λ(b - B.V) ≥ 1$, and, in case of success, it inserts the Benders' cut $λ(b - B.V) ≤ 0$.

We apply this cutting scheme on our **SLSS** problem while considering that $V = (x, y, z, T, \delta, \gamma)$, that A is the matrix induced by the constraints (S.1, ..., S.8, R.1, ..., R.5), m is our resource quantity vector, and (B, Q) are the matrices related to the non-structural constraints (NS.1, ..., NS.6).

# 5 FORMULATING SLSS AS A PATH SEARCH PROBLEM

We are now going to show that **SLSS** may be formulated as a path search problem in an acyclic large state network. We shall handle it with the well-known A* algorithm (see [9]) for the computation of robot trajectories inside complex spaces.

## 5.1 The SLSS Path Search Formulation

Let us recall that Λ is the set of all transfer pairs (i, j), augmented with a source element (-1, -1) and a sink element (N, M). Λ is provided with a partial order relationship ≪:

* $(i_1, j_1) \ll (i_2, j_2)$ if and only if $(i_2 - i_1 - 1).p \ge \Delta(j_1, j_2)$

* For any $(i, j) \in \Lambda, (-1, -1) \ll (i, j)$ iff $i.p \ge \Delta(-1, j)$ and $(i, j) \ll (N, M)$ iff $(N - 1 - i).p \ge \Delta(j, M)$

We know that transfers involved in any feasible **SLSS** solution define a chain Θ from (-1, -1) to (N, M) in the partially ordered set (Λ, ≪). If $(i_1, j_1)$ and $(i_2, j_2)$ are two consecutive transfers in a solution, then $(i_1, j_1) \ll (i_2, j_2)$ and we also have:

* If $(i_1, j_1) \ne (-1, -1)$ and if $(i_2, j_2) \ne (N, M)$ then $\mu(j_1, j_2) \le C^E$

* If $(i_1, j_1) = (-1, -1)$ and if $(i_2, j_2) \ne (N, M)$ then $\mu(-1, j_2) \le C_0^E$

* If $(i_1, j_1) \ne (-1, -1)$ and if $(i_2, j_2) = (N, M)$ then $\mu(j_1, M) \le C^E - C_0^E$
Such a chain $\Theta = \{(i_0, j_0) = (-1, -1), (i_1, j_1), (i_2, j_2), \dots, (i_Q, j_Q), (i_{Q+1}, j_{Q+1}) = (N, M)\}$ does not characterise an SLSS feasible solution. But we are going to show that it will do it if we provide it with well-fitted value sequences $w = \{w_q, q = 0, 1, \dots, Q, Q+1\}$ and $W = \{W_q, q = 0, 1, \dots, Q\}$, with the meaning:

* For any $q = 1, \dots, Q$, $w_q$ means the resource quantity globally stored by both the resource producer and the job scheduler at the end of period $i_q$ (right after the $(i, j)$ transfer) and $W_q$ denotes the resources produced between period $i_q$ and period $i_{q+1}$

* $w_0 = C_0^F + C_0^E$ means the initial resource quantity and $W_0$ denotes the resources produced before period $i_1$

* $w_{Q+1} \ge C_0^F + C_0^E$ means the resource quantity globally stored by both the resource producer and the job scheduler at the end of the whole process

Then we may state:

**THEOREM 5.1.** *Chain $\Theta$ together with non-negative values $w_q, q = 0, 1, \dots, Q, Q+1$ and $W_q, q = 0, 1, \dots, Q$, define a feasible solution of SLSS if and only if:*

* For any $q = 0, 1, \dots, Q$, $W_q < \min(C^F, C^E + C^F - w_q)$ is a feasible production for periods in $\{i_q + 1, \dots, i_{q+1} - 1\}$

* For any $q = 1, \dots, Q$, $w_q \le C^F + C^E$

* $w_0 = C_0^F + C_0^E$ and $w_{Q+1} \ge C_0^F + C_0^E$

* For any $q = 0, \dots, Q$, $w_{q+1} = w_q + W_q - \mu(j_q, j_{q+1})$

**PROOF.** The key point is that knowing global resource quantities $w_q$ allows us to derive similar quantities $w_q^E$ and $w_q^F$ for respectively the job scheduler and the resource producer. This comes from the fact that the transfer amounts related to $(i_q, j_q)$ may always be chosen such that either they completely fill the storage device of the job scheduler ($w_q^E = C^E$) or they make the storage device of the resource producer become empty ($w_q^F = 0$). By applying this rule, we see by induction that if $\Theta$, $w$ and $W$ are feasible, then related quantities $w^E = \{w_q^E, q = 0, 1, \dots, Q, Q+1\}$ and $w^F = \{w_q^F, q = 0, 1, \dots, Q, Q+1\}$ are such that for any $q, 0 \le w_q^E \le C^E$ and $0 \le w_q^F \le C^F$, while $w_{Q+1}^E \ge C_0^E$ and $w_{Q+1}^F \ge C_0^F$. $\square$

Then, the SLSS problem can be reformulated as a path search: Theorem 5.1 suggests using values $w_q$ as state variables and values $W_q$ as decision variables. More precisely, we define a state set $\Omega$ as the set of all 3-uples $(i, j, w)$ such that $(i, j) \in \Lambda$ and $0 \le w \le C^E+C^F$. We define a source state $(-1, -1, C_0^E+C_0^F)$ and a sink state set $\{(N, M, w), w \ge C_0^E + C_0^F\}$. Then a transition in $\Omega$, related to some decision $(i_2, j_2, W)$ and provided with production cost $Cost(W)$ turns a state 3-uple $(i_1, j_1, w_1)$ into another state $(i_2, j_2, w_2)$ if and only if:

* $(i_1, j_1) \ll (i_2, j_2)$

* $w_2 = w_1 + W - \mu(j_1, j_2)$, $W$ being a feasible production for periods in $i_1 + 1, \dots, i_2 - 1$

The cost of such a transition is $\alpha \cdot Cost(W) + \beta \cdot (i_2 - i_1)$. Please notice that this last formula has to be adapted in case $(i_2, j_2) = (N, M)$. Then it comes that solving SLSS means searching for the shortest path from the source state to a sink state in the set $\Omega$ defined this way, which means a sequence of transitions whose cumulative cost is the smallest possible.

<table><caption>**Table 2: Instance parameters table**</caption><thead><tr><th>id</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th></tr></thead><tbody><tr><th>n</th><td>40</td><td>40</td><td>80</td><td>80</td><td>120</td><td>120</td><td>160</td><td>160</td></tr><tr><th>m</th><td>10</td><td>10</td><td>20</td><td>20</td><td>30</td><td>30</td><td>40</td><td>40</td></tr><tr><th>p</th><td>4</td><td>3</td><td>2</td><td>4</td><td>3</td><td>3</td><td>4</td><td>2</td></tr><tr><th>#SP</th><td>7</td><td>10</td><td>14</td><td>20</td><td>20</td><td>30</td><td>27</td><td>40</td></tr></tbody></table>

## 5.2 An A* Based Shortest Path Algorithm

We use resource quantity $W$ as part of a decision $(i_2, j_2, W)$. If we are in current state $\sigma_1 = (i_1, j_1, w_1)$ then decision $(i_2, j_2, W)$ means that the next transfer will involve $(i_2, j_2)$, with a production $W$ during periods $i_1+1, \dots, i_2-1$. In order to easily get production cost $Cost(W)$, perform a dynamic programming pre-process which yields a table $TAB$, indexed on the pair $(i_1, i_2, 0 \le i_1 < i_2 \le N)$. For any such a pair, $TAB[i_1 i_2]$ contains a list of 3-uples $(W, Cost(W), Sol)$ where $W$ means resources produced during periods $i = i_1 + 1, \dots, i_2 - 1$, $Cost(W)$ their optimal production cost, and $Sol$ some related production schedule.

Provided with table $TAB$, we design our algorithm as an adaptation of the well-known A* algorithm for path search in large state networks. In the current case, we deal with previously described network $\Omega$ and related transitions. For any state $\sigma = (i, j, w)$, we get a lower bound $LB(\sigma)$ for the cost of a path from $\sigma$ to a sink by setting $LB(\sigma) = \alpha \cdot Cost^* + \beta \cdot \Delta(j, M)$, where $Cost^*$ is the smallest cost value obtained in $TAB[i, N]$ for $W \ge C_0^F + C_0^E + \mu(j, M) - w$.

At any time during the resolution process, we are provided with an expansion list $L$ of states $\sigma = (i, j, w)$, given together with related cumulative production costs $Cost(\sigma)$ and future cost estimations $LB(\sigma)$. Those states are ordered in $L$ according to increasing $(\alpha \cdot Cost(\sigma) + \beta \cdot p \cdot (i+1)) + LB(\sigma)$ values. Then we pick up the first element $\sigma_1 = (i_1, j_1, w_1)$ in $L$, called the *pivot state*, and we expand it: we generate all valid decisions $(i_2, j_2, W)$ such that $(i_1, j_1) \ll (i_2, j_2)$ and $W$ is in $TAB[i_1, i_2]$. For every such a decision, we generate resulting state $\sigma_2 = (i_2, j_2, w_2)$ and insert it into $L$ while keeping $L$ ordered according to increasing $Cost(\sigma) + LB(\sigma)$ values. We stop when the *pivot state* $\sigma$ is a sink.

**THEOREM 5.2.** *Above algorithm is pseudo-polynomial and solves SLSS in an exact way.*

**PROOF.** The proof is straightforward. This algorithm is nothing more than the A* algorithm applied to the state network whose nodes are all states $\sigma = (i, j, w)$, and arcs correspond to transitions $(\sigma_1 = (i_1, j_1, w_1) \rightarrow (\sigma_2 = (i_2, j_2, w_2))$ according to decisions $(i_2, j_2, W)$. $\square$

# 6 NUMERICAL EXPERIMENTS

**Purpose:** Observe the behaviour of SLSS-MILP, of the additional valid constraints and Benders' cuts, and the A* algorithm.

**Technical Context:** Algorithms were implemented in C++17 on an Intel i5-9500 CPU at 4.1GHz. CPU times are in seconds.

## 6.1 Instance Generation

In order to mimic the electricity market, production periods are clustered into super-periods of fixed length $p$. Each super-period is
<table><caption>Table 3: Results of all algorithms</caption><thead><tr><th>id</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th></tr></thead><tbody><tr><td>#T</td><td>5</td><td>5</td><td>5</td><td>5</td><td>5</td><td>4</td><td>5</td><td>4</td></tr><tr><td>obj</td><td>202.5</td><td>150</td><td>143.5</td><td>193.5</td><td>211.5</td><td>274.5</td><td>318.3</td><td>197.3</td></tr><tr><td colspan="9">Exact</td></tr><tr><td>relax</td><td>60.2</td><td>55.4</td><td>47.1</td><td>65.2</td><td>79.7</td><td>116.4</td><td>98.3</td><td>123.1</td></tr><tr><td>#AC</td><td>0</td><td>2</td><td>6</td><td>0</td><td>47</td><td>0</td><td>22</td><td>22</td></tr><tr><td>CPU</td><td>43.1</td><td>43.3</td><td>2478</td><td>8795</td><td>6819</td><td>7986</td><td>12853</td><td>12748</td></tr><tr><td>#nodes(k)</td><td>4.1</td><td>4.4</td><td>17.7</td><td>43.7</td><td>41.4</td><td>75.0</td><td>49.1</td><td>40.9</td></tr><tr><td colspan="9">Reinforced</td></tr><tr><td>relax</td><td>86.6</td><td>113.8</td><td>51.2</td><td>79.1</td><td>79.7</td><td>116.5</td><td>99.5</td><td>123.3</td></tr><tr><td>#AC</td><td>1</td><td>6</td><td>10</td><td>7</td><td>25</td><td>21</td><td>4</td><td>6</td></tr><tr><td>CPU</td><td>31.8</td><td>20.0</td><td>2459</td><td>13384</td><td>13933</td><td>9387</td><td>11688</td><td>13130</td></tr><tr><td>#nodes(k)</td><td>1.0</td><td>0.3</td><td>13.3</td><td>42.2</td><td>20.0</td><td>30.8</td><td>3.9</td><td>6.4</td></tr><tr><td colspan="9">Approximate</td></tr><tr><td>approx</td><td>150</td><td>125</td><td>135.5</td><td>188.9</td><td>199.4</td><td>272.9</td><td>239.1</td><td>168.4</td></tr><tr><td>#AC</td><td>0</td><td>2</td><td>0</td><td>20</td><td>1</td><td>20</td><td>2</td><td>22</td></tr><tr><td>CPU</td><td>19.6</td><td>9.7</td><td>410.5</td><td>1325</td><td>4329</td><td>3490</td><td>9281</td><td>10038</td></tr><tr><td>#nodes(k)</td><td>1.0</td><td>0.2</td><td>4.3</td><td>15.6</td><td>15.0</td><td>4.5</td><td>34.9</td><td>2.3</td></tr><tr><td colspan="9">Benders</td></tr><tr><td>#BD</td><td>497</td><td>458</td><td>5189</td><td>5034</td><td>11</td><td>4827</td><td>2745</td><td>52</td></tr><tr><td>#AC</td><td>5</td><td>2</td><td>18</td><td>28</td><td>0</td><td>13</td><td>8</td><td>2</td></tr><tr><td>CPU</td><td>173.4</td><td>94.2</td><td>4706</td><td>15358</td><td>15344</td><td>8716</td><td>13018</td><td>15306</td></tr><tr><td>#nodes(k)</td><td>4.1</td><td>2.1</td><td>12.4</td><td>36.8</td><td>14.9</td><td>19.7</td><td>4.8</td><td>1.4</td></tr><tr><td colspan="9">A*</td></tr><tr><td>CPU</td><td>0.01</td><td>0.01</td><td>28.8</td><td>6.8</td><td>301.6</td><td>1840</td><td>262.5</td><td>3518</td></tr><tr><td>#nodes(k)</td><td>0.3</td><td>0.7</td><td>7.8</td><td>6.3</td><td>24.6</td><td>28.4</td><td>16.5</td><td>37.7</td></tr><tr><td>nodes(%)</td><td>6.5</td><td>6.1</td><td>17.8</td><td>5.7</td><td>15.5</td><td>13.8</td><td>4.2</td><td>6.8</td></tr></tbody></table>

assigned symbolic mean production and cost values $\overline{R}_{cl}$, $\overline{Cost}_{cl}$ in {Low, Medium, High}. Then, production quantities and cost values are randomly generated for every period according to their super-period's means. We do this in such a way that demand can be satisfied.

We capture the lot sizing feature with activation costs such that $\frac{Cost_i^{Act}}{Cost_i^{Prod}} \in [\frac{N}{#tr}, 2\frac{N}{#tr}]$ where $\#tr = \frac{\mu(-1,M)}{C^T}$ is the expected number of transfers. In the experiments below, we fix this value to $\frac{\mu(-1,M)}{C^T} = 3$ and we set $\frac{C^E}{C^F} = 2$.

Some No-Antichain cuts are generated before the start of the Branch&Cut. In order to have every pair $(i, j)$ at least once, we generate $N \times M$ No-Antichain cuts: starting from $(i, j)$, choose a random $(i', j')$ that is incomparable with every pair chosen so far, repeat until there is no more incomparable pair possible.

Table 2 presents a package of 8 instances with their characteristics (#SP is the length of the optimal path to be found by the A* algorithm).

## 6.2 Outputs and Numerical Results

For every instance, we compute and show in Table 3:

* The id of the instance, #T the number of transfers in the optimal solution and the objective value obj of SLSS-MILP.

* **Exact**: The linear relaxation relax, the number #AC of No-Antichain cuts, related CPU times CPU and #nodes(k) the number of explored nodes in thousands of nodes (×1000).

* **Reinforced**: The same values relax, #AC, CPU and #nodes(k) (×1000) resulting from the reinforcement of SLSS-MILP by valid constraints of Section 4.1.

* **Approximate**: The objective values approx induced by SLSS-MILP with valid constraints of Section 4.1 and without the non-structural vector m.

* **Benders**: The values obj, #AC, CPU and #nodes(k) (×1000) as before, together with the number #BD of Benders' cuts resulting from the Benders' decomposition of Section 4.2.

* **A***: The value obj, the CPU times CPU, the #nodes(k) the number of visited nodes (×1000) and the percentage nodes(%) of visited nodes on all possible nodes, induced by the A* algorithm of Section 5.

Comments: First, we see that the reinforced constraints help a lot in reducing the number of nodes but are a little harder to solve. However, they have no understandable effect on the number of No-Antichain cuts (sometimes more, sometimes less antichains). The same goes for the Benders' formulation. Also, as expected, the A* algorithm is, by far, the fastest to give the optimal solution.
# 7 CONCLUSION

We dealt here with the problem of synchronising a *Lot Sizing* actor with a *Job Scheduling* one. We proposed a MILP formulation, some valid constraints on the integer variables to reinforce the MILP, a Benders' formulation to replace the rational variables and a path search formulation. Then, we solved the *SLSS* using *Branch&Cut* and an *A*-based algorithm for the path search. This last method proved to be the best and all other methods are almost tied in terms of computation time, but the Benders' formulation is the one exploring the fewest nodes. In the next months, we plan to address either the collaborative issue and the management of related uncertainty or one of the variants proposed in Section 2.2.

# ACKNOWLEDGMENTS

This work was sponsored by a public grant overseen by the French National Research Agency as part of the "Investissements d'Avenir" through the IMobS.3 Laboratory of Excellence (ANR-10-LABX-0016) and the IDEX-ISITE initiative CAP 20-25 (ANR-16-IDEX-0001).

# REFERENCES

[1] Yossiri Adulyasak, Jean François Cordeau, and Raf Jans. 2015. The production routing problem: A review of formulations and solution algorithms. *Computers and Operations Research* 55 (2015), 141–152. https://doi.org/10.1016/j.cor.2014.01.011

[2] Konstantin Biel and Christoph H. Glock. 2016. Systematic literature review of decision support models for energy-efficient production planning. *Computers and Industrial Engineering* 101 (nov 2016), 243–259. https://doi.org/10.1016/j.cie.2016.08.021

[3] Alistair Clark, Bernardo Almada-Lobo, and Christian Almeder. 2011. Lot sizing and scheduling: Industrial extensions and research opportunities. *International Journal of Production Research* 49, 9 (may 2011), 2457–2461. https://doi.org/10.1080/00207543.2010.532908

[4] Benoit Colson, Patrice Marcotte, and Gilles Savard. 2005. Bilevel programming: A survey. *arXiv* 3, 2 (2005), 87–107. https://doi.org/10.1007/s10288-005-0071-0

[5] A. Drexel and A. Kimms. 1997. Lot sizing and scheduling - Survey and extensions. *European Journal of Operational Research* 99, 2 (1997), 221–235. https://doi.org/10.1016/S0377-2217(97)00030-1

[6] Tomislav Erdelic, Tonči Carić, and Eduardo Lalla-Ruiz. 2019. A Survey on the Electric Vehicle Routing Problem: Variants and Solution Approaches. *Journal of Advanced Transportation* 2019 (2019). https://doi.org/10.1155/2019/5075671

[7] András Frank. 1980. On chain and antichain families of a partially ordered set. *Journal of Combinatorial Theory. Series B* 29, 2 (oct 1980), 176–184. https://doi.org/10.1016/0095-8956(80)90079-9

[8] Guillaume Goisque and Christophe Rapine. 2017. An efficient algorithm for the 2-level capacitated lot-sizing problem with identical capacities at both levels. *European Journal of Operational Research* 261, 3 (2017), 918–928. https://doi.org/10.1016/j.ejor.2017.02.024

[9] Peter E. Hart, Nils J. Nilsson, and Bertram Raphael. 1968. A Formal Basis for the Heuristic Determination of Minimum Cost Paths. *IEEE Transactions on Systems Science and Cybernetics* 4, 2 (1968), 100–107. https://doi.org/10.1109/TSSC.1968.300136

[10] Y. F. Hung and K. L. Chien. 2000. A multi-class multi-level capacitated lot sizing model. *Journal of the Operational Research Society* 51, 11 (2000), 1309–1318. https://doi.org/10.1057/palgrave.jors.2601026

[11] Sandy Irani and Kirk R. Pruhs. 2005. Algorithmic problems in power management. *ACM SIGACT News* 36, 2 (jun 2005), 63–76. https://doi.org/10.1145/1067309.1067324

[12] Philip Kaminsky and David Simchi-Levi. 2003. Production and distribution lot sizing in a two stage supply Chain. *IIE Transactions (Institute of Industrial Engineers)* 35, 11 (2003), 1065–1075. https://doi.org/10.1080/07408170304401

[13] Hans Kellerer, Ulrich Pferschy, and David Pisinger. 2004. Multidimensional Knapsack Problems. *Knapsack Problems* (2004), 235–283. https://doi.org/10.1007/978-3-540-24777-7_9

[14] Thomas Kleinert, Martine Labbé, Ivana Ljubić, and Martin Schmidt. 2021. A Survey on Mixed-Integer Programming Techniques in Bilevel Optimization. *EURO Journal on Computational Optimization* 9 (2021). https://doi.org/10.1016/j.ejco.2021.100007

[15] Martine Labbé, Fränk Plein, and Martin Schmidt. 2020. Bookings in the European gas market: characterisation of feasibility and computational complexity results.

*Optimization and Engineering* 21, 1 (mar 2020), 305–334. https://doi.org/10.1007/s11081-019-09447-0

[16] Giusy Macrina, Luigi Di Puglia Pugliese, and Francesca Guerriero. 2020. The Green-Vehicle Routing Problem: A Survey. *Modeling and Optimization in Green Logistics* (2020), 1–26. https://doi.org/10.1007/978-3-030-45308-4_1

[17] Joon Yung Moon and Jinwoo Park. 2014. Smart production scheduling with time-dependent and machine-dependent electricity cost by considering distributed energy resources and energy storage. *International Journal of Production Research* 52, 13 (2014), 3922–3939. https://doi.org/10.1080/00207543.2013.860251

[18] Agnes Pechmann and Ilka Schöler. 2011. Optimizing energy costs by intelligent production scheduling. *Glocalized Solutions for Sustainability in Manufacturing - Proceedings of the 18th CIRP International Conference on Life Cycle Engineering* (2011), 293–298. https://doi.org/10.1007/978-3-642-19692-8_51

[19] F. Zeynep Sargut and H. Edwin Romeijn. 2007. Capacitated production and subcontracting in a serial supply chain. *IIE Transactions (Institute of Industrial Engineers)* 39, 11 (nov 2007), 1031–1043. https://doi.org/10.1080/07408170601091899

[20] Yang Song, Chi Zhang, and Yuguang Fang. 2008. Multiple multidimensional knapsack problem and its applications in cognitive radio networks. *Proceedings - IEEE Military Communications Conference MILCOM* (2008). https://doi.org/10.1109/MILCOM.2008.4753629

[21] Franck Taillandier, Christophe Fernandez, and Amadou Ndiaye. 2017. Real Estate Property Maintenance Optimization Based on Multiobjective Multidimensional Knapsack Problem. *Computer-Aided Civil and Infrastructure Engineering* 32, 3 (mar 2017), 227–251. https://doi.org/10.1111/mice.12246

Received 28 August 2023; accepted 17 October 2023