Spelling suggestions: "subject:"_programa??o fronteira"" "subject:"_programa??o inteiramente""
1 |
Problema das sequ?ncias justas ponderadasPess?a, Bruno Jefferson de Sousa 15 December 2017 (has links)
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.
|
2 |
Algoritmos meta-heur?sticos para a solu??o do problema do caixeiro viajante com m?ltiplas caronas / Metaheuristic algorithms for the solution of the traveling salesman with multiple ridesharingAra?jo, Guilherme Fernandes de 12 February 2016 (has links)
Submitted by Automa??o e Estat?stica (sst@bczm.ufrn.br) on 2016-08-16T20:15:31Z
No. of bitstreams: 1
GuilhermeFernandesDeAraujo_DISSERT.pdf: 1848505 bytes, checksum: eaa10d2add37ab0c93d005b148c492ee (MD5) / Approved for entry into archive by Arlan Eloi Leite Silva (eloihistoriador@yahoo.com.br) on 2016-08-17T22:17:58Z (GMT) No. of bitstreams: 1
GuilhermeFernandesDeAraujo_DISSERT.pdf: 1848505 bytes, checksum: eaa10d2add37ab0c93d005b148c492ee (MD5) / Made available in DSpace on 2016-08-17T22:17:58Z (GMT). No. of bitstreams: 1
GuilhermeFernandesDeAraujo_DISSERT.pdf: 1848505 bytes, checksum: eaa10d2add37ab0c93d005b148c492ee (MD5)
Previous issue date: 2016-02-12 / O Problema do Caixeiro Viajante com Caronas M?ltiplas (PCV-MCa) ? uma classe do Caixeiro Viajante Capacitado que apresenta a possibilidade de compartilhamento de assentos para passageiros aproveitando os deslocamentos do caixeiro entre as localidades do ciclo. O caixeiro divide o custo do trajeto com os passageiros embarcados. O modelo pode representar uma situa??o real em que, por exemplo, motoristas est?o dispostos a compartilhas trechos de sua viagem com turistas que pretendem se deslocar entre duas localidades visitadas pela rota do motorista, aceitando compartilhar o ve?culo com outros indiv?duos e visitando outras localidades do ciclo. / The Traveling Salesman with Multiple Ridesharing (TSP-MR) is a type of the Capacitated Traveling Salesman, which presents the possibility of sharing seats with passengers taking advantage of the paths the salesman travels through his cycle. The salesman shares the cost of a path with the boarded passengers. This model can portray a real situation in which, for example, drivers are willing to share parts of a trip with tourists that wish to move between two locations visited by the driver?s route, accepting to share the vehicle with other individuals visiting other locations within the cycle. This work proposes a mathematical formulation for the problem, and an exact and metaheuristics algorithms for its solution, comparing them.
|
3 |
Algoritmos de solu??o para o problema do caixeiro viajante com passageiros e quota / Solution algorithms for the traveling salesman problem with rideshare and quotaSilva, Jean Gleison de Santana 31 July 2017 (has links)
Submitted by Automa??o e Estat?stica (sst@bczm.ufrn.br) on 2017-11-01T21:17:50Z
No. of bitstreams: 1
JeanGleisonDeSantanaSilva_DISSERT.pdf: 1141115 bytes, checksum: 891de7a8a9407e8af54f241f1a174785 (MD5) / Approved for entry into archive by Arlan Eloi Leite Silva (eloihistoriador@yahoo.com.br) on 2017-11-07T22:09:47Z (GMT) No. of bitstreams: 1
JeanGleisonDeSantanaSilva_DISSERT.pdf: 1141115 bytes, checksum: 891de7a8a9407e8af54f241f1a174785 (MD5) / Made available in DSpace on 2017-11-07T22:09:47Z (GMT). No. of bitstreams: 1
JeanGleisonDeSantanaSilva_DISSERT.pdf: 1141115 bytes, checksum: 891de7a8a9407e8af54f241f1a174785 (MD5)
Previous issue date: 2017-07-31 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior (CAPES) / O Problema do Caixeiro Viajante com Passageiros e Quota pertence ? classe de Problemas
do Caixeiro Viajante com Quota. Neste problema, considera-se uma vantagem econ?mica
quando o caixeiro, viajando em um ve?culo privado, embarca passageiros que passam a
dividir as despesas da viagem com ele. O modelo pode representar situa??es reais onde
o motorista tem uma rota de visita de cidade predefinida, na qual a cada cidade est?
associado um b?nus, sendo demandada a coleta de um valor m?nimo desses b?nus, na
fun??o objetivo da variante investigada leva-se em conta a possibilidade da redu??o dos
custos do caixeiro embarcando pessoas em seu ve?culo. Um modelo matem?tico, seis
algoritmos evolucion?rios, um GRASP e um heur?stico s?o apresentados para o problema.
O comportamento dos algoritmos propostos ? analisado em um experimento computacional
com 48 inst?ncias. / The Traveling Salesman Problem with Ridesharing and Quota belongs to the class of Quota
Traveling Salesman problems. In this problem, it is considered the economic advantage
achieved when the salesman, traveling in a private vehicle, gives ride to passengers who
share travel expenses with him. The model can represent real situations where a driver
programs a route to visit cities, each of which associated with a bonus, with the requirement
of collecting a minimum sum of bonuses and taking into account the possibility of reducing
costs due to people embarked in his vehicle. A math model, six evolutionary algorithms, a
GRASP and one heuristic are presented for the problem addressed. The behavior of the
proposed algorithms is analyzed on a computational experiment with 48 instances.
|
Page generated in 0.0755 seconds