Sequenciamento e alocação de operações em flow-shops com restrições sobre os recursos compartilhados e sobre os prazos de entrega dos tarefas : uma abordagem de busca orientada por restrições

Resumo: O flow-shop, assim como a grande maioria dos problemas de scheduling, é un problema cuja complexidade computacional cresce exponencialmente com a sua dimensão. Para diminuir esta complexidade, geralmente são feitas hipóteses que simplificam o modelo da planta mediante o relaxamento de restrições. Grande parte destas hipóteses dizem respeito aos instantes de tempo em que as tarefas devem ser alocadas e às disponibilidades dos recursos compartilhados. Entrentanto, na indústria de processos químicos, que é a principal área de aplicação do fIow-shop, estas restrições não podem ser relaxadas, porque o alto custo dos produtos que são produzidos exige que as instalações disponíveis sejam utilizadas da melhor maneira possível. Além do mais, o atendimento rápido aos clientes é o principal objetivo, o qualsó é alcançado se as restrições temporais impostas pelo processo produtivo e pela demanda do mercado são obedecidas.Neste trabalho propõe-se uma estratégia de solução para o problema de fIow-shop que não admite a relaxação das restrições sobre os recursos compartilhados e sobre os instantes de tempo em que as tarefas devem ser alocadas. A estratégia proposta combina técnicas de Inteligência Artificial (IA), que têm por objetivo satisfazer as restrições do problema, com a técnica Branch-and-Bound (BAB) clássica da Pesquisa Operacional (PO), que permite alcançar o objetivo do problema que é minimização do tempo de conclusão das tarefas, através da maximização da utilização dos recursos compartilhados. As técnicas de IA utilizadas são a análise e propagação de restrições que, juntamente com heurísticas de aIocação de tarefas,permitem uma redução significativa do espaço de soluções e de busca do problema. O uso conjunto do BAB com propagação de restriçõese heurísticas resulta em um algoritmo de busca em árvore eficiente, no sentido de que ele geralmente consegue obter soluções ótimas sem precisar pesquisar um elevado número de nósAbstract: Not informe