A Parallel Biological Optimization Algorithm to Solve the Unbalanced Assignment Problem Based on DNA Molecular Computing

被引：19
|
作者：
Wang, Zhaocai [1 ]
Pu, Jun [2 ]
Cao, Liling [3 ]
Tan, Jian [4 ]
机构：
[1] Shanghai Ocean Univ, Coll Informat, Shanghai 201306, Peoples R China
[2] Univ Int Business & Econ, Ctr Finance & Accounting Res, Beijing 100029, Peoples R China
[3] Shanghai Ocean Univ, Coll Engn Sci & Technol, Shanghai 201306, Peoples R China
[4] Chinese Acad Sci, Inst Remote Sensing & Digital Earth, Key Lab Digital Earth Sci, Beijing 100094, Peoples R China
来源：
INTERNATIONAL JOURNAL OF MOLECULAR SCIENCES | 2015年 / 16卷 / 10期
基金：
中国国家自然科学基金;
关键词：
DNA molecules computing; the unbalanced assignment problem; biological optimization algorithm; NP-complete problem; COMPUTATION;
D O I：
10.3390/ijms161025338
中图分类号：
Q5 [生物化学]; Q7 [分子生物学];
学科分类号：
071010 ; 081704 ;
摘要：
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.
引用
收藏
页码：25338 / 25352
页数：15
相关论文
共 50 条
  • [21] Molecular Beacon Based DNA Computing Model for 0-1 Programming Problem
    Huang, Xiaohui
    Yin, Zhixiang
    Zhi, Lingying
    Hu, Juan
    2009 FOURTH INTERNATIONAL CONFERENCE ON BIO-INSPIRED COMPUTING: THEORIES AND APPLICATIONS, PROCEEDINGS, 2009, : 99 - 103
  • [22] Genetic algorithm in DNA computing: A solution to the maximal clique problem
    LI Yuan
    ChineseScienceBulletin, 2004, (09) : 967 - 971
  • [23] Genetic algorithm in DNA computing: A solution to the maximal clique problem
    Li, Y
    Fang, C
    Qi, OY
    CHINESE SCIENCE BULLETIN, 2004, 49 (09): : 967 - 971
  • [24] A new parallel algorithm to solve one classic water resources optimal allocation problem based on inspired computational model
    Ji, Zuwen
    Wang, Zhaocai
    Deng, Anjun
    Huang, Wei
    Wu, Tunhua
    DESALINATION AND WATER TREATMENT, 2019, 160 : 214 - 218
  • [25] A New Biologically DNA Computational Algorithm to Solve the k-Vertex Cover Problem
    Zhao, Kai
    Wang, Zhaocai
    Lu, Yunzhao
    Qin, Jiangfeng
    Tan, Jian
    JOURNAL OF COMPUTATIONAL AND THEORETICAL NANOSCIENCE, 2015, 12 (03) : 524 - 526
  • [26] Fast parallel molecular solutions for DNA-based supercomputing: the subset-product problem
    Ho, M
    BIOSYSTEMS, 2005, 80 (03) : 233 - 250
  • [27] Fast parallel molecular solution to the dominating-set problem on massively parallel bio-computing
    Guo, MY
    Ho, MSH
    Chang, WL
    PARALLEL COMPUTING, 2004, 30 (9-10) : 1109 - 1125
  • [28] Problem-specific Knowledge based heuristic algorithm to solve Satellite Broadcast scheduling problem
    Salman, Ayed
    Ahmad, Imtiaz
    Omran, Mahamed G. H.
    2012 THIRD GLOBAL CONGRESS ON INTELLIGENT SYSTEMS (GCIS 2012), 2012, : 364 - 368
  • [29] A molecular computing model for 3-coloring graph problem based on circular DNA branch migration
    Cheng, Zhang
    Jing, Yang
    Jin, Xu
    2009 FOURTH INTERNATIONAL CONFERENCE ON BIO-INSPIRED COMPUTING: THEORIES AND APPLICATIONS, PROCEEDINGS, 2009, : 302 - 306
  • [30] DNA-Based Molecular Computing, Storage, and Communications
    Liu, Qiang
    Yang, Kun
    Xie, Jialin
    Sun, Yue
    IEEE INTERNET OF THINGS JOURNAL, 2022, 9 (02) : 897 - 915
12345