期刊
EXPERT SYSTEMS WITH APPLICATIONS
卷 170, 期 -, 页码 -出版社
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.eswa.2020.114268
关键词
Timetabling; Ontological model; Metaheuristics; Combinatorial optimization; Simulated annealing
Timetabling is a common managerial issue with solution challenges that worsen with increasing problem size. Current heuristic methods face issues, prompting the proposal of a two-stage solution approach based on an ontology to address the problem.
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据