Research on water resources optimal scheduling problem based on parallel biological computing

摘要

Water resource shortage has become one of the main factors restricting the rapid economic and social development of mankind, how limited water resources reasonable allocation to various users, protection of life and production, ecological water safety is facing an important problem in various countries. Water resources optimal scheduling problem also has a wide range of application space, which involves cost control and optimization of design expertise. The shortest flow path problem, as a well-known NP-complete problem and one of famous water resources optimal scheduling problem, has attracted the attention of many scholars. In this paper, we use a new parallel algorithm to solve the problem by basic DNA molecular operations. We reasonably design DNA chains that characterize cities and paths, take appropriate biological operations and get solutions of the task scheduling problem in proper length range with O(n(2)) time complexity. The ability of biological manipulation in the algorithm helps us better understand DNA computing, and can be widely used to solve more complex problems.