Bilevel scheduling of uniform parallel machines in the context
of coupling maintenance and scheduling decisions

Schau Q.¹, Ploton O.¹, T'kindt V.¹, Della Croce F.²

¹ Université de Tours, Laboratoire d'Informatique Fondamentale et Appliquée, Tours, France,
{quentin.schau,olivier.ploton,tkindt}@univ-tours.fr

² DIGEP, Politecnico di Torino, Corso Duca degli Abruzzi 24, 10129 Torino, Italy,
**federico.dellacroce@polito.it**

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

# 1 Introduction

This study focuses on a scenario with one leader and one follower (named Cyber Physical Sys-
tem CPS) composed of parallel 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 [1, 4, 5, 6].

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$. We have a leader that manages the system health and global scheduling and we have a CPS, composed of parallel uniform machines, which schedules the jobs given by the leader. The leader aims to minimize the number of weighted tardy jobs while the follower aims to minimize the total completion time. 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 ZDM for 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 objective function.
Correspondingly, following the three-field classification [2], we denote this bilevel problem as
$Q|V_i \in \{V_0, V_{max}\}, OPT - n|\sum_j C_j^F, \sum_j w_j U_j^L$, while 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. Hence,

$$
Q|V_i \in \{V_0, V_{max}\}|Lex (\sum_j C_j^F, \sum_j w_j U_j^L) \propto Q|V_i \in \{V_0, V_{max}\}, OPT - n|\sum_j C_j^F, \sum_j w_j U_j^L.
$$

## 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 problem $Q|V_i \in \{V_0, V_{max}\}, OPT-n|\sum_j C_j^F, \sum_j w_j U_j^L$). 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* (*∑*<sub>*j*</sub> *C*<sub>*j*</sub><sup>*F*</sup>, *∑*<sub>*j*</sub> *U*<sub>*j*</sub><sup>*L*</sup>) is *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 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.

Assume we have a set $\mathcal{J}$ of $n$ jobs, 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 a high-speed machine and one block on a low-speed machine. Jobs highlighted with $\boxled{1}$ are part of the first pattern, while those marked with $\boxled{2}$ belong to a other pattern. Jobs within the green-dashed group signify their membership to a block and can subsequently undergo permutation. Let us define $\mathcal{B}_{max}$ (respectively $\mathcal{B}_0$) as the set of all blocks that can be assigned to high-speed machines (respectively low-speed machines).

<figure><img src="image_1.png" /><figcaption>FIG. 1: Scheduling pattern with block structure for the optimal solution of $Q|V_i \in \{V_{max}, V_0\}| \sum_j C_j$</figcaption></figure>

Hence, we know for all jobs $j$ on which set $\mathcal{B}_{max}$ or $\mathcal{B}_0$ it is scheduled. Using this characterization, by extending to the considered problem the approach on parallel machines scheduling proposed in [3], a dynamic programming recursion can be formulated running in pseudo-polynomial time. The related approach can be adapted for the bilevel problem, and we will present this adaptation at the Conference. The characterizations we have developed also enable the development of heuristics for the bilevel problem.

## 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] Ronald Lewis Graham, Eugene Leighton Lawler, Jan Karel Lenstra, and AHG Rinnooy Kan. Optimization and approximation in deterministic sequencing and scheduling: a survey. In *Annals of discrete mathematics*, volume 5, pages 287–326. Elsevier, 1979.

[3] Nicholas G. Hall, Maseka Lesaoana, and Chris N. Potts. Scheduling with fixed delivery dates. *Operations Research*, 49(1):134–144, 2001.

[4] John K Karlof and Wei Wang. Bilevel programming applied to the flow shop scheduling problem. *Computers & operations research*, 23(5):443–451, 1996.

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

[6] Vincent T'kindt, Federico Della Croce, and Alessandro Agnetis. Single machine adversarial bilevel scheduling problems. *European Journal of Operational Research*, 2023.