A Problem Solving Environment for Combinatorial Optimization Based on Parallel Meta-heuristics

Computational grid offers a great potential solution to parallel meta-heuristics toward combinatorial optimization. However, it is quite difficult for specialists in combinatorial optimization to develop parallel meta-heuristics in extremely heterogeneous computational environment, starting from scratch without any toolkit. This paper presents a problem solving environment for combinatorial optimization based on parallel meta-heuristics (PSEPMH) to help specialists to harness heterogeneous computational resources and handle dynamic granularity control. PSEPMH requires specialist to decompose one problem into two sub-problems with divide-and-conquer framework just as generic sequential algorithm. Then compiler of PSEPMH generates mobile agent code that automatically forms adaptive multi-granularity parallel computing at runtime by cloning himself and distributing along dynamic, complex grid environment with the support of PSEPMH. Not only can PSEPMH relieve specialists´ burden, but also make use of the computational resources more efficiently.