Metaheuristics is a powerful and general strategy to practically solve computationally difficult problems in many fields, such as supply chain management, bioinformatics and so on. However, as the requirements and the constraints of the problems become much more complex, the problem sizes become enormous; even metaheuristics algorithms require much computational time. Parallelization is one solution of speeding algorithms up: By using more than one computers, the reduction of the computational time is expected. While it seems to be a very natural
solution, designing a good parallelized version of a given algorithm is not trivial, because naive parallelization may be detrimental to the overall  strategy of the original algorithm.
In this talk, we first review general ideas of metaheuristics and its flexibility and generality through some examples of applications to problems in logisitics and bioinformatics. We then consider the parallelization of metaheuristics algorithms,
especially, ones based on the local-search based strategy. We explain the points of the parallelization from the viewpoint of granularity of algorithms, and present some parallelization methods based on them.