Flow-shop and job-shop problems. Complexity of problems. Solution Methods

Submitted by Ruth Quaresma de Freitas (ruth_quaresma@hotmail.com) on 2019-01-30T17:45:59Z No. of bitstreams: 1 MARIA SONIA NOGUEIRA - TESE PPGC 1980..pdf: 19279217 bytes, checksum: dc6f81bdecc4440b0d77a368358b4c16 (MD5) Made available in DSpace on 2019-01-30T17:45:59Z (GMT). No. of bitstreams: 1 MARIA SONIA NOGUEIRA - TESE PPGC 1980..pdf: 19279217 bytes, checksum: dc6f81bdecc4440b0d77a368358b4c16 (MD5) Previous issue date: 1980-03 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.