Utilize este identificador para referenciar este registo:
https://hdl.handle.net/1822/12502
Título: | Pattern 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-chave: | Cutting 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 |
Data: | 26-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. |
Tipo: | Tese de doutoramento |
Descrição: | Tese de doutoramento em Engenharia Industrial e de Sistemas |
URI: | https://hdl.handle.net/1822/12502 |
Acesso: | Acesso aberto |
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 |