Submitted by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2018-02-07T18:59:59Z
No. of bitstreams: 2
Tese_Rainer X. Amorim.pdf: 6271497 bytes, checksum: 42feec49cd385dde2a106aee5c11c269 (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2018-02-07T19:00:25Z (GMT) No. of bitstreams: 2
Tese_Rainer X. Amorim.pdf: 6271497 bytes, checksum: 42feec49cd385dde2a106aee5c11c269 (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2018-02-07T19:00:25Z (GMT). No. of bitstreams: 2
Tese_Rainer X. Amorim.pdf: 6271497 bytes, checksum: 42feec49cd385dde2a106aee5c11c269 (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Previous issue date: 2017-10-06 / FAPEAM - Fundação de Amparo à Pesquisa do Estado do Amazonas / This research investigates scheduling problems with earliness and tardiness penalties
on single and parallel machine environments. This problem is also known in
the literature as Just-in-Time scheduling, system widely used in industries to reduce
inventories and costs, in order to lead product to be produced according to demand.
In this work we present a hybrid exact-heuristic algorithmic strategy, based on an
arc-time indexed integer programming formulation and a generalized evolutionary
heuristic based on a strong local search, to better solve classical parallel machine
scheduling problems involving weighted earliness-tardiness penalties, with independent
jobs and arbitrary processing times. Selected arcs from local optima solutions
generated by a genetic algorithm based on a strong local search (GLS) with generalized
pairwise interchanges are given as input to the arc-time formulation, to produce
better solutions than those obtained by both methods when used isolated. Computational
experiments present competitive results according to the literature. Our
proposed method also solves large instances up to 500 jobs in identical parallel machines. / Esta pesquisa investiga problemas de escalonamento com penalidades de antecipação
e atraso em ambiente mono e multiprocessado envolvendo máquinas paralelas. Este
problema é também conhecido na literatura como escalonamento Just-in-Time, sistema
amplamente utilizado em indústrias para reduzir estoques e os custos decorrentes, a fim
de que o produto seja produzido de acordo com a demanda. Neste trabalho é proposta
uma estratégia algorítmica híbrida exato-heurística, baseada em uma formulação de
programação inteira arc-time e um algoritmo evolucionário fortemente baseado em
busca local, para melhor resolver problemas clássicos de escalonamento em máquinas
paralelas envolvendo penalidades de antecipação e atraso, com tarefas independentes e
tempos de processamento arbitrários. Os arcos são selecionados das soluções ótimas
locais obtidas pelo algoritmo genético fortemente baseado em busca local (GLS) com
movimentos generalizados de troca de pares, que são fornecidos como entrada para
a formulação arc-time, para gerar soluções melhores do que as obtidas por ambos
os métodos quando utilizados isoladamente. Os experimentos computacionais apresentam
resultados competitivos em relação à literatura. O método proposto também
resolve instâncias de tamanho maior de até 500 tarefas em máquinas paralelas idênticas.
| Identifer | oai:union.ndltd.org:IBICT/oai:http://localhost:tede/6147 |
| Date | 06 October 2017 |
| Creators | Amorim, Rainer Xavier de, 92-99449-7663 |
| Contributors | secretaria@icomp.ufam.edu.br, Rodrigues, Rosiane de Freitas, Barreto, Raimundo da Silva, Santos, Eulanda Miranda dos, Barboza, Eduardo Uchoa, Pio, José Luiz de Souza |
| Publisher | Universidade Federal do Amazonas, Programa de Pós-graduação em Informática, UFAM, Brasil, Instituto de Computação |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFAM, instname:Universidade Federal do Amazonas, instacron:UFAM |
| Rights | http://creativecommons.org/licenses/by-nc-nd/4.0/, info:eu-repo/semantics/openAccess |
| Relation | -312656415484870643, 600, 500, 4163267508810754609 |
Page generated in 0.0025 seconds