排课表问题的闭环DNA计算模型的算法

Algorithm of closed circle DNA computing model for time-table problem

排课表问题是NP-完全问题。基于闭环DNA计算模型引入多种生化实验得出求解排课表问题的DNA算法。本算法采用两部编码方式产生初始数据池,引入批删除实验解决了教师和班级的冲突问题和同班课问题;引入批分离实验解决了正常合班课问题和教师时间要求问题;引入电泳实验解决了排课的均衡分配问题;引入标记实验得到了排课表问题的全局最优解集,并给出了算法的生化实现过程。最后,对算法的正确性进行了证明,并讨论了算法的复杂性。

Time-table problem is a NP-complete problem. Algorithm of DNA computing for time-table problem was obtained with introducing manifold biochemical experiments on closed circle DNA computing model. The algorithm produced initialization pool of data using two DNA encoding modes. It solved the problem of the conflict between teacher and grade and the problem of incorporate-class class by introducing group deleting experiment, solved the problem of normal incorporate-class class and problem of teacher＇s request of time by introducing group separate experiment, solved the problem of how to balance the scheme of time-table by introducing electrophorcsis experiment, and obtained a set of whole-optimizatlon solution by introducing mark experiment. And the process of algorithm＇s realization was put forward. Finally, validity of the algorithm was proved, and complexity of the algorithm was discussed.