Parallelizing the Microcanonical Optimization Metaheuristic: A Case Study for the Task Scheduling Problem

  • Stella C. S. Porto UFF
  • André M. Barroso UFF
  • José R. A. Torreão UFF

Resumo


The present work deals with the parallelization of the microcanonical optimization metaheuristic (µO), and implements a parallel algorithm for the task scheduling problem on heterogeneous processors under precedence constraints without communication delays. The (µO) algorithm consists of two iterative procedures - the initialization and the sampling phases, which are alternately applied. Our parallel implementations are based on a scheme where p processes execute altemate parallel versions of the initialization and sampling phases, coupled at a synchronization point. They have been implemented on a network of workstations using the MPI communication library, and an evaluation of the quality of the solulions generated has been performed for different sets of the algorithm parameters. The solution quality has been measured by the makespan reduction achieved in comparison with the best greedy algorithm, and with tabu search, for the same problem instances [7, 10]. The conditions under which the new algorithm is able to show a superior performance are then highlighted by our preliminary results.

Palavras-chave: Metaheuristic parallelization, microcanonical optimization, task scheduling, network of workstations

Referências

R. CORRÊA. A. FERREIRA and S.C.S. PORTO, Selected Algorithmic Techniques for Parallel Optimization, chapter in Handbook of Combinatorics, 1998, 407-456.

T. G. CRAINIC, M. TOULOUSE e M. GENDREAU, "Towards a Taxonomy of Parallel Tabu Search Algorithms", Research Report CRT-933. Centre de Recherche sur les Transpon s. Universilé de Montréal, 1993.

M. CREUTZ. "Microcanonical Monte Carlo Simulation", Physical Review Letters 50 (1983). p. 1411.

A. LINHARES and J.R.A. TORREÃO, "Microcanonical Optimization Applied to the Traveling Salesman Problem", Inrl. Journal of Modem Physics C 9(I)(1998). 133-146.

T. MAVRIDOU. P.M. PARDALOS, L. PITSOULIS and M.G.C. RESENDE, "Parallel Search for Combinatorial Optimization: Genetic Algorithms. Simulated Annealing, Tabu Search and GRASP", Proceedings of the Workshop on Parallel Algorithms for Irregularly Structured Problems. Lyon, France, September 4-6, 1995.

D.A. MENASCÉ and V. ALMEIDA, "Cosi-Performance Analysis of Heterogeneity in Supercomputer Architectures". Proceedings of the Supercomputing'90 Conference, New York, 1990.

D.A. MENASCÉ, S.C.S. PORTO and S. TRIPATHI. "Processor Assignment in Heterogeneous Parallel Architectures", Proceedings of the IEEE International Parallel Processing Symposium, 186-191, Beverly Hills. 1992.

S.C.S. PORTO, J.P.W. KITAJIMA, and C.C. RIBEIRO, "Perfomance Evaluation of a Parallel Tabu Search Task Scheduling Algorithm", accept for the Special Issue on High-Performance Computing for Operational Research of the Parallel Computing (1999).

S.C.S. PORTO and C.C. RIBEIRO," Parallel Tabu Search Message-Passing Synchronous Strategies for Task Scheduling under Precedence Constraints". Journal of Heuristics I (1996). 207-233.

S.C.S. PORTO and C.C. RIBEIRO. "A Tabu Search Approach to Task Scheduling on Heterogeneous Processors under Preeedence Constraints", International Journal of High-Speed Computing 7 (1995), 45-71.

M. REISER e S.S. LAVENBERG, "Mean Value Analysis of Closed Multichain Queueing Networks". Journal of the Association for Computing Machinery 27 (1980), 313-322.

E. TAILLARD. "Parallel Taboo Search Techniques for the Job Shop Scheduling Problem", ORSA Journal on Computing 6 (1994), 108-117.

J.R.A. TORREÃO, J.C.B. LEITE, O.G. LOQUES, and A.M. BARROSO, An Experiment with a New Heuristic for Task Scheduling in Real-Time Distributed Systems, Technical Report RT_01-97, Applied Computing & Automation, Universidade Federal Fluminense. Niterói. Brasil, January 1997.

J.R.A. TORREÃO and E. ROE, "Microcanonical Optimization Applied to Visual Processing", Physics Letters A 205 (1995). 377-382.
Publicado
29/09/1999
Como Citar

Selecione um Formato
PORTO, Stella C. S.; BARROSO, André M.; TORREÃO, José R. A.. Parallelizing the Microcanonical Optimization Metaheuristic: A Case Study for the Task Scheduling Problem. In: INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD), 11. , 1999, Natal. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 1999 . p. 149-156. DOI: https://doi.org/10.5753/sbac-pad.1999.19784.