Independent and cooperative parallel search methods for the generalized assignment problem

Author： Asahiro Yuichi Ishibashi Masahiro Yamashita Masafumi

ISSN： 1055-6788

Source： Optimization Methods and Software, Vol.18, Iss.2, 2003-04, pp. : 129-141

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

The generalized assignment problem is a representative NP-hard problem, for which many heuristic algorithms are known. In this article, two parallel heuristic algorithms are proposed, which are based on the ejection chain local search (EC) proposed by Yagiura et al. One is a simple parallelization called multistart parallel EC (MPEC) and the other is cooperative parallel EC (CPEC). In MPEC each search process independently explores search space while in CPEC search processes share partial information to cooperate with each other. The experimental results with 9 computers for large benchmark instances show that (1) MPEC and CPEC, respectively, run twice and 4 times faster than EC, and (2) compared to EC, the difference in quality between obtained solutions and theoretical lower bounds is reduced to $3/4$ and $2/3$ by MPEC and CPEC, respectively. It is said that these methods give us full benefit of parallelization, speedup and improvement for quality of solutions.