| Numa aplicação paralela constituída de um conjunto finito de processadores idênticos e n tarefas com ordem de precedência, objetivamos encontrar um escalonamento dessas tarefas nos processadores que minimize o tempo total gasto na execução da aplicação. Uma tarefa só pode ser executada depois do término de suas predecessoras. Assim, considerando tempos iguais de execução e comunicação, uma tarefa poderá ser alocada em qualquer processador p, desde que o tempo de início exceda aquele de cada predecessora em uma ou duas unidades, dependendo se esta foi alocada em p ou outro processador, respectivamente. Uma forma de resolver este problema, que é NP-Difícil, é através de um algoritmo Branch & Bound, no qual métodos para obtenção de bons limites inferiores e superiores são fundamentais. Propomos uma nova heurística para o problema, com o objetivo de melhorar os limites superiores obtidos com heurísticas já conhecidas. A nova ideia se baseia em, a cada instante, verificar o estado de cada processador e escolher a tarefa prioritária a ser alocada nele. Dizemos que uma tarefa i tem prioridade sobre j quando i está mais distante que j das tarefas maximais (isto é, das tarefas que não têm sucessoras), no grafo direcionado que representa a ordem. Como o conjunto de processadores não possui uma estrutura específica, não estabelecemos um critério de prioridade entre eles. Uma unidade de tempo após a outra, analisamos o estado de um processador livre e, em um conjunto constituído pelas tarefas já liberadas e pela tarefa cujo último predecessor foi alocado naquele mesmo processador, escolhemos a mais prioritária (se o conjunto for não vazio) e a alocamos naquele processador. Essa nova abordagem trouxe melhoras significativas sobre vários testes com relação às heurísticas anteriores, e pode contribuir para um futuro desenvolvimento de um algoritmo Branch & Bound para o problema.
Apoio: UFC e CNPq.
|