Beta
282389

University Examination Timetable Scheduling Using Constructive Heuristic Compared to Genetic Algorithm

Article

Last updated: 03 Jan 2025

Subjects

-

Tags

-

Abstract

Examination Timetable Scheduling can be defined as assigning a set of exams into a limited number of days and periods, subject to a set of constraints, some of which contradict each other. An issue that makes timetabling a challenging task most universities have to solve every semester. It usually takes days or even weeks to find a solution that does not even “entirely" satisfy the universities' constraints. Automating this task is really challenging, since timetabling problem is a Nondeterministic Polynomial time (NP) complete problem. The most known characteristic of NP-complete problems is that no fast solution to them is known. That is, the time required to solve the problem using any currently known algorithm increases exponentially as the size of the problem grows. NP-complete problems have tremendous solution space, so brute-force methods cannot be used . This research builds and compares the performance of two proposed solutions; Genetic Algorithm and Constructive Heuristic models when both used to solve a real-world examination time-tabling problem at Misr University for Science and Technology (MUST). This re-search shows how the Constructive Heuristic proposed outperformed the Genetic Algorithm in creating optimized schedules which solves all the students' conflicts. An easy to use, GUI desktop application was created to be used by all universities' members, to automate their timetabling tasks, the program creates many feasible schedules, meeting all requirements of MUST examination timetables, while reducing the pressure on the students, in seconds, which will result in saving a lot of time and effort for the universities' members.

DOI

10.21608/fuje.2022.157195.1018

Keywords

Constructive Heuristics, Examination Timetabling, Genetic Algorithm, Scheduling, artificial intelligence

Authors

First Name

Dina

Last Name

Salem

MiddleName

Ahmed

Affiliation

Computer Department, Faculty of Engineering, MUST University, 6th of October city, Egypt

Email

dina.almahdy@must.edu.eg

City

-

Orcid

0000-0002-6892-319X

Volume

6

Article Issue

1

Related Issue

39196

Issue Date

2023-01-01

Receive Date

2022-08-19

Publish Date

2023-01-01

Page Start

39

Page End

46

Print ISSN

2537-0626

Online ISSN

2537-0634

Link

https://fuje.journals.ekb.eg/article_282389.html

Detail API

https://fuje.journals.ekb.eg/service?article_code=282389

Order

3

Type

Original Article

Type Code

651

Publication Type

Journal

Publication Title

Fayoum University Journal of Engineering

Publication Link

https://fuje.journals.ekb.eg/

MainTitle

University Examination Timetable Scheduling Using Constructive Heuristic Compared to Genetic Algorithm

Details

Type

Article

Created At

24 Dec 2024