Algorítimo de busca em vizinhança com q-learning para a resolução do no-idle flow shop para minimização do atraso total

Abstract

This work addresses the No-Idle Permutation Flow Shop Problem (NIPFSP) to Minimize Total Tardiness. Initially, a Mixed Integer Linear Programming (MILP) model and a Mixed-Integer Quadratically Constrained Programming (MIQCP) model were proposed, aiming to structure the modeling foundations of the problem. The MILP and MIQCP models were computationally implemented, and their characteristics were validated. Exact experiments revealed the effectiveness of the MILP model in producing high-quality solutions for instances with the number of jobs ranging between 20 and 100 and with up to 5 machines. However, for problems with 10, 15, and 20 machines, the MILP model was unable to prove optimality within the established time limit, pointing to the need for approximate methods. Therefore, a hybrid metaheuristic was proposed that combines intensive local search with reinforcement learning (Q-learning) to adaptively explore the solution space in more difficult instances, named Iterated Noisy Local Search Q-learning (INLSQL), which was compared with other existing heuristic algorithms. Substantial performance gains were achieved through the Q-learning-guided strategy compared to the main algorithms reported in the reviewed literature.