A biological algorithm to solve the assignment problem based on DNA molecules computation

摘要

The assignment problem (AP) is to optimally solve the task of assigning n jobs to n individuals, such that minimum cost or maximum profit can be obtained. It is a vitally important NP-complete problem in operation management and applied mathematics, having a wide range of applications. In this paper, we present a new parallel DNA algorithm to solve the assignment problem using DNA molecular operations. Meanwhile, we design flexible length DNA strands to represent different jobs and individuals, take appropriate steps and get the solutions of the AP in proper length range and with time complexity. We extend the application of DNA molecular operations and simultaneity reduce the complexity of the computation.