Utilize este identificador para referenciar este registo:
https://hdl.handle.net/1822/12502
Registo completo
Campo DC | Valor | Idioma |
---|---|---|
dc.contributor.advisor | Carvalho, J. M. Valério de | - |
dc.contributor.author | Lopes, Isabel da Silva | - |
dc.date.accessioned | 2011-06-02T16:04:07Z | - |
dc.date.available | 2011-06-02T16:04:07Z | - |
dc.date.issued | 2011-04-26 | - |
dc.date.submitted | 2011-02-03 | - |
dc.identifier.uri | https://hdl.handle.net/1822/12502 | - |
dc.description | Tese de doutoramento em Engenharia Industrial e de Sistemas | por |
dc.description.abstract | 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. | por |
dc.description.abstract | 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. | por |
dc.description.sponsorship | Fundação para a Ciência e a Tecnologia (FCT), programa de financiamento QREN-POPH-Tipologia 4.1-Formação Avançada comparticipado pelo Fundo Social Europeu e por fundos do MCTES (Bolsa individual com a refer^encia SFRH/BD/32151/2006) entre 2006 e 2009, e pela Escola Superior de Estudos Industriais e de Gest~ao do Instituto Polit ecnico do Porto (Bolsa PROTEC com a refer^encia SFRH/BD/49914/2009) entre 2009 e 2010. | por |
dc.language.iso | eng | por |
dc.rights | openAccess | por |
dc.subject | Cutting stock | por |
dc.subject | Pattern sequencing | por |
dc.subject | Minimization of open stacks | por |
dc.subject | Interval graphs | por |
dc.subject | Linear ordering | por |
dc.subject | Minimum interval graph completion | por |
dc.subject | Corte de stock | por |
dc.subject | Sequenciação de padrões | por |
dc.subject | Minimização | por |
dc.subject | Grafo de intervalos | por |
dc.subject | Ordenação linear | por |
dc.subject | Completamento mínimo | por |
dc.title | Pattern sequencing models in cutting stock problems | por |
dc.title.alternative | Modelos para sequenciação de padrões em problemas de corte de stock | - |
dc.type | doctoralThesis | por |
dc.subject.udc | 519.874 | - |
Aparece nas coleções: | DPS - Teses de Doutoramento |
Ficheiros deste registo:
Ficheiro | Descrição | Tamanho | Formato | |
---|---|---|---|---|
Isabel Cristina da Silva Lopes.pdf | 1,7 MB | Adobe PDF | Ver/Abrir |