Escalonamento com restrição de mão-de-obra: um estudo comparativo de heurísticas combinatórias

• Processo: 96/10270-8
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Data de Início da vigência: 01 de julho de 1997
• Data de Término da vigência: 31 de agosto de 1998
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Matemática da Computação
• Pesquisador responsável: Cid Carvalho de Souza
• Beneficiário: Cristina Célia Barros Cavalcante
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Assunto(s): Otimização combinatória Escalonamento de processos Heurística Mão-de-obra
• Palavra(s)-Chave do Pesquisador: Algoritimos Heuristicos | Otimizacao Combinatoria

Resumo

O problema de escalonamento com restrição de mão-de-obra (SPLC) consiste em: dados um conjunto de Jobs cada qual com uma quantidade específica de mão-de-obra necessária para a sua execução, e um grafo de precedência entre estes Jobs, determinar um escalonamento para todos os Jobs que minimize o tempo total de execução e satisfaça as restrições de mão-de-obra e precedência entre Jobs. O SPLC é NP-difícil. O objetivo principal deste projeto é o desenvolvimento para o SPLC de heurísticas com potencial para paralelismo assíncrono como por exemplo Estratégias Paralelas e Assíncronas de Busca Tabu e A-Teams. Pretendemos também estudar formulação do SPLC usando Programação Linear Inteira. O objetivo neste caso é ter soluções exatas de bons limites inferiores para algumas instâncias do SPLC de maneira que possamos avaliar a qualidade das soluções obtidas pelas heurísticas a serem implementadas. (AU)

Publicações científicas

(Referências obtidas automaticamente do Web of Science e do SciELO, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores)

HEIPCKE‚ S.; COLOMBANI‚ Y.; CAVALCANTE‚ C.C.B.; SOUZA‚ C.C.. Scheduling under labour resource constraints. CONSTRAINTS, v. 5, n. 4, p. 415-422, 2000. (96/10270-8)

CAVALCANTE‚ C.C.B.; CARVALHO DE SOUZA‚ C.; SAVELSBERGH‚ M.W.P.; WANG‚ Y.; WOLSEY‚ L.A.. Scheduling projects with labor constraints. DISCRETE APPLIED MATHEMATICS, v. 112, n. 1, p. 27-52, 2001. (96/10270-8, 00/00308-5, 97/02990-3)

Publicações acadêmicas

(Referências obtidas automaticamente das Instituições de Ensino e Pesquisa do Estado de São Paulo)

CAVALCANTE, Cristina Célia Barros. Escalonamento com restrição de mão-de-obra: heuristicas combinatorias e limitantes inferiores. 1998. Dissertação de Mestrado - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação Campinas, SP.