Modelos e algoritmos para o problema de sequenciamento de pedidos de clientes para minimização do atraso total

Abstract

In this work, we address the order scheduling problem, in which customer orders (composed of different individual tasks) are scheduled, where the objective function is the minimization of the total tardiness of completed orders. In the reviewed literature, less studies regarding the problem of sequencing of customer orders were found compared with other production environments, such as, parallel machines or flow shop. In this work, we present a new variant for that problem, where we explicitly consider the setup times of machines dependent on the production sequence, which belongs to the NP-hard class. Then, we propose a new formulation using linear integer programming, an adaptation of the OMDD heuristic (referred to as OMMD-S), and a heuristic called Model with Fixed Permutaion (MFP). The extensive computational simulations carried out show that the MFP matheuristic yields the best results, since it achieved the lowest average RDI (5,69%) considering the analyzed methods and the evaluated instances.