UNRELATED PARALLEL MACHINE SCHEDULING USING A HEURISTIC INTEGRATED WITH REINFORCEMENT LEARNING

This work investigates the problem of sequencing in unrelated parallel machines, considering sequence-dependent preparation times, release dates and different deadlines. The objective is to minimize the weighted sum of the penalties for anticipation and for delay. It is proposed to integrate the iterated local search meta-heuristic with the Q-Learning reinforcement learning technique to guide the local search phase. The resulting algorithm dynamically learns the best order to exploit local search operators by evaluating epsilon-gluttonous and Boltzmann policies. Computational experiments in 48 instances of the literature demonstrate that the epsilon-gluttonous policy offers the best balance between computational effort and solution quality. It is more effective at guiding learning, achieving equivalent or superior results, especially in larger instances with 60 tasks. Boltzmann's policy results in the longest execution times, without translating this cost into gains in the value of the objective function. Its low performance can be attributed to the initial temperature value, as a high value can prolong the random exploration phase and, as a result, the algorithm can take time to exploit the knowledge accumulated over the iterations.