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

Abstract

In this work, the order sequencing problem is addressed, 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 revised literature, approaches that address the order sequencing problem with machine setup times are quite limited. We present a new variant for the problem, in which the setup times depending on the production sequence are explicitly considered. As the variant under study is NP-diffi cult, a new formulation using linear integer programming, an adaptation of the Order-Scheculing Modifi ed Due-Date heuristic (OMDD) (referred to as Order-Scheculing Modifi ed Due-Date Setup (OMMD-S)), an adaptation of the Framinan and Perez-Gonzalez heuristic (FP) (hereinafter referred to as Framinan and Perez-Gonzalez Setup (FP-S)), a model with Same Permutation in All Machines (SPAM), and a SPAM-JPO matheuristic hybrid based on Job-Position Oscillation (JPO) are proposed. The extensive computational experience carried out shows that for the small-sized evaluated instances the SPAM is the most effi cient, presenting the lowest average and standard deviation of the values of Relative Deviation Index (RDI), while for the large-sized evaluated instances it shows that the SPAM-JPO matheuristic hybrid and Mixed-integer linear programming (MILP) are the most effi cient, with SPAM-JPO matheuristic hybrid showing the lowest average and standard deviation of the RDI values.