NP problems remain unresolved and thus are still open. Many approaches have been developed to resolve them, some of which use parallel DNA computing or parallel computing in calculating large amounts of tasks in less than a moment. A parallel genetic algorithm (PGA), as implemented in this paper, is also an approach to solving NP, NP-hard, and NP-complete problems.

In this paper, the authors describe a scalable PGA as well as a sequential genetic algorithm (SGA) that they implemented to address generalized assignment problems, which are known to be NP-hard. They further show through this work the ambiguity of the PGA with regard to parallelization aspects. The results of the conducted tests and evaluation of the performance of the proposed algorithm demonstrate the potentiality of the proposed scalable PGA in solving the generalized assignment problem; this is the main contribution of this paper to the resolution of NP-hard optimization problems.

However, the authors do not discuss the SGA in detail in order to point out the differences between a PGA and its corresponding sequential counterparts (GAs). Furthermore, they neither provide pseudocode for the SGA nor conduct a test over the corresponding SGAs. Though the authors briefly compare the scalability properties of both sequential and parallel GAs, they do not quantitatively compare the performance of both algorithms.

Despite these weaknesses, I recommend this paper for researchers working on algorithmic or computational complexity, parallel computing, or algorithmic efficiency.