面向大学课程时间表的并行多视图搜索算法

doi:10.3778/j.issn.1002-8331.2101-0343

摘要/Abstract

摘要： 针对大学课程时间表问题，提出一种基于改进迭代局部搜索的并行多视图搜索算法进行求解。依据课程时间表问题特性设计包含八种基础邻域的多邻域集，并根据提升速度比制定基邻域选择概率设置规则。在迭代局部搜索过程中，运用多视图学习策略对多个局部搜索步骤进行视图共享，及时调整搜索方向以提升搜索效率。通过并行计算思想对算法优化，提升多视图搜索的收敛速度。实验结果表明，提出的算法求解精度更佳，且具有优异的扩展性和并行效率。

关键词: 大学课程时间表, 迭代局部搜索, 多视图学习, 并行计算

Abstract: For the university course timetable problem（UCTP）, this paper proposes a parallel iterative local search algorithm based on multi-view learning strategy to solve it. The algorithm designs a multi-neighborhood set with eight base neighborhoods according to the characteristics of UCTP, and formulates the base neighborhood selection probability setting rules based on the increase speed ratio. In the iterative local search process, a multi-view learning strategy with view pooling is presented to fuse the search results of different local search and the search direction is adjusted in time to improve the search efficiency. The algorithm is optimized through the idea of parallel computing to improve the convergence speed of multi-view search. Experimental results show that the proposed algorithm has better solution accuracy, and has excellent scalability and parallel efficiency.

Key words: university course timetable, iterative local search, multi-view learning, parallel computing

宋婷, 王栋, 许玉龙, 王昂. 面向大学课程时间表的并行多视图搜索算法[J]. 计算机工程与应用, 2022, 58(18): 304-310.

SONG Ting, WANG Dong, XU Yulong, WANG Ang. Parallel Multi-View Search Algorithm for University Course Timetable Problem[J]. Computer Engineering and Applications, 2022, 58(18): 304-310.

参考文献

[1] EVEN S，ITAI A，SHAMIR A.On the complexity of time table and multi-commodity flow problems[J].SIAM Journal on Computing，1975，5（4）：691-703.
[2] 逯建琦，南建国，李雪.改进的贪婪算法在无人机组网中的研究与应用[J].空军工程大学学报（自然科学版），2020，21（2）：41-46.
LU J Q，NAN J G，LI X.Research and application of improved greedy algorithm in UAV network[J].Journal of Air Force Engineering University（Natural Science Edition），2020，21（2）：41-46.
[3] BURKE E K，MCCOLLUM B，MEISELS A，et al.A graph-based hyper heuristic for timetabling problems[J].European Journal of Operational Research，2007，176：177-192.
[4] LYU Z P，HAO J K.Adaptive tabu search for course timetabling[J].European Journal of Operational Research，2010，200（1）：235-244.
[5] ALI M，T?RN A，VIITANEN S.A direct search simulated annealing algorithm for optimization involving continuous variables[J].Computers & Operations Research，2002，29（1）：87-102.
[6] ALZAQEBAH M，ABDULLAH S.Artificial bee colony search algorithm for examination timetabling problems[J].International Journal of Physical Sciences，2011，6（6）：4264-4272.
[7] THEPPHAKORN T，PONGCHAROEN P，HICKS C.An ant colonybased timetabling tool[J].International Journal of Production Economics，2014，149（1）：131-144.
[8] 陈璐，王秀.改进遗传算法求解走班制下的排课问题[J].计算机工程与应用，2019，55（6）：218-224.
CHEN L，WANG X.Solution to course-timetabling problem of mobile learning system based on improved genetic algorithm[J].Computer Engineering and Applications，2019，55（6）：218-224.
[9] MCCOLLUM B，SCHAERF A，PAECHTER B，et al.Setting the research agenda in automated timetabling：the second international timetabling competition[J].Informs Journal on Computing，2010，22（1）：120-130.
[10] MüLLER T.ITC2007 solver description：a hybrid approach[J].Annals of Operations Research，2009，172（1）：429.
[11] GEIGER M J.An application of the threshold accepting metaheuristic for curriculum based course timetabling[J].arXiv：0809.0757v1，2008.
[12] CLARK M，HENZ M，LOVE B.Quikfix a repair-based timetable solver[C]//Proceedings of the 7th PATAT Conference，2008.
[13] ABDULLAH S，TURABIEH H，MCCOLLUM B，et al.A hybrid metaheuristic approach to the university course timetabling problem[J].Heuristics，2012，18（1）：1-23.
[14] BELLIO R，GASPERO L D，SCHAERF A.Design and statistical analysis of a hybrid local search algorithm for course timetabling[J].Journal of Scheduling，2011，15（1）：49-61.
[15] BELLIO R，CESCHIA S，GASPERO L D，et al.Feature-based tuning of simulated annealing applied to the curriculum-based course timetabling problem[J].Computers & Operations Research，2016，65：83-92.
[16] 宋婷，陈矛，吴超，等.基于多类迭代局部搜索的自动化排课算法[J].计算机应用，2019，39（6）：1760-1765.
SONG T，CHEN M，WU C，et al.A multi-class iterated local search algorithm for course timetabling[J].Journal of Computer Applications，2019，39（6）：1760-1765.
[17] SONG T，LIU S Y，TANG X Y，et al.An iterated local search algorithm for the university course timetabling problem[J].Applied Soft Computing，2018，68：597-608.
[18] NAGATA Y，ONO I.A guided local search with iterative ejections of bottleneck operations for the job shop scheduling problem[J].Computers & Operations Research，2018，90：60-71.
[19] GASPERO L D，MCCOLLUM B，SCHAERF A.The second international timetabling：competition（ITC-2007）：curriculum-based course timetabling（track3）[R].Belfast，UK：Queen’s University，2007.