# Embedding reinforcement-learning into an iterated local search for solving an unrelated parallel machine scheduling problem

Ruan Myller Magalhães de Oliveira, Arthur Kramer, Thiago Alves de Queiroz

► To cite this version:

Ruan Myller Magalhães de Oliveira, Arthur Kramer, Thiago Alves de Queiroz. Embedding reinforcement-learning into an iterated local search for solving an unrelated parallel machine scheduling problem. 26ème Congrès Annuel de la Société Française de Recherche Opérationnelle et Aide à la Décision, Feb 2025, Champs-sur-Marne (Marne-la-Vallée), France. hal-04995200

HAL Id: hal-04995200

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

Submitted on 18 Mar 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>
Embedding reinforcement-learning into an iterated local search
for solving an unrelated parallel machine scheduling problem

Ruan Myller Magalhães de Oliveira¹², Arthur Kramer<fnref n="2" />, Thiago Alves de Queiroz<fnref n="1" />

**Keywords** : scheduling, iterated local search, reinforcement-learning, optimization

# 1 Introduction

In this work, we address an unrelated parallel machine scheduling problem that arises in the context of just-in-time manufacturing systems. We are given a set *M* of unrelated parallel machines that are available to process a set *J* of jobs. Each job in *J* must be processed by one machine. The processing time *p*<sub>*j*</sub><sup>*k*</sup> of a job *i* ∈ *J* depends on the machine *k* ∈ *M* that will process it. For each job *j* ∈ *J*, a due date *d*<sub>*j*</sub> and two weights are given, one to penalize the earliness (*w*<sub>*j*</sub>) and another for tardiness (*w*'<sub>*j*</sub>). In addition, we consider sequence- and machine-dependent setup times, i.e., if job *i* is processed immediately before job *j* in machine *k*, a setup time *s*<sub>*ij*</sub><sup>*k*</sup> is necessary. The objective is to find a schedule that minimizes the total weighted earliness and tardiness: $\sum_{j \in J} (w_j E_j + w'_j T_j)$. The earliness of a job *j* is given by $E_j = \max\{0, d_j - C_j\}$ and the tardiness by $T_j = \max\{0, C_j - d_j\}$, where $C_j$ refers to the completion time of job *j* in a solution of the problem. This problem is $\mathcal{NP}$-hard and denoted as $R|s_{ij}^k| \sum_{j \in J} (w_j E_j + w'_j T_j)$ using the three-field scheduling notation. Among the works that dealt with this problem, we highlight the contributions of [2, 4]. In [2], the authors proposed an exact framework to solve a class of scheduling problems, including the one solved here. In [4], the authors proposed a Meta-Heuristic (MH) based on the Iterated Local Search (ILS) to solve the same class of problems. Recently, the research community has also turned its attention to the use of Machine-Learning (ML) techniques to help solving optimization problems, as summarized in [1]. The authors emphasize how the use of these techniques can be used during the decision-making process and how they are capable of acquiring implicit knowledge by experience.

Thus, in this work, we are interested in the integration of two different techniques to solve the $R|s_{ij}^k| \sum_{j \in J} (w_j E_j + w'_j T_j)$: ML and MH. In particular, we are interested in embedding Reinforcement Learning (RL), a very promising branch in ML, as pointed out by [3], into the local search phase of the proposed ILS. This integration seems promising, as can be seen in the work of [5] that considered a makespan minimization scheduling problem.

2 Proposed method and preliminary results

The ILS considered in this work (ILS) can deal with one of the greatest trade-offs inside the MH
field: the balance between exploitation and exploration. The ILS is composed of four mains
steps: (i) construction, (ii) local search, (iii) perturbation, and (iv) acceptance criterion. The
ILS we considered in this work is the same previously proposed in [4] that is, to the best of our
knowledge, the state-of-the-art concerning the problem under investigation. In their method,
the local search phase is based on a Variable Neighborhood Descent (VND). The classical VND
is composed of a set of neighborhood structures, which follows a given exploration sequence,

<footnote n="1">¹ Institute of Mathematics and Technology, Federal Univ. of Catalão, 75708-560, Catalão, Brazil
ruanmyller@discente.ufcat.edu.br, taq@ufcat.edu.br</footnote>

<footnote n="2">² Mines Saint-Étienne, Univ. Clermont Auvergne, CNRS, UMR 6158 LIMOS, Institut Henri Fayol, 42023, Saint-Étienne, France
arthur.kramer@emse.fr</footnote>
in order to improve an input solution. Actually, in [4] the authors used a slightly modified version of the VND called Randomized VND (RVND) in which the neighborhood exploration order is random.

Our contribution relies on the modification of the local search phase. We integrate a RL method to define the exploration order of the neighborhood structures instead of considering either a fixed or a totally random exploration order. This method may be better understood from the concept called Markov decision process where the agent is the element responsible for making decisions and for learning as it interacts with the environment. Basically, the agent is able to realize changes (actions) into the environment since it has the capability of sensing certain attributes of the environment where it acts. The actions are then rewarded by the environment based on a reward function (based on the objective function of the problem). The memory on the actions and rewards are then stored into the so-called Q-table that can be seen as a guiding element during the choice of further actions. In our method, we use RL to learn on the transitions between each pair of neighborhoods considered in the VND (local search phase) and the memory on the rewards and actions are stored into a Q-table of size $|N|^2$, where N is the set of neighborhood structures in the VND. Our Q-table is initialized with no memorized information, i.e., the learning phase is considered during the resolution of a given instance of the problem. We considered two different policies for selecting the actions to perform at each iteration of the method: the ε-greedy and the Boltzmann exploration strategies. We tested our method using a set of instances from the literature. We compared the obtained results with the ones obtained by the state-of-the-art method by [4]. The preliminary results seem promising as we are able to find solutions that are in average at 2% from the best known results.

## 3 Concluding remarks

In this work, we proposed a method that combines ML and MH techniques to solve the $R|s_{ij}^k| \sum_{j \in J} (w_j E_j + w_j' T_j)$. More precisely, we embedded a RL into an ILS, where the RL is responsible for deciding the neighborhood exploration order inside the VND used as local search. Our preliminary results seem promising as the proposed method is able to find solutions close to the best known solutions in the literature. However, a better calibration of the parameters is still needed in order to fine tuning the method. As future research directions, in addition to the calibration of parameters, we will investigate the use of different reward functions for the RL method as well as considering previously trained Q-tables as inputs of our method. The extension/adaptation to deal with other optimization problems is also planned.

## References

[1] Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: A methodological tour d'horizon. *Eur. J. Oper. Res.*, 290(2):405-421, 2021.

[2] Teobaldo Bulhoes, Ruslan Sadykov, Anand Subramanian, and Eduardo Uchoa. On the exact solution of a large class of parallel machine scheduling problems. *J. Sched.*, 23:411-429, 2020.

[3] Behice Kayhan and Gokalp Yildiz. Reinforcement learning applications to machine scheduling problems: a comprehensive literature review. *J. Intell. Manuf.*, 34, 10 2021.

[4] Arthur Kramer and Anand Subramanian. A unified heuristic and an annotated bibliography for a large class of earliness-tardiness scheduling problems. *J. Sched.*, 22(1):21-57, 2019.

[5] Maria Lopes, Sérgio Souza, Marcone Souza, and Ana Bazzan. A reinforcement learning-based multi-agent framework applied for solving routing and scheduling problems. *Expert Syst. Appl.*, 131, 04 2019.