Problemas industriais de seqüenciamento de padrões: alguns resultados de complexidade e novos modelos de busca local / Industrial pattern seguencing problems: some complexity results and new local search models

AUTOR(ES)
DATA DE PUBLICAÇÃO

2001

RESUMO

In this thesis we explore some industrial pattern sequencing problems arising in settings as distinct as the scheduling of flexible machines, the design of VLSI circuits, and the sequencing of cutting patterns. This latter setting presents us the minimization of open stacks problem, which is the main focus of our study. Some complexity results are presented for these sequencing problems, establishing a surprising connection between previously unrelated fields. New local search methods are also presented to deal with these problems, and their effectiveness is evaluated by comparisons with results previously obtained in the literature. The first method is derived from the simulated annealing algorithm, bringing new ideas from statistical physics. The second method advances these ideas, by proposing a collective search model based on two themes: (i) to explore the search space while simultaneously exhibiting search intensity and search diversity, and (ii) to explore the search space in proportion to the perceived quality of each region. Some preliminaries, given by coordination policies (to guide the search processes) and distance metrics, are introduced to support the model.

ASSUNTO(S)

complexidade pesquisa operacional escala de integração muito grande very large scale integration otimização computaÇÃo aplicada problema de minimização de pilhas abertas sequenciamento operations research permutations métodos heurísticos optimization sequencing complexity heuristic methods minimization of open stack problem permutações

ACESSO AO ARTIGO

Documentos Relacionados