• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Dissertação de Mestrado
DOI
10.11606/D.3.2006.tde-13032007-162724
Documento
Autor
Nome completo
Márcio Seiti Kawamura
E-mail
Unidade da USP
Área do Conhecimento
Data de Defesa
Imprenta
São Paulo, 2006
Orientador
Banca examinadora
Ronconi, Débora Pretti (Presidente)
Santoro, Miguel Cezar
Toledo, Franklina Maria Bragion de
Título em português
Aplicação do método branch-and-bound na programação de tarefas em uma única máquina com data de entrega comum sob penalidades de adiantamento e atraso.
Palavras-chave em português
Branch-and-bound
Pesquisa operacional
Programação de produção
Resumo em português
O objetivo desse trabalho é o de estudar o problema de programação de tarefas num ambiente produtivo com uma única máquina com data comum de entrega. Nesse caso, as tarefas, depois de processadas uma única vez na máquina, devem ser entregues em uma data comum e sofrem penalidades de adiantamento e de atraso conforme o instante em que são completadas. Na prática, esse problema é encontrado em casos de pedidos de lotes de produtos com data de entrega comum préespecificada, embarques para exportação e material químico ou misturas que têm vida média de curta duração. Problemas desse tipo são NP-hard (Hall, Kubiak & Sethi, 1991; Hoogeven & van de Velde, 1991), sendo comumente tratados na literatura através de heurísticas e meta-heurísticas. Visto não ser de nosso conhecimento a existência na literatura de tratamento desse problema através de métodos exatos, propôs-se a utilização de um algoritmo do tipo branch-and-bound para obtenção da solução ótima do problema que minimize a soma das penalidades de adiantamento e de atraso. No desenvolvimento do algoritmo, a utilização de propriedades do problema foi importante na elaboração de limitantes inferiores e regras de dominância que melhoraram a eficiência do modelo. Os experimentos realizados avaliaram o desempenho de diferentes critérios elaborados, como escolha do nó pai, limitante inferior, ordem de execução das estratégias e ordem de construção da seqüência. Os resultados obtidos mostraram-se robustos quando comparados com o benchmark da literatura e revelaram o bom desempenho do modelo para problemas de pequeno porte, superando o desempenho de programas de otimização comerciais.
Título em inglês
Branch-and-bound method application in a single machine earliness/tardiness scheduling problem with a common due date.
Palavras-chave em inglês
Brand-and-bound
Operations research
Scheduling
Resumo em inglês
The objective of this work is to study the single-machine scheduling problem with a common due date. In this case, jobs, after be processed only once in the machine, must be delivered in a common due date and they are penalized of earliness or tardiness according to their completion time. This problem is found in cases of batch production with prespecified common due date, exportation shipping and chemical material that has short half-life period. This kind of problem is NP-hard (Hall, Kubiak & Sethi, 1991; Hoogeven & van de Velde, 1991) and it has been treated in the literature by heuristics and meta-heuristics. Not having knowledge about previous treatment by exact methods in the literature, it was proposed the implementation of a branch-and-bound algorithm to obtain the optimal solution that minimizes the total weighted earliness and tardiness penalties. In the development of the algorithm, the utilization of problem properties was important to the elaboration of lower bounds and pruning rules that have enhanced the efficiency of the model. The realized tests have evaluated the performance of different criteria, like the choice of father node, lower bound, strategy execution order and sequence construction order. The obtained results have demonstrated robustness comparing to benchmark and they have revealed the good working of the model for small problems, overcoming optimization software performance.
 
AVISO - A consulta a este documento fica condicionada na aceitação das seguintes condições de uso:
Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange a todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome da pessoa autora do trabalho.
FichaCatalografica.pdf (12.04 Kbytes)
teseMarcioKawamura.pdf (493.07 Kbytes)
Data de Publicação
2007-04-03
 
AVISO: Saiba o que são os trabalhos decorrentes clicando aqui.
Todos os direitos da tese/dissertação são de seus autores
Centro de Informática de São Carlos
Biblioteca Digital de Teses e Dissertações da USP. Copyright © 2001-2018. Todos os direitos reservados.