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

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

作　　者：周康[1] 同小军[1] 刘文斌[2] 

机构地区：[1]武汉工业学院数理科学系,湖北武汉430023 [2]华中科技大学控制科学与工程系,湖北武汉430074

出　　处：《计算机应用》2007年第4期991-993,共3页journal of Computer Applications

基　　金：国家自然科学基金资助项目(60403002);湖北省自然科学基金资助项目(2005ABA233;2006ABA272);湖北省优秀中青年科技创新团队计划资助项目;湖北省教育厅社科研究资助项目(2005q092);浙江省自然科学基金资助项目(ZJNSF-Y105654)

摘　　要：排课表问题是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.

关 键 词：闭环DNA计算模型 排课表问题 批删除实验 批分离实验 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]