.png){kind=icon}
返回
A hybrid algorithm for the university course timetabling problem using the improved parallel genetic algorithm and local search
.png){kind=icon}
PRE
AI
DOI：10.1007/s10489-020-01833-x.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Scheduling is one of the problems that has attracted the attention of many researchers over the years. The University Course Timetabling Problem (UCTP) is a highly constrained real-world combinatorial optimization task. Designing course timetables for academic institutions has always been challenging, because it is a non-deterministic polynomial-time hardness (NP-hard) problem. This problem attempts to assign specific timeslots and rooms to the events considering a number of hard and soft constraints. All hard constraints must be satisfied to achieve a feasible solution, whereas satisfying all soft constraints is not necessary. Although the quality of the solution is directly related to the number of soft constraints that are satisfied. One of the recent innovative methodologies for solving UCTP is the hybrid algorithm, which attempts to automate the timetabling design process so that it would be able to work with different instances of problem domains. In this paper, we present a hybrid method based on the Improved Parallel Genetic Algorithm and Local Search (IPGALS) to solve the course timetabling problem. The Local Search (LS) approach is used to strengthen the Genetic Algorithm (GA). The IPGALS has applied a representation of the timetable, which ensure the hard constraints would never be violated. Hard constraints are measured by Distance to Feasibility (DF) criterion. In fact, applying the DF criterion leads to achieving feasible solutions and promotes the performance of our algorithm. Due to the wide range of problem constraints, the proposed algorithm is performed in parallel to improve the GA searching process. The IPGALS algorithm is tested over BenPaechter and ITC-2007 standard benchmarks and compared with the state-of-the-art techniques in this literature. The experimental results confirm the effectiveness and the superiority of the proposed algorithm compared to other prominent methods for solving UCTP.
Keyword:
Genetic algorithm
Local search
University course timetabling problem
Distance to feasibility
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
3.5
论文数:
7.6K
被引数:
1.7W
机构
引用论文
.png){kind=icon}
分享收藏A bi-criteria hybrid Genetic Algorithm with robustness objective for the course timetabling problem
PREAI
分享收藏分享收藏
查看更多内容