# A column generation approach for solving a bilevel parallel machine scheduling problem

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

► To cite this version:

Quentin Schau, Olivier Ploton, Vincent T'kindt, Federico Della Croce, Han Hoogeveen, et al. A column generation approach for solving a bilevel parallel machine scheduling problem. ROADEF 2025, École Nationale des Ponts et Chaussées, Feb 2025, Champs Sur Marne, France. hal-05141732

HAL Id: hal-05141732

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

Submitted on 3 Jul 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
A column generation approach for solving a bilevel parallel
machine scheduling problem

Schau Q.<fnref n="1" />, Ploton O.<fnref n="1" />, T'kindt V.<fnref n="1" />, Della Croce F.<fnref n="3" />, Hoogeveen H.<fnref n="2" />, Hoogeveen J.<fnref n="2" />

**Keywords:** Scheduling, bilevel optimization, parallel machines

# 1 Introduction

This research investigates a scheduling problem that can find applications in Industry 4.0. It is assumed that the shop floor is composed of a Cyber-Physical System (CPS), called the follower, which schedules parallel uniform machines. At an upper decision level another agent, called the leader, decides of the jobs to be scheduled for the current period. This setup falls into the category of bilevel optimization. To the best of our knowledge, the body of research specifically addressing bilevel scheduling is rather sparse, with relevant works including [1, 2, 3, 6].

The problem can be more formally defined as follows. At each scheduling period, a set $\mathcal{J}$ containing $N$ jobs is given, where each job $j$ is defined by its processing time $p_j$, weight $w_j$, and due date $d_j$. The leader is responsible for the overall system health and has to select a subset $\mathcal{I} \subset \mathcal{J}$ of exactly $n$ jobs that are assigned to the follower. Thus, this one is tasked with executing the selected jobs on the uniform parallel machines. Based on the status of each machine, the leader determines actions in order to preserve the health status of the system: healthy machines are set to the maximal speed $V_{max}$, machines having a risk of failure are set to the minimal speed $V_0$ and machines which do need a maintenance operation are excluded from the follower's control. Therefore, we denote by $N_{max}$ (resp. $N_0$) the number of machines operating at high speed $V_{max}$ (resp. low speed $V_0$). Without loss of generality, it is assumed that $V_0$ divides $V_{max}$. These decisions are framed within the context of Zero Defect Manufacturing (ZDM) for Industry 4.0.

The leader's objective is to minimize the weighted number of tardy jobs, denoted by $\sum_j w_j U_j^L$, whereas the follower seeks to reduce the total completion time, denoted by $\sum_j C_j^F$. We adopt the optimistic perspective, meaning the follower provides the schedule that minimizes the leader's objective ($\sum_j w_j U_j^L$) from among the schedules that are optimal with respect to $\sum_j C_j^F$. Consequently, the follower's problem reduces to solve the lexicographical problem denoted by $Lex(\sum_j C_j^F, \sum_j w_j U_j^L)$. Using the standard three-field notation extended in [6], this bilevel problem is denoted by $Q|OPT - n, V_i \in V_0, V_{max}| \sum_j C_j^F, \sum_j w_j U_j^L$, while the corresponding follower's problem is denoted by $Q|V_i \in V_0, V_{max}|Lex(\sum_j C_j^F, \sum_j w_j U_j^L)$. It is important to note that when $n = N$, the two problems are equivalent.

# 2 Complexity and solution approaches

In terms of complexity, [4] have shown that problem $Q|OPT-n, V_i \in V_0, V_{max}| \sum_j C_j^F, \sum_j w_j U_j^L$ is $\mathcal{NP}$-hard in the strong sense of problem. Problem $Q|V_i \in V_0, V_{max}|Lex(\sum_j C_j^F, \sum_j w_j U_j^L)$

<footnote n="1">¹ Université de Tours, Laboratoire d'Informatique Fondamentale et Appliquée, Tours, France,
{quentin.schau,olivier.ploton,tkindt}@univ-tours.fr</footnote>

<footnote n="2">² Department of Information and Computing Sciences, Utrecht University Princetonplein 5, 3584
CC Utrecht, Netherlands, j.a.hoogeveen@uu.nl</footnote>

<footnote n="3">³ DIGEP, Politecnico di Torino, Corso Duca degli Abruzzi 24, 10129 Torino, Italy,
**federico.dellacroce@polito.it**+</footnote>
has also been shown NP-hard which may be surprising knowing that problem $Q \parallel \sum_j C_j$ can be solved in polynomial time.

In [4, 5], we proposed a dynamic programming recursion with pseudo-polynomial complexity, as well as a MIP model for the bilevel optimization problem. Computational experiments showed that the MIP is able to solve randomly generated instances with up to 40 jobs and 4 machines in a reasonable amount of time.

We now focus on the exact solution of the bilevel problem by means of column generation and a branch-and-bound algorithm. The column generation that we propose aims to compute a lower bound for the problem; we are extending the approach of [7]. On one hand, we have the master problem that is formulated as a set-covering problem with an exponential number of binary variables and a linear number of constraints. On the other hand, we have the pricing problem that consists of solving a dynamic programming problem to find a column with the minimal reduced cost. The branch and bound algorithm is based on properties from the follower and incorporates some dominance rules to reduce the number of nodes. These algorithms will be presented in more detail at the time of the conference.

## References

[1] Samir A Abass. Bilevel programming approach applied to the flow shop scheduling problem under fuzziness. *Computational Management Science*, 2:279-293, 2005.

[2] John K Karlof and Wei Wang. Bilevel programming applied to the flow shop scheduling problem. *Computers & Operations Research*, 23(5):443-451, 1996.

[3] Tamás Kis and András Kovács. On bilevel machine scheduling problems. *OR spectrum*, 34(1):43-68, 2012.

[4] Quentin Schau, Olivier Ploton, Vincent T'Kindt, and Federico Della Croce. Bilevel scheduling of uniform parallel machines in the context of coupling maintenance and scheduling decisions. In *Project Management and Scheduling (PMS)*, 2024.

[5] Quentin Schau, Vincent T'kindt, Olivier Ploton, Federico Della Croce, and Han Hoogeveen. Exact algorithms for the bilevel scheduling of uniform parallel machines in the context of coupling maintenance and scheduling decisions. In *MAPSP*, 2024.

[6] Vincent T'kindt, Federico Della Croce, and Alessandro Agnetis. Single machine adversarial bilevel scheduling problems. *European Journal of Operational Research*, 315(1):63-72, 2024.

[7] Marjan Van Den Akker, Han Hoogeveen, and Steef Van de Velde. Parallel machine scheduling by column generation. *Operations Research*, 47(6):862-872, 1999.