EURO 2025 Leeds
Abstract Submission

2701. Reinforcement learning-based iterated local search for the unrelated parallel machine scheduling problem

Invited abstract in session MA-38: Automating the Design, Generation and Control of Optimization Algorithms 1, stream Data Science meets Optimization.

Monday, 8:30-10:00
Room: Michael Sadler LG19

Authors (first author is the speaker)

1. Arthur Kramer
Mathematics and Operations Research for Engineering, Mines Saint-Étienne
2. Ruan Myller Magalhães de Oliveira
UFCAT
3. Thiago Alves de Queiroz
Instituto de Matemática e Tecnologia, Universidade Federal de Goiás

Abstract

In this work, we propose an optimization method that combines Iterated Local Search (ILS), Variable Neighborhood Descent (VND) and Reinforcement Learning (RL) to solve the earliness and tardiness unrelated parallel machine scheduling problem with sequence and machine-dependent setup times that arises in just-in-time manufacturing systems. In this problem, a set of non-identical parallel machines are available to process a given set of tasks. Each task has a due date, two penalty weights (earliness and tardiness) and requires a machine-dependent processing time to be completed. In addition, a setup operation is necessary between the operation of two consecutive jobs. The objective is to schedule all tasks so that each machine process at most a job at time and that minimizes the total weighted earliness and tardiness penalty.
The state-of-the-art meta-heuristic method in the literature to solve this problem is a combination of ILS and a randomized VND where the neighborhoods inside the VND are explored in a random order. Thus, in this work we propose a RL-based method to define, at each iteration of the ILS, the exploration order of the neighborhood structures inside the VND instead of considering totally fixed or totally random orders. We model this decision problem as a Markov decision process and consider different policies and reward functions. Experimental tests show that the method is able to find solutions within 2% from the best-known solutions in the literature.

Keywords

Status: accepted

Back to the list of papers