Problema das sequências justas ponderadas
Scheduling problems on which constraints are imposed with regard to the temporal distances between successive executions of the same task have numerous applications, ranging from task scheduling in real-time systems to automobile production on a mixedmodel assembly line. This paper introduces a n...
Na minha lista:
Autor principal: | |
---|---|
Outros Autores: | |
Formato: | doctoralThesis |
Idioma: | por |
Publicado em: |
Brasil
|
Assuntos: | |
Endereço do item: | https://repositorio.ufrn.br/jspui/handle/123456789/24794 |
Tags: |
Adicionar Tag
Sem tags, seja o primeiro a adicionar uma tag!
|
Resumo: | Scheduling problems on which constraints are imposed with regard to the temporal
distances between successive executions of the same task have numerous applications,
ranging from task scheduling in real-time systems to automobile production on a mixedmodel
assembly line. This paper introduces a new NP-hard optimization problem belonging
to this class of problems, namely the Weighted Fair Sequences Problem (WFSP). In
addition to the study of the computational complexity of the WFSP, we present a mathematical
formulation based on mixed-integer linear programming as well as a serie of cuts
that improve the problem resolution via exact methods. To solve the WFSP, we propose
an iterative method that greatly reduces the number of variables in the WFSP formulation
and a heuristic solution developed from the combination of classical metaheuristics from
the literature. Computational experiments show that, for a given time limit, the proposed
approaches significantly increase the number of instances solved, preserving the quality
of the solutions. |
---|