Submitted by Maike Costa (maiksebas@gmail.com) on 2016-04-27T14:06:26Z
No. of bitstreams: 1
arquivo total.pdf: 1831708 bytes, checksum: edf5d3b8c2b5483f249063f565ba3024 (MD5) / Made available in DSpace on 2016-04-27T14:06:26Z (GMT). No. of bitstreams: 1
arquivo total.pdf: 1831708 bytes, checksum: edf5d3b8c2b5483f249063f565ba3024 (MD5)
Previous issue date: 2015-04-14 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This work proposes a uni ed heuristic algorithm for a large class of earlinesstardiness
(E-T) scheduling problems. We consider single/parallel machine E-T problems
that may or may not consider some additional features such as idle time, setup times and
release dates. In addition, we also consider those problems whose objective is to minimize
either the total (average) weighted completion time or the total (average) weighted
ow
time, which arise as particular cases when the due dates of all jobs are either set to zero or
to their associated release dates, respectively. The developed local search based metaheuristic
framework is quite simple, but at the same time relies on sophisticated procedures
for e ciently performing local search according to the characteristics of the problem. The
algorithm was tested in hundreds of instances of several E-T problems and particular cases.
The results obtained show that our general heuristic is capable of producing high quality
solutions when compared to the best ones available in the literature that were obtained by
speci c methods. Moreover, the algorithm was tested on a new set of instances proposed
for the most general case (Rjrj ; sk
ij jPw0j Ej + wjTj) of the class of problems considered,
in order to validate the method. / Esta disserta c~ao prop~oe uma heur stica uni cada para uma classe de problemas de
sequenciamento da produ c~ao com penalidades por antecipa c~ao e atraso. S~ao considerados
problemas que envolvem uma ou m ultiplas m aquinas e que podem, ou n~ao, considerar algumas
particularidades, tais como: a inser c~ao de tempos ociosos entre as tarefas, tempos
de setup e datas de libera c~ao distintas. Al em desses problemas, tamb em s~ao considerados
os em que a fun c~ao objetivo e de minimizar tanto o a soma (ponderada) dos tempos de t ermino
das tarefas, quanto a soma (ponderada) dos tempos de
uxo das tarefas, que surgem
como casos particulares quando as datas de entrega de todas as tarefas s~ao de nidas com
zero ou iguais a suas respectivas datas de libera c~ao, respectivamente. A meta-heur stica
baseada em busca local proposta e simples, mas cont em procedimentos so sticados que
possibilitam uma execu c~ao e ciente da busca local, de acordo com as caracter sticas do
problema. O algoritmo foi testado em centenas de inst^ancias de problemas envolvendo
penalidades por antecipa c~ao e atraso e em casos particulares. Os resultados obtidos mostram
que a heur stica proposta e capaz de produzir solu c~oes de alta qualidade quando
comparadas com os melhores dispon veis na literatura, os quais foram obtidos por m etodos
espec cos. Al em disso, o algoritmo foi testado em um novo conjunto de inst^ancias
propostas para caso mais geral (Rjrj ; sk
ij jPw0j Ej +wjTj) da classe de problemas considerados,
com o intuito de validar o m etodo.
| Identifer | oai:union.ndltd.org:IBICT/oai:tede.biblioteca.ufpb.br:tede/8159 |
| Date | 14 April 2015 |
| Creators | Kramen, Arthur Harry frederico Ribeiro |
| Contributors | Subramanian, Anand |
| Publisher | Universidade Federal da Paraíba, Programa de Pós-Graduação em Engenharia de Produção, UFPB, Brasil, Engenharia de Produção |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFPB, instname:Universidade Federal da Paraíba, instacron:UFPB |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | -7829092827138436175, 600, 600, 600, 600, -2166229310001672562, 2551182063231974631, 3590462550136975366 |
Page generated in 0.0025 seconds