| Resumo: |
Este projecto visa o desenvolvimento e teste de ferramentas para resolução de problemas de posicionamento de figuras irregulares (Nesting) usando Programação por Restrições bem como a sua comparação com abordagens alternativas. O foco do projecto é colocado em duas questões cruciais para a eficiência da aplicação da Programação por Restrições (CP) a problemas combinatórios: a utilização de restrições globais e a definição de estratégias para exploração do espaço de pesquisa.
Os elementos da equipa concluiram com sucesso o projecto CLPNest, POSI/33757/SRI/2000, em Dezembro de 2002, no âmbito do qual foram desenvolvidas e testadas num protótipo ferramentas de Programação em Lógica por Restrições (CLP) para problemas de Nesting. Um outro resultado desse projecto é um conjunto de problemas e a identificação de heurísticas eficazes no melhoramento de resultados de pesquisa. O projecto CLPNest mostrou que as linguagens CLP são uma ferramenta de modelização muito útil para abordar problemas combinatórios.
O problema de Nesting pertence à classe dos problemas de cortes e empacotamentos. Neste problema, uma peça grande deve ser dividida em peças irregulares de menor dimensão, com o objectivo de minimizar o desperdício. Este problema tem uma grande relevância em todos os processos produtivos onde a matéria-prima deve ser cortada em peças pequenas e irregulares (tais como indústria do vestuário, calçado e mobiliário) e tem também implicações a nível ambiental, dado que a redução do desperdício implica a utilização de menor quantidade de matéria-prima.
Do ponto de vista da Investigação Operacional, as linguagens de CP podem ser encaradas como linguagens de modelização, oferecendo um conjunto grande de restrições primitivas e permitindo o desenvolvimento de estratégias de pesquisa à medida. A utilização de CP em alguns problemas combinatórios é facilitada pela utilização de "restrições globais", que reflectem as dependências entre as variáveis de um problema e são of  |
Resumo
Este projecto visa o desenvolvimento e teste de ferramentas para resolução de problemas de posicionamento de figuras irregulares (Nesting) usando Programação por Restrições bem como a sua comparação com abordagens alternativas. O foco do projecto é colocado em duas questões cruciais para a eficiência da aplicação da Programação por Restrições (CP) a problemas combinatórios: a utilização de restrições globais e a definição de estratégias para exploração do espaço de pesquisa.
Os elementos da equipa concluiram com sucesso o projecto CLPNest, POSI/33757/SRI/2000, em Dezembro de 2002, no âmbito do qual foram desenvolvidas e testadas num protótipo ferramentas de Programação em Lógica por Restrições (CLP) para problemas de Nesting. Um outro resultado desse projecto é um conjunto de problemas e a identificação de heurísticas eficazes no melhoramento de resultados de pesquisa. O projecto CLPNest mostrou que as linguagens CLP são uma ferramenta de modelização muito útil para abordar problemas combinatórios.
O problema de Nesting pertence à classe dos problemas de cortes e empacotamentos. Neste problema, uma peça grande deve ser dividida em peças irregulares de menor dimensão, com o objectivo de minimizar o desperdício. Este problema tem uma grande relevância em todos os processos produtivos onde a matéria-prima deve ser cortada em peças pequenas e irregulares (tais como indústria do vestuário, calçado e mobiliário) e tem também implicações a nível ambiental, dado que a redução do desperdício implica a utilização de menor quantidade de matéria-prima.
Do ponto de vista da Investigação Operacional, as linguagens de CP podem ser encaradas como linguagens de modelização, oferecendo um conjunto grande de restrições primitivas e permitindo o desenvolvimento de estratégias de pesquisa à medida. A utilização de CP em alguns problemas combinatórios é facilitada pela utilização de "restrições globais", que reflectem as dependências entre as variáveis de um problema e são oferecidas como uma biblioteca de funções.
Trabalho anterior realizado pelos membros da equipa mostrou que as restrições geométricas do problema de Nesting são tratadas de forma ineficiente pelas restrições primitivas. Por outro lado não há nos sistemas existentes restrições globais apropriadas para este problema. Já foi realizado algum trabalho preliminar com restrições globais para problemas de Nesting e os resultados são bastante promissores.
Este projecto pretende contribuir com algoritmos eficientes para manipulação das restrições de Nesting. Para obter boas soluções será igualmente importante o desenvolvimento de estratégias de pesquisa adequadas. Nesse sentido, as heurísticas propostas no âmbito do CLPNest serão desenvolvidas e integradas numa aplicação comum. Os resultados do projecto incluirão um protótipo ilustrando estratégias diversas para a obtenção de soluções num ambiente em que as restrições do problema são garantidas. |