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.

PDF Restricted to Registered users only Download (1MB) | Request a copy

Abstract

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.

Item Type:	Conference or Workshop Item (Paper)
Additional Information:	INSPEC Accession Number: 19671660
Subjects:	Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Divisions:	School of Computing
Depositing User:	Mrs. Norazmilah Yaakub
Date Deposited:	23 Jul 2020 01:46
Last Modified:	23 Jul 2020 01:46
URI:	https://repo.uum.edu.my/id/eprint/27227

Actions (login required)

View Item