Return to search

Problema das sequ?ncias justas ponderadas

Submitted by Automa??o e Estat?stica (sst@bczm.ufrn.br) on 2018-02-21T21:29:05Z
No. of bitstreams: 1
BrunoJeffersonDeSousaPessoa_TESE.pdf: 1029802 bytes, checksum: fb7e1bbf01b30106e4b0a64511f955d1 (MD5) / Approved for entry into archive by Arlan Eloi Leite Silva (eloihistoriador@yahoo.com.br) on 2018-02-22T22:38:00Z (GMT) No. of bitstreams: 1
BrunoJeffersonDeSousaPessoa_TESE.pdf: 1029802 bytes, checksum: fb7e1bbf01b30106e4b0a64511f955d1 (MD5) / Made available in DSpace on 2018-02-22T22:38:00Z (GMT). No. of bitstreams: 1
BrunoJeffersonDeSousaPessoa_TESE.pdf: 1029802 bytes, checksum: fb7e1bbf01b30106e4b0a64511f955d1 (MD5)
Previous issue date: 2017-12-15 / Problemas de escalonamento aos quais s?o impostas restri??es relativas ?s dist?ncias
temporais entre sucessivas execu??es de uma mesma tarefa possuem um grande n?mero
de aplica??es, que variam desde o escalonamento de tarefas em sistemas de tempo real ?
produ??o de autom?veis em uma linha de montagem. O presente trabalho apresenta um
novo problema de otimiza??o, denominado de Problema das Sequ?ncias Justas Ponderadas
(PSJP), que faz parte dessa classe de problemas. Al?m do estudo da complexidade
computacional do PSJP, ? apresentada uma formula??o matem?tica baseada em programa??o
linear inteira mista e uma s?rie de cortes que aprimoram sua resolu??o via m?todos
exatos. Para resolv?-lo, foram elaborados um m?todo iterativo que reduz o n?mero de vari?veis
da formula??o proposta e uma solu??o heur?stica desenvolvida a partir da combina??o
de meta-heur?sticas cl?ssicas da literatura. Experimentos computacionais mostram
que, para um dado limite de tempo, as abordagens propostas aumentam significativamente
o n?mero de inst?ncias resolvidas, preservando-se a qualidade das solu??es. / 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.

Identiferoai:union.ndltd.org:IBICT/oai:repositorio.ufrn.br:123456789/24794
Date15 December 2017
CreatorsPess?a, Bruno Jefferson de Sousa
Contributors03553729406, Ara?jo, F?bio Meneghetti Ugulino de, 82675090468, Silva, Ivanovitch Medeiros Dantas da, 04665499462, Cabral, Luc?dio dos Anjos Formiga, 37383388372, Campelo Neto, Manoel Bezerra, 32171684372, Aloise, Daniel
PublisherPROGRAMA DE P?S-GRADUA??O EM ENGENHARIA EL?TRICA E DE COMPUTA??O, UFRN, Brasil
Source SetsIBICT Brazilian ETDs
LanguagePortuguese
Detected LanguageEnglish
Typeinfo:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis
Sourcereponame:Repositório Institucional da UFRN, instname:Universidade Federal do Rio Grande do Norte, instacron:UFRN
Rightsinfo:eu-repo/semantics/openAccess

Page generated in 0.0023 seconds