Utilize este identificador para referenciar este registo: https://hdl.handle.net/1822/12502

TítuloPattern sequencing models in cutting stock problems
Outro(s) título(s)Modelos para sequenciação de padrões em problemas de corte de stock
Autor(es)Lopes, Isabel da Silva
Orientador(es)Carvalho, J. M. Valério de
Palavras-chaveCutting stock
Pattern sequencing
Minimization of open stacks
Interval graphs
Linear ordering
Minimum interval graph completion
Corte de stock
Sequenciação de padrões
Minimização
Grafo de intervalos
Ordenação linear
Completamento mínimo
Data26-Abr-2011
Resumo(s)In this thesis, we address an optimization problem that appears in cutting stock operations research called the minimization of the maximum number of open stacks (MOSP) and we put forward a new integer programming formulation for the MOSP. By associating the duration of each stack with an interval of time, it is possible to use the rich theory that exists in interval graphs in order to create a model based on the completion of a graph with edges. The structure of this type of graphs admits a linear ordering of the vertices that de nes an ordering of the stacks, and consequently decides a sequence for the cutting patterns. The polytope de ned by this formulation is full-dimensional and the main inequalities in the model are proved to be facets. Additional inequalities are derived based on the properties of chordal graphs and comparability graphs. The maximum number of open stacks is related with the chromatic number of the solution graph; thus the formulation is strengthened by adding the representatives formulation for the vertex coloring problem. The model is applied to the minimization of open stacks, and also to the minimum interval graph completion problem and other pattern sequencing problems such as the minimization of the order spread (MORP) and the minimization of the number of tool switches (MTSP). Computational tests of the model are presented.
Nesta tese e abordado um problema de optimização que surge em operações de corte de stock chamado minimização do número máximo de pilhas abertas (MOSP) e e proposta uma nova formulação de programação inteira. Associando a duração de cada pilha a um intervalo de tempo, e possível usar a teoria rica que existe em grafos de intervalos para criar um modelo baseado no completamento de um grafo por arcos. A estrutura deste tipo de grafos admite uma ordenação linear dos vértices que define uma ordenação linear das pilhas e, por sua vez, determina a sequência dos padrões de corte. O politopo definido por esta formulação tem dimensão completa e prova-se que as principais desigualdades do modelo são facetas. São derivadas desigualdades adicionais baseadas nas propriedades de grafos cordais e de grafos de comparabilidades. O número máximo de pilhas abertas está relacionado com o número cromático do grafo solução, pelo que o modelo e reforçado com a formulação por representativos para o problema de coloração de vértices. O modelo e aplicado a minimização de pilhas abertas, e também ao problema de completamento mínimo de um grafo de intervalos e a outros problemas de sequenciação de padrões, tais como a minimização da dispersão de encomendas (MORP) e a minimização do número de trocas de ferramentas (MTSP). São apresentados testes computacionais do modelo.
TipoTese de doutoramento
DescriçãoTese de doutoramento em Engenharia Industrial e de Sistemas
URIhttps://hdl.handle.net/1822/12502
AcessoAcesso aberto
Aparece nas coleções:BUM - Teses de Doutoramento
DPS - Teses de Doutoramento

Ficheiros deste registo:
Ficheiro Descrição TamanhoFormato 
Isabel Cristina da Silva Lopes.pdf1,7 MBAdobe PDFVer/Abrir

Partilhe no FacebookPartilhe no TwitterPartilhe no DeliciousPartilhe no LinkedInPartilhe no DiggAdicionar ao Google BookmarksPartilhe no MySpacePartilhe no Orkut
Exporte no formato BibTex mendeley Exporte no formato Endnote Adicione ao seu ORCID