title: A Parallel Biological Optimization Algorithm to Solve the Unbalanced Assignment Problem Based on DNA Molecular Computing.
abstract: The unbalanced assignment problem (UAP) is to optimally resolve the problem of assigning n jobs to m individuals (m < n), such that minimum cost or maximum profit obtained. It is a vitally important Non-deterministic Polynomial (NP) complete problem in operation management and applied mathematics, having numerous real life applications. In this paper, we present a new parallel DNA algorithm for solving the unbalanced assignment problem using DNA molecular operations. We reasonably design flexible-length DNA strands representing different jobs and individuals, take appropriate steps, and get the solutions of the UAP in the proper length range and O(mn) time. We extend the application of DNA molecular operations and simultaneity to simplify the complexity of the computation.
authors.affiliation: College of Information, Shanghai Ocean University, Shanghai 201306, China. zcwang1028@163.com.
authors.forename: Zhaocai
authors.initials: Z
authors.lastname: Wang
authors.affiliation: Center for Finance and Accounting Research of University of International Business and Economics, Beijing 100029, China. junp1980@163.com.
authors.forename: Jun
authors.initials: J
authors.lastname: Pu
authors.affiliation: College of Engineering Science and Technology, Shanghai Ocean University, Shanghai 201306, China. appll188@163.com.
authors.forename: Liling
authors.initials: L
authors.lastname: Cao
authors.affiliation: Key Laboratory of Digital Earth Science, Institute of Remote Sensing and Digital Earth, Chinese Academy of Sciences, Beijing 100094, China. jtan1980@163.com.
authors.forename: Jian
authors.initials: J
authors.lastname: Tan
mesh_terms: D039301:Computers, Molecular; D018803:Models, Economic
keywords: DNA molecules computing; NP-complete problem; biological optimization algorithm; the unbalanced assignment problem