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...

Full description

Bibliographic Details
Main Authors: Arbaoui, Billel, Wahid, Juliana, Abdul-Rahman, Syariza
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