# Exact algorithms for the bilevel scheduling of uniform parallel machines in the context of coupling maintenance and scheduling decisions

Quentin Schau, Vincent T'kindt, Olivier Ploton, Federico Della Croce, Han Hoogeveen

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

## To cite this version:

Quentin Schau, Vincent T'kindt, Olivier Ploton, Federico Della Croce, Han Hoogeveen. Exact algorithms for the bilevel scheduling of uniform parallel machines in the context of coupling maintenance and scheduling decisions. MAPSP, Kevin Schewior; Marco Chiarandini; Lene Monrad Favrholdt, Jun 2024, Kolding, Denmark, France. hal-04711273

HAL Id: hal-04711273

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

Submitted on 26 Sep 2024

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>
Exact algorithms for the bilevel scheduling of uniform
parallel machines in the context of coupling maintenance
and scheduling decisions

Quentin Schau * Federico Della Croce † Han Hoogeveen ‡

Olivier Ploton § Vincent T'kindt ¶

# 1 Introduction

This study focuses on a scenario with one leader and one follower composed of par-
allel uniform machines where scheduling decisions occur periodically in the context of
bilevel optimization. To the best of our knowledge, the literature on bilevel scheduling
is relatively limited, we refer here to [2, 5, 6, 7, 8].

Assume we are given a set $\mathcal{J}$ of $N$ jobs, each job $j$ being characterized by its processing time $p_j$, weight $w_j$ and due date $d_j$. On one hand, we have a leader that manages the system health and global scheduling. On the other hand, we have a follower that schedules jobs on a set of given parallel uniform machines. The leader decides of the jobs the follower schedules by minimizing the number of weighted tardy jobs. The follower aims to minimize the total completion time. Following the classic bilevel optimization framework, we consider the optimistic case, i.e. the follower returns the schedule that leads to the minimum number of weighted tardy jobs among schedules optimal for the total completion time.

We assume that the leader periodically makes scheduling decisions every $T$ units of
time. Prior to each period, the leader receives data from the shop floor. Using this data,
the leader makes decisions, potentially altering the speed of certain machines by setting
them to $V_{max}$ or $V_0$, or removing them from the follower. These decisions are relevant
within the context of Industry 4.0. Next, the leader selects a subset $\mathcal{I} \subset \mathcal{J}$ of $n$ jobs and
assigns them to the follower. In the follower's problem, there is a lexicographical ob-
jective function. Correspondingly, following the extended three-field classification in [1],
we denote this bilevel problem as $Q|V_i \in \{V_0, V_{max}\}, \text{OPT} - n| \sum_j C_j^F, \sum_j w_j U_j^L$, while

<footnote>*quentin.schau@univ-tours.fr. Laboratoire d'Informatique Fondamentale et Appliquée, Université de Tours, 64 rue Jean Portalis, 37200 Tours, France.</footnote>

<footnote>†federico.dellacroce@polito.it. DIGEP, Politecnico di Torino, Corso Duca degli Abruzzi 24, 10129 Torino, Italy.</footnote>

<footnote>‡j.a.hoogeveen@uu.nl. Department of Information and Computing Sciences, Utrecht University, Princetonplein 5, 3584 CC Utrecht, The Netherlands.</footnote>

<footnote>§olivier.ploton@univ-tours.fr. Laboratoire d'Informatique Fondamentale et Appliquée, Université de Tours, 64 rue Jean Portalis, 37200 Tours, France.</footnote>

<footnote>¶tkindt@univ-tours.fr. Laboratoire d'Informatique Fondamentale et Appliquée, Université de Tours, 64 rue Jean Portalis, 37200 Tours, France.</footnote>
the related follower problem is denoted as $Q|V_i \in \{V_0, V_{max}\}|Lex(\sum_j C_j^F, \sum_j w_j U_j^L)$.
Notice that, when $n = N$ the two problems coincide.

## 2 Complexity and solution approaches

In terms of complexity, we can show the $\mathcal{NP}$-hardness in the strong sense of problem $Q|V_i \in \{V_0, V_{max}\}|Lex(\sum_j C_j^F, \sum_j w_j U_j^L)$ (and correspondingly of the bilevel problem). Indeed, the special case with identical parallel machines and unit weights, that is problem $P|Lex(\sum_j C_j^F, \sum_j w_j U_j^L)$, can be shown to be $\mathcal{NP}$-hard in the strong sense by reduction from the numerical 3-dimensional matching (NUM-3DM).

When the number of machines $m$ is not part of the input, we can already show that problem $P2|Lex(\sum_j C_j^F, \sum_j w_j U_j^L)$ is $\mathcal{NP}$-hard by reduction from the well known even-odd partition problem. To complete the complexity analysis, we can show that all problems from $P2|Lex(\sum_j C_j^F, \sum_j w_j U_j^L)$ to $Qm|V_i \in \{V_0, V_{max}\}|Lex(\sum_j C_j^F, \sum_j w_j U_j^L)$ with $m$ constant are $\mathcal{NP}$-hard in the ordinary sense.

Before solving the bilevel problem, we focus on the follower problem. The lexicographical objective function, especially the first criteria, leads to a block structure for the scheduling. Assume we have a set $\mathcal{J}$ of $n$ jobs given by the leader, then let $N_{max}$ (respectively $N_0$) be the number of machines with high-speed $V_{max}$ (respectively, with low speed $V_0$). We can show that an optimal schedule of the problem $Q|V_i \in \{V_{max}, V_0\}|\sum_j C_j$ is given by the repetition of patterns. In Figure 2, an illustration depicts a pattern consisting of $\alpha$ blocks on high-speed machines and one block on low-speed machines. Jobs highlighted with $\color{red}{\blacksquare}$ are part of the first pattern, while those marked with $\color{green}{\blacksquare}$ belong to a other pattern. Jobs within the blue-dashed group signify their membership to a block and can subsequently undergo permutation without changing the optimal value of the first criteria, i.e. $\sum_j C_j$. Let us define $B_{max}$ (respectively $B_0$) as the set of all blocks that can be assigned to high-speed machines (respectively low-speed machines).

Hence, we know for all jobs $j$ on which set $B_{max}$ or $B_0$ it is scheduled. Using this characterization, by extending to the considered problem the approach on parallel machines scheduling proposed in [4], a dynamic programming recursion can be formulated running in pseudo-polynomial time. In addition, a MIP can be formulated for the follower problem. We are currently working on a column generation approach, by extending the works proposed in [3]. At the time of the conference we will present these three exact solution approaches and how they can be generalized to solve the bilevel problem.
<figure><img src="image_3.png" /><figcaption>Figure 1: Scheduling pattern with block structure for the optimal solution of problem $Q|V_i \in \{V_{max}, V_0\}| \sum_j C_j$</figcaption></figure>

References

[1] R. L. GRAHAM AND E. L. LAWLER AND J.K. LENSTRA AND AHG R. KAN (1979). *Optimization and approximation in deterministic sequencing and scheduling: a survey*. Annals of discrete mathematics.

[2] JOHN K. KARLOF AND WEI WANG (1996). *Bilevel programming applied to the flow shop scheduling problem*. Computers & operations research.

[3] J.M. VAN DEN AKKER AND J.A. HOOGEVEEN AND S. L. VAN DE VELDE (1999). *Parallel machine scheduling by column generation*. Operations research.

[4] JNICHOLAS G. HALL AND MASEKA LESAOANA AND CHRIS N. POTTS (2001). *Scheduling with fixed delivery dates*. Operations Research.

[5] SAMIR A ABASS (2005). *Bilevel programming approach applied to the flow shop scheduling problem under fuzziness*. Computational Management Science.

[6] ANDRÁS KOVÁCS AND TAMÁS KIS (2011). *Constraint programming approach to a bilevel scheduling problem*. Constraints.

[7] TAMÁS KIS AND ANDRÁS KOVÁCS (2012). *On bilevel machine scheduling problems*. OR spectrum.

[8] VINCENT T'KINDT AND FEDERICO DELLA CROCE AND ALESSANDRO AGNETIS (2023). *Single machine adversarial bilevel scheduling problems*. European Journal of Operational Research.