Algoritmos heuristicos e exatos para resolução do problema de sequenciamento em processadores paralelos
Felipe Martins Muller
TESE
Português
(Broch.)
T/UNICAMP M912a
Campinas, SP : [s.n.], 1993.
[129] f. : il.
Orientador: Paulo Morelato França, Michel Gendreau
Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica
Resumo: Não informado
Abstract: 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...
Ver mais
Abstract: 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.
Ver menos
Algoritmos heuristicos e exatos para resolução do problema de sequenciamento em processadores paralelos
Felipe Martins Muller
Algoritmos heuristicos e exatos para resolução do problema de sequenciamento em processadores paralelos
Felipe Martins Muller
Exemplares
Nº de exemplares: 2
Não existem reservas para esta obra