Escalonamento com restrição de mão-de-obra: heuristicas combinatorias e limitantes inferiores

Autor(es)

Cristina Celia Barros Cavalcante

• Tipo de documento: Dissertação de Mestrado
• Imprenta: Campinas, SP.
• Instituição: Universidade Estadual de Campinas (UNICAMP). Instituto de Computação
• Data de defesa: 1998-08-28

Membros da banca

Cid Carvalho de Souza; Celso da Cruz Carneiro Ribeiro; João Carlos Setubal

• Orientador: Cid Carvalho de Souza

Resumo

Esta dissertação estuda o problema de escalonamento com restrição de mão-de-obra (SPLC) e apresenta algumas estratégias para obtenção de limitantes inferiores e de limitantes superiores para este problema NP-difícil. No que diz respeito à obtenção de limitantes inferiores para o SPLC, são apresentadas duas formulações de programação inteira e discutidos os limitantes inferiores obtidos com a relaxação linear de cada uma delas. Um algoritmo de branch-and-bound específico para o SPLC é também implementado na tentativa de se obter soluções exatas para este problema. Finalmente, é introduzida uma extensão, baseada em uma formulação de programação inteira, para um método existente na literatura para o cálculo de limitantes inferiores para problemas de escalonamento com restrição de recursos. Com relação à obtenção de limitantes superiores para o SPLC, são propostas e implementadas quatro estratégias heurísticas seqüenciais (heurística baseada em regras de prioridade, heurística baseada em classes de escalonamento, heurística baseada em programação linear e um algoritmo seqüencial de busca tabu) e duas estratégias paralelas e assíncronas (A-Team e um algoritmo paralelo de busca tabu). Um conjunto de instâncias de teste para o SPLC é gerado e disponibilizado como benchmark para ser usado na avaliação da qualidade dos limitantes inferiores e superiores obtidos neste trabalho e em outros disponíveis na literatura. Embora pouco sucesso tenha sido obtido com as estratégias propostas para obtenção de limitantes inferiores, no caso dos limitantes superiores, as estratégias paralelas e assíncronas propostas e implementadas neste trabalho mostraram-se altamente adequadas à obtenção de soluções de boa qualidade para o SPLC e são, atualmente, responsáveis pelas melhores soluções conhecidas para este problema. (AU)

• Processo FAPESP: 96/10270-8 - Escalonamento com restrição de mão-de-obra: um estudo comparativo de heurísticas combinatórias
• Beneficiário: Cristina Célia Barros Cavalcante
• Modalidade de apoio: Bolsas no Brasil - Mestrado