A new parallel DNA algorithm to solve the task scheduling problem based on inspired computational model

作者：Wang, Zhaocai; Ji, Zuwen; Wang, Xiaoming; Wu, Tunhua^*; Huang, Wei

来源：Biosystems, 2017, 162: 59-65.

DOI：10.1016/j.biosystems.2017.09.001

• Parallel DNA computing
• The task scheduling problem
• Adleman-Lipton model
• NP-complete problem

As a promising approach to solve the computationally intractable problem, the method based on DNA computing is an emerging research area including mathematics, computer science and molecular biology. The task scheduling problem, as a well-known NP-complete problem, arranges n jobs to m individuals and finds the minimum execution time of last finished individual. In this paper, we use a biologically inspired computational model and describe a new parallel algorithm to solve the task scheduling problem by basic DNA molecular operations. In turn, we skillfully design flexible length DNA strands to represent elements of the allocation matrix, take appropriate biological experiment operations and get solutions of the task scheduling problem in proper length range with less than O(n(2)) time complexity.

• 出版日期2017-12
• 单位中国水利水电科学研究院; 北京大学; 温州医科大学; 上海海洋大学; 贵阳学院