Enhancing the Sorting Layers in the Initial Stage of High School Timetabling
The high school timetabling problem (HSTP) is considered as an NP-Complete problem as the optimal solution for it, is still not discovered by any algorithm. Generally, NP-Complete problem was solved firstly by constructing the initial solution, in the construction phase. The initial solution will be...
Main Authors: | , , |
---|---|
Format: | Conference or Workshop Item |
Language: | English |
Published: |
2020
|
Subjects: | |
Online Access: | https://repo.uum.edu.my/id/eprint/27227/1/ISCAIE%202020%2059%2063.pdf |
_version_ | 1803629268499955712 |
---|---|
author | Arbaoui, Billel Wahid, Juliana Abdul-Rahman, Syariza |
author_facet | Arbaoui, Billel Wahid, Juliana Abdul-Rahman, Syariza |
author_sort | Arbaoui, Billel |
collection | UUM |
description | The high school timetabling problem (HSTP) is considered as an NP-Complete problem as the optimal solution for it, is still not discovered by any algorithm. Generally, NP-Complete problem was solved firstly by constructing the initial solution, in the construction phase. The initial solution will be improvised in the improvisation phase. KHE is an algorithm that generates initial solution of HSTP. The layer sorting procedure in KHE is based on a certain priority. For every two layers, the layers will be ranked based on the highest value of duration. If both layers have equal value of duration, the layer with the highest value of demand will be at a higher rank. If both layers have equal value of demand. The layer will be arranged according to the index value of the layer. These sorting criteria use the layer properties independently which causes non-good results after the time-assignment phase. Therefore, this study proposed a mathematical model based on the Markov Chain Model for the sorting procedure that combines the layer properties in a formula. The proposed model was executed with 40 datasets of XHSTT2014, and it shows better results on 25 datasets of XHSTT2014 compared to the KHE algorithm. The mathematical model based on Markov Chain proposed in this study is able to improvise the original sorting of KHE. |
first_indexed | 2024-07-04T06:35:09Z |
format | Conference or Workshop Item |
id | uum-27227 |
institution | Universiti Utara Malaysia |
language | English |
last_indexed | 2024-07-04T06:35:09Z |
publishDate | 2020 |
record_format | dspace |
spelling | uum-272272020-07-23T01:46:29Z https://repo.uum.edu.my/id/eprint/27227/ Enhancing the Sorting Layers in the Initial Stage of High School Timetabling Arbaoui, Billel Wahid, Juliana Abdul-Rahman, Syariza QA75 Electronic computers. Computer science The high school timetabling problem (HSTP) is considered as an NP-Complete problem as the optimal solution for it, is still not discovered by any algorithm. Generally, NP-Complete problem was solved firstly by constructing the initial solution, in the construction phase. The initial solution will be improvised in the improvisation phase. KHE is an algorithm that generates initial solution of HSTP. The layer sorting procedure in KHE is based on a certain priority. For every two layers, the layers will be ranked based on the highest value of duration. If both layers have equal value of duration, the layer with the highest value of demand will be at a higher rank. If both layers have equal value of demand. The layer will be arranged according to the index value of the layer. These sorting criteria use the layer properties independently which causes non-good results after the time-assignment phase. Therefore, this study proposed a mathematical model based on the Markov Chain Model for the sorting procedure that combines the layer properties in a formula. The proposed model was executed with 40 datasets of XHSTT2014, and it shows better results on 25 datasets of XHSTT2014 compared to the KHE algorithm. The mathematical model based on Markov Chain proposed in this study is able to improvise the original sorting of KHE. 2020 Conference or Workshop Item PeerReviewed application/pdf en https://repo.uum.edu.my/id/eprint/27227/1/ISCAIE%202020%2059%2063.pdf Arbaoui, Billel and Wahid, Juliana and Abdul-Rahman, Syariza (2020) Enhancing the Sorting Layers in the Initial Stage of High School Timetabling. In: 2020 IEEE 10th Symposium on Computer Applications & Industrial Electronics (ISCAIE), Malaysia, Malaysia, 18-19 April 2020. http://doi.org/10.1109/ISCAIE47305.2020.9108804 doi:10.1109/ISCAIE47305.2020.9108804 doi:10.1109/ISCAIE47305.2020.9108804 |
spellingShingle | QA75 Electronic computers. Computer science Arbaoui, Billel Wahid, Juliana Abdul-Rahman, Syariza Enhancing the Sorting Layers in the Initial Stage of High School Timetabling |
title | Enhancing the Sorting Layers in the Initial Stage of High School Timetabling |
title_full | Enhancing the Sorting Layers in the Initial Stage of High School Timetabling |
title_fullStr | Enhancing the Sorting Layers in the Initial Stage of High School Timetabling |
title_full_unstemmed | Enhancing the Sorting Layers in the Initial Stage of High School Timetabling |
title_short | Enhancing the Sorting Layers in the Initial Stage of High School Timetabling |
title_sort | enhancing the sorting layers in the initial stage of high school timetabling |
topic | QA75 Electronic computers. Computer science |
url | https://repo.uum.edu.my/id/eprint/27227/1/ISCAIE%202020%2059%2063.pdf |
work_keys_str_mv | AT arbaouibillel enhancingthesortinglayersintheinitialstageofhighschooltimetabling AT wahidjuliana enhancingthesortinglayersintheinitialstageofhighschooltimetabling AT abdulrahmansyariza enhancingthesortinglayersintheinitialstageofhighschooltimetabling |