Algoritmos heuristicos e exatos para resolução do problema de sequenciamento em processadores paralelos
Felipe Martins Muller
DATA DE PUBLICAÇÃO
This thesis deals with the problem of scheduling n jobs on m identical parallel machines with the objective of minimizingthe total execution time (makespan).Two cases are considered: in the first one the jobs are independent and the processing times are positive integers; in the second case we have sequence dependent times. For the first case we propose a 3-PHASE heuristic: initial assignment, job reassignment and job interchange. The 3-PHASE algorithm is compared with three other heuristics chosen from the literature by its good known average performance. The new heuristic is also compared with an exact method in order to evaluate the quality of the solutions obtained by the heuristic. Extensive computational tests were performed for randomly generated problems and they exhibited that the 3-PHASE heuristic yields average solution values at least as good as (with only one exception) those obtained with any of the three alternative heuristics used for comparison. The 3-PHASE algorithm found the optimal solution in around 70% of the problems for wich the optimal solution were known. In the second case we also propose a three phase heuristic: initial assignment, tabu phase and post-optimization phase. This algorithm rruUcesuse of tabu search techniques and general insertion procedure called GENIUS, originally designed for the Traveling Salesman Problem and properly adapted for the scheduling problem. A nearest neighbour procedures was also adapted for the scheduling problem and was used in comparisons with the proposed method. An exact method was developed for the problem in question. Tests were performed in randomly generated problems in a structured fashion and in a non-structured fashion. Results for both cases are presented and commented
ACESSO AO ARTIGOhttp://libdigi.unicamp.br/document/?code=vtls000069995
- Sequenciamento de processadores paralelos utilizando a meta heurística busca Tabu
- Algoritmos paralelos para o problema da mochila.
- Novos algoritmos para resolução do problema de roteamento.
- Uma heurística de trocas para o problema de sequenciamento de tarefas em processadores uniformes
- O problema do corredor de comprimento mínimo : algoritmos exatos, aproximativos e heurísticos