基于分布式势博弈算法的排课方法研究

Study on Scheduling Assignment Based on Distributed Potential Algorithm

排课问题已被证明是NP完全问题,排课问题的难度随课表规模的增大而增加。通过对排课问题建立图形着色模型,采用分布式势博弈算法求解。分布式势博弈算法从局部最优入手,最终形成全局最优,适用于排课问题求解;同时势博弈算法对排课问题中课表微调问题的响应是高效的。实践表明,相较于遗传算法、模拟退火算法,分布式势博弈算法对解决排课系统问题具有独特优势。

Scheduling Problem has been proved to be an NP-complete problem,the difficulty of scheduling problem increases with increasing size of the curriculum.Through establishing graphics rendering model and applying to scheduling problem,a distributed potential algorithm is introduced.Distributed potential game algorithm starts to solve the problem from local optimum,which eventually forms the global optimum for the Scheduling Problem.At the same time the potential game algorithm is efficient in response to the course arrangement where there is a micro change in timetable.Practice shows that compared to genetic algorithms,simulated annealing algorithm,distributed game algorithm is unique and effective to solve the Scheduling Problem.