Um algoritmo Branch and Cut para o Problema das Sequências Justas Ponderadas

Abstract

This work address the Weight Fair Sequence Problem (WFSP), a optimization pro blem recently introduced in the scientific literature that can be classified as a Distance constrained scheduling problem. It covers numerous applications in different areas, ran ging from minimizing the cost of automobile production in a mixed-model assembly line to the scheduling of maintenance service to machines in a factory. The WFSP is a perio dic scheduling problem with a finite time horizon that, given a set of task with different priorities, it must build a sequence of tasks executions such that the maximum product between the largest temporal distance between two consecutive executions of a task and its priority is minimized. This work proposes some adjustments to the classical mathe matical formulation utilized for the WFSP and introduces the use of a Branch-and-Cut method. The computational experiments have shown that the proposed approach has found a larger number of optimal solutions in a smaller time when compared with the classical mathematical model.