多处理机独立任务调度问题的DNA计算机算法

Molecular Solutions for Independent Task Scheduling Problem on DNA-based Supercomputing

任务调度是提高多处理机系统效率的一个关键问题,许多任务调度问题已被证明是NP难问题.对于多处理机独立任务调度问题,采用粘贴模型,给出了一种新的该类问题的DNA计算模型.我们首先提出了基于分子生物技术的多处理机独立任务调度问题的DNA算法,算法的关键是对任务分配的恰当的编码,以便于使用常规的生物操作及生物酶来完成解的产生及最终解的分离.依据分子生物学的实验方法,证明所提出的算法是有效和可行的;其次指出了该算法的优点、存在的问题及将来进一步的研究方向.

Task scheduling is a NP-hard problem and is an integral part of parallel and distributed computing. In this paper, implementation ideas and methods to solve independent task scheduling problem which is an engineering related combinatorial problem using this DNA computing approach is presented. The objective of solution of the independent task scheduling p ：oblem is to find an optimal scheduling that can satisfy with resources load balancing. The proposed algorithms show promising results that DNA computing approach can be well-suited for solving such real-world application in the near future.