Problemas "flow-shop" e "job-shop". Complexidade dos problemas. Métodos de solução

• Ano de defesa: 1980
• Autor(a) principal: NOGUEIRA, Maria Sônia.
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de Campina Grande; Brasil; Centro de Ciências e Tecnologia - CCT; PÓS-GRADUAÇÃO EM CIÊNCIA DA COMPUTAÇÃO; UFCG
• Palavras-chave em Português: Flow-shop.; Job-shop.; Algoritmos.; Complexidade dos problemas.; Métodos de solução.; Algorithms.; Complexity of problems.; Solution methods.; Ciência da computação.
• Link de acesso: http://dspace.sti.ufcg.edu.br:8080/jspui/handle/riufcg/2643

Este trabalho consta de um estudo detalhado dos problemas "Flow-Shop" e "Job-Shop". Algoritmos exatos são dados para estes problemas. Dentre os algoritmos exatos, tem-se alguns algoritmos polinomiais para problemas muito particulares e alguns algoritmos enumerativos para problemas gerais . Estes problemas pertencem à classe NP-Completa, uma classe de problemas muito complicados e que agora não foram escritos algoritmos mais simples que os algoritmos mais simples que os algoritmos enumerativos para solucionar tais problemas. Devido ao crescimento exponencial com o número de jobs e maquinas dos algoritmos enumerativos, outros algoritmos serão analisados. Estes são chamados Heurísticos, muito importantes na teoria "schedule" devido a simplicidade e viabilidade das soluções. Finalmente, efeito um estudo sobre a pior solução de problemas "Flow-Shop" através de alguns métodos heurísticos.