A general ontological timetabling-model driven metaheuristics approach based on elite solutions

2021
Timetabling is a managerial problem that recurringly appears in various domains such as education, transport, sports, and staff management. The combinatorial nature of this problem poses solution challenges that aggravate with an increase in the problem size. While heuristics and metaheuristics initially offered promise, the progress plateaued as attempts to solve even bigger problems showed exorbitant costs while sampling feasible solutions. This issue is criticized for the lack of exploiting the underlying problem structure and the prevailing fragmen-tation in modeling and solution approaches. To address these issues, we first propose a novel timetabling ontology that serves as a common modeling basis, resolving the existing heterogeneity across various application domains. This ontology facilitates mapping the anatomy of any real timetabling problem onto its general structure. Second, it offers a unique two-stage solution approach for solving this generalized problem. The first stage of this approach entails generating elite initial solutions by exploiting this general problem structure, while the second stage uses a metaheuristic to improve these solutions at a very low computational cost. Using a university timetabling problem, we demonstrate the applicability of this approach. The numerical results show that the proposed algorithm converges within a fraction of computational costs incurred by other techniques for comparable problem sizes. This research paves the way for consolidating efforts for the development of gener-alizable cross-domain timetabling approaches.
EXPERT SYSTEMS WITH APPLICATIONS
卷号:170
ISSN:0957-4174
来源机构
Imam Abdulrahman Bin Faisal University
收录类型
SSCI
发表日期
2021
学科领域
循证管理学
国家
沙特阿拉伯
语种
英语
DOI
10.1016/j.eswa.2020.114268
其他关键词
HYBRID GENETIC ALGORITHM; MATING OPTIMIZATION ALGORITHM; UNIVERSITY-COURSE; SEARCH ALGORITHM; SINGLE-TRACK; PROGRAMMING APPROACH; SCHEDULING PROBLEM; HEURISTICS; SYSTEM; SELECTION
EISSN
1873-6793
被引频次(WOS)
2
被引更新日期
2022-01
关键词
Timetabling Ontological model Metaheuristics Combinatorial optimization Simulated annealing