Estudo de heurísticas matemáticas para o problema de escalonamento de máquina simples

Abstract

This document presents a study of matheuristics for the common due date single machine scheduling problem, where the goal is to minimize earliness and tardiness penalties in the delivery of jobs. The problem is NP-hard, which justifies proposals of heuristics and metaheuristics for solving it over the years. The purpose of the work is to develop a method that combines metaheuristics and exact algorithms, the so-called matheuristics. In the course of this work, two mathematical models for the problem were validated. In all, five exact neighborhoods were implemented using hard fixing and soft fixing. The neighborhoods with hard fixing were inspired in Fix-and-Optimize (FixOpt) and Relaxation Induced Neighborhood Search (RINS). The neighborhood with soft fixing were inspired in Local Branching (LB). Among the implemented neighborhoods, the neighborhood inspired in RINS had the best results and it was combined with Variable Neighborhood Search (VNS) to obtain the final results. Computational tests were performed using benchmark instances of the problem and the results obtained in the work were compared with different results reported in the literature. The main contributions of this work were the study of mathematical models and the proposition of exact neighborhoods for the single machine common due date scheduling problem.