Parallelizing the Microcanonical Optimization Metaheuristic: A Case Study for the Task Scheduling Problem - Porto, Stella C. S.; Barroso, André M.; Torreão, José R. A. (Anais do International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD); 1999: Anais do XI Symposium on Computer Architecture and High Performance ComputingDO - 10.5753/sbac-pad.1999.19784, 1999)
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.