As a promising approach to solve the computationally intractable problem, the method based on dnacomputing is an emerging research area including mathematics, computer science and molecular biology. The task scheduli...
详细信息
As a promising approach to solve the computationally intractable problem, the method based on dnacomputing 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. (C) 2017 Published by Elsevier Ireland Ltd.
暂无评论