Meta Heuristic Algorithm: An Optimal Solution for Examination Resources Scheduling

Meta Heuristic Algorithm: An Optimal Solution for Examination Resources Scheduling

Ramoni Tirimisiyu Amosa^*, Adekiigbe Adebanjo, Fabiyi Aderanti Alifat, Olorunlomerue Adam Biodun, Babafemi Olusola Florence, Olatunji Fatai Abiodun, Adejola Aanu Adeyinka.

Department of Computer Science, School of Applied Sciences, Federal Polytechnic Ede, Osun State, Nigeria.

*Corresponding Author

DOI: https://doi.org/10.51584/IJRIAS.2024.909018

Received: 24 August 2024; Revised: 02 September 2024; Accepted: 07 September 2024; Published: 03 October 2024

ABSTRACT

Information Technology had turn to a very significant tool in order to ease our daily activities and higher education has become much more complex due to the rise in student enrolment and the implementation of modularity in many institutions. This has put additional strain on administrators to find solutions, frequently without the use of computers. A successful distribution of examination venue, seats, and effective allocation of invigilators and attendants is one of the primary concerns of examination committee in any institution of learning.  The main problems faced by the educational institution include allocating the proper examination venue for a class, having some seats empty and in some cases the number of students greater than the available capacity of the venue and finally students may decide to go to venue he/she wishes which eventually causes some venue overcrowded while some are underutilized. The examination resource schedulling was developed using Php, Mysql while WAMP was used for the implementation of the system and an optimisation technique called meta heuristic algorithm is employed to locate the optimal answer inside a specified search space, it focus on making incremental changes to improve a current solution until they reach a locally optimal or satisfactory solution. The evaluation of the system was carried using Mean Opinion Scores (MOS) among the players (users), the internal and external rating of the software by the students are 99.20% and 98.67% while rating by the staff are 98.50% and 98.13%. Finally, the study concludes that the system can easily be adopted by any higher school of learning with little or no amendments.

Keywords: Attendant, Examination, Information Technology, Institution, Invigilator.

INTRODUCTION

All spheres of human activity and every profession have been impacted by the ICT revolution. Retooling, retraining, and curriculum revision are ways that professions including law, medicine, engineering, library and information science, and others are adapting to the ICT environment (Nilima et al., 2017).   Every academic institution faces the problem of allocating the appropriate and necessary resources for required courses during the semester examination. Examination resources is described all the needed ingredient and required assets for a standard and acceptable examination conduct which includes examination venue, invigilators, attendants and laboratory (Gupta et al., 2022). Exam scheduling is a tedious, time-consuming process that calls for extensive preparation. In addition, exam seating arrangements must be planned, and invigilation (supervision) responsibilities must be established (Farida et al., 2015). Using neighbouring solutions as a guide, a local search algorithm iteratively refines a potential solution to solve computing problems. In order to get closer to an ideal or suitable solution, these algorithms concentrate on making tiny, local adjustments to the existing solution rather than exploring the whole solution space. (Wang and Zuo, 2021).

The goal of the examinations resources scheduling system is to decrease the amount of time and human labour that the school committee must devote to creating the final exam schedule, seat assignments, and student attendance records (Mohmad and Mohd, 2013). This is made possible with the creation of a database that collects information pertaining students’ data and courses registration and also invigilators/institution lecturers data. This system is beneficial especially to the school examination committee of higher learning because it enables them to produce comprehensive examinations invigilation schedule, sitting arrangement and create a convenient and conducive environment for students while writing the examination. This paper is directed at facilitating the effective and easy processing of examination-invigilation schedule, which is the allocation of time, date/days, venue and invigilation for each course at all levels, with regard to the size of each venue and the population of students offering each course.

Exam scheduling, as described by Gao et al. (2020), is the process of allocating exams to time slots within a predefined period of time while also assigning rooms and invigilators to each exam in order to satisfy a variety of constraints. This includes avoiding double bookings for rooms, teachers and students, room capacity and type constraints, exam sequence and spreading constraints, pre-assignments and availability of resources. The examination scheduling facility can be used to generate a clash free assessment timetable for each student, based on a series of criteria about what is and is not allowable for a student to do. The key to the process is the concept of the assessment slot, into which assessments are scheduled. The assessment will, as part of the process, be scheduled into one or more appropriate rooms Ismael et al., 2021)

Overview of Optimal Solution for Examination Resources Scheduling

The examination scheduling system in many institutions is purely manual; the school examination committee compare the capacity of the classes with the venue and allocate the students to the venue for the purpose of writing the examination and also invigilators and attendant are allocated arbitrarily. More than one course can be written in a venue and the sitting arrangement is done by the invigilators, this approach is characterized by a problem which includes:

1. Semester Examination Scheduling requires a lot of time and human effort.
2. Allocating examination venue arbitrarily causes a lot of inconsistencies as some venues are over utilized while some are underutilized and thereby in some cases create unconducive environment for students during the examination.
3. Some invigilators are given higher number of supervision time while some are allocated little slot of invigilation

Optimal Solution for Examination Resources Scheduling and manage all the Needs (resources)  for effective and reliable allocating exam venue, attendants and invigilators and removes the human effort required to ensure smooth running of a complex situation and therefore drastically reduces administrative workload (El-Zoghdy et al., 2013). This will ensures the best use of space and resources, reducing the number of venue and staff required for the conduct of semester examination.

RESEARCH METHODOLOGY

The Information and Communication Technology (ICT) Centre/Management Information System (MIS), being the custodian of students records, can be relied upon for the access to the students records through the institution database/server. the students’ database consist of three different tables;

1. Students bio-data table
2. Course Pool table
3. Course registration table

Database has to be maintained by the system to store information about students, invigilators, classrooms, course code, examination date and time. The various updates must be saved and stored in the database of the system. Therefore MySQL, relational database adopted for the design of the system. PHP was used to design the back end of the system.

1. A set of exams E={e₁,e₂,…,e_n} where each exam ei​ has a corresponding course code.
2. A set of time slots T={t₁,t₂,…,t_m}
3. A set of venues V={v₁,v₂,…,v_k} with specific capacities.
4. A set of invigilators I={i₁,i₂,…,i_p}.

The major objectives of metaheuristic algorithm is to minimize conflicts which includes:

1. Assigning more than one exam to the same venue at the same time.
2. Scheduling an invigilator to supervise more than one exam at the same time.
3. Exceeding venue capacity.
4. Assigning students with multiple exams at the same time.

Architectural Overview of the System

1. Administrator phase: This is only accessed by the system administrator, administrator is someone that oversee the overall function of the system to ensure the effectiveness, integrity, and reliable output.
2. Students side: This side of the application is accessed by the students, the students log-in to the system with their matriculation number, this will give students opportunity to preview their examination venue irrespective of time and location.

Metaheuristic Algorithm

A metaheuristic is an algorithm or heuristic that operates at a higher level and is designed to assist other heuristics in more effectively solving optimisation problems. These algorithms are widely used when it is not practical to utilise typical optimisation techniques (e.g., exact algorithms) due to the problem’s complexity, scale, or non-linearity. Metaheuristics aim to find a good or nearly optimal response in a reasonable amount of time, but they do not guarantee that the best solution will be found.

Features of metaheuristic search include:

Problem Independence: Metaheuristics can be used to solve a variety of optimisation problems and are typically not affected by specific difficulties.

Exploration vs. Exploitation: They strike a balance between enlarging the search around viable answers (exploitation) and expanding the search space (exploration).

Stochastic Nature: To break out of local optima and discover new regions of the search space, a lot of metaheuristics use randomness.

Iterative Process: Most of these algorithms are iterative, getting better at solving problems with each iteration.

Data Flow Diagram (DFD)

The transfer of data between an entity, a process, and a data store is known as data flow. The interface between the DFD’s component parts is depicted via data flow. In a DFD, the names given to the data flow correspond to the type of data that is used (these names should also be unique inside a certain DFD). During the preliminary stages of study, DFDs assist system designers and other stakeholders in visualising an existing system or one that could be required to fulfil new requirements. Working with DFDs is preferred by systems analyses, especially when they need to clearly define the boundary between the assumed and existing systems.

DFDs represent the following:

1. External devices sending and receiving data
2. Processes that change that data
3. Data flows themselves
4. Data storage locations

System Algorithm

Analyse the algorithm below using meta heuristic method:

<?php

require_once ‘../core/db.php’;

if(!admin())

{

    header(“location:login.php”);

    exit();}

if(isset($_POST[‘ok’])){

    // var_dump($_POST);

    // exit;

    $session = settings(“session”);

    $semester = settings(“semester”);

    $courses = $_POST[‘course’];

    //GET TOTAL STUDENTS

    $total_students = 0;

    foreach ($courses as $course) {

        //get caps

        $sql_caps = $db->query(“SELECT NULL FROM course_reg WHERE allocated = ‘0’ AND course = ‘$course'”);

        $total_students += $sql_caps->rowCount();

    }

    //var_dump($total_students);

    //Get capacity of available hall

    $halls = $db->query(“SELECT SUM(capacity) as total_halls FROM centers WHERE status = ‘1’”);

    $halls_rs = $halls->fetch(PDO::FETCH_ASSOC);

    $halls->closeCursor();

    $total_halls = $halls_rs[‘total_halls’];

    if($total_halls < $total_students){

        set_flash(“Error, available hall capacity is lesser than students capacity!”,”danger”);

        header(“location:generate.php”);

        exit();    }

Data Flow Diagram

The data flow inside the system is depicted in Figure 1, which also shows the data storage and external entities involved, as well as how data is transformed and moved through the system.

Figure 1: System Data Flow Diagram

System Interfaces

The interfaces in the system are grouped into two (i) Administrator interface (ii) Students interface.

Students’ Interface

Figure 2 below shows the interface with various link at which the students can navigate within the application. The dashboard contains the following links

Course Registration: This allows the students to enter their personal data including the details of semester courses into the system and save it into the system database.

Check Venue: The links allows the students to check the venue and time at which the student will write a particular examination.

Account Setting: Here the student can edit his/her biodata

Logout: Student can exit the application

Figure 2: Students Interface

System Administrator

The dashboard here gives the administrator opportunity to carry out a wide range of operation with the available links.

Generate Examination Schedule: The administrator allocate examination venue to students as well as invigilator and attendant.

Send SMS: This interface allows the administrator to send to students and invigilator alerting them of their venue and time.

Print Schedule: System administrator print the examination schedule generated by the system sample schedule is shown in Figure 4.

View Schedule: Administrator print the students attendance generated by the system, sample students’ attendance is shown in figure 5.

Figure 3: Administrator Interface

SYSTEM RESULTS/OUTPUT

The system generated many results and outputs after the implementation

Invigilation Schedule: Invigilation schedule shows the details of the examination invigilation, it shows the time and session at which a course is to be written, the venue of the examination, number of the students in the venue, name of the invigilator, sample invigilation schedule is shown in Figure 4.

Students Attendance: This shows the list of students that writes examination is a particular venue, it display the course title, course code, students matriculation number and name. It also shows the name of invigilator that invigilates the examination. This eliminates the situation whereby students write examination in their preferred venue which sometimes causes examination malpractices.

Table 1: Examination Invigilation Schedule

 Figure 4: Students Attendance

System Evaluation

As we covered in the methodology section, the goal of the research project is to design a system, not to examine or contrast existing systems. Consequently, the system’s outcome is tested using the mean opinion score. The program testing follows two distinct stages:

1. External Quality Testing: This involved the testing that is clearly visible to end users or the player such as; Clarity, User friendly, Usability, Economy, Timeliness, and Validity (McCall et al., 1977).
2. Internal Quality Testing: This includes testing the software’s internal technical problems, which include maintainability, efficiency, correctness, modularity, and documentation. It is an essential step in the software development process that focusses on assessing a software product’s internal components to make sure it satisfies quality requirements (Fowler, 2018).

The mean opinion score (MOS) was recorded after several attempts by the player (i.e Invigilators, Supervisors, Attendants and Students) other researchers in the field. The software was put into use during 2023/2023 Second Semester Examination for Faculty of Science at Premier College of Education (PCE), Ede Osun State, Nigeria. Following multiple player efforts, players who were specifically chosen to engage with the system were given questionnaires to complete. They were asked to rate the system according to the previously indicated software quality rating. According to the results, the system did better than average (Very Good) (rating range: 1-bad to 5-excellent).

Evaluation Results

The chosen participants were involved in the activity for a while, and hundred (100) students and thirty (30) staff members from different departments (academics and non-academics) completed a questionnaire to grade the system according to the previously given criterion. First, the External and Internal Quality Testing ratings of the Examination Resources Scheduling System are displayed in tables 2, 3, 4, 5 and figures 6, 7, 8, and 9, respectively. The cumulative weighted % against the rating parameters is shown in these tables.

Table 2.0: Students rating based on External Software Quality

Table 3.0: External Software Quality Rating for Player (Staffs) Faculty of Science PCE.

Table 4.0: Internal Software Quality Rating for Player (Students) Faculty of Science PCE.

Table 5.0: Internal Software Quality Rating for Player (Staffs) Faculty of Science PCE.

Figure 5.0: External Software Quality Rating from Students

Figure 6.0: External Software Quality Rating from Staff

Figure 7.0: Internal Software Quality Rating from Students

Figure 8.0: Internal Software Quality Rating from Staff

CONCLUSION

Examination Resources scheduling System has been developed and tested. The application is quite flexible, reliable and easy to operate. It is an inexpensive application which is developed using Php, Mysql, WAMP and other components. It is an educational application which can be used by institution anytime and anywhere and also can be used to prepare proper distribution of examination venue, seat and effective allocation of invigilator, supervisor attendances during exanimation. Evaluation results of the research show that the developed system perform better in both system performance and system quality rating vis-à-vis its response time proves to be beyond average as expected. This result shows that users (Invigilators, supervisor and Students) found the system very interactive and useful. Therefore, from the results obtained, it can be concluded that the aim of this research work has been practically and theoretically achieved.

REFERENCES

1. Astaiza, L. G. (2005). A practical approach to scheduling examinations In geniería eInvestigación, 25(3), 92-100.
2. El-Zoghdy . S. F., Noval M., Shoka M. A and El-sawy (2013): An Efficient Algorithm for Resource Allocation in Parallel and Distributed Computing Systems. International Journal of Advanced Computer Science and Applications,  Vol. 4, No. 2, 2013
3. Farida Hanum, Mira A. Romliyah, Toni Bakhtiar (2015): Exam Invigilators Assignment Problem: A Goal Programming Approach. Applied Mathematical Sciences, Vol. 9, 2015, no. 58, 2871 – 2880. HIKARI Ltd, m-hikari.com. http://dx.doi.org/10.12988/ams.2015.52134.
4. Fowler, M. (2018). Refactoring: improving the design of existing code. Addison-Wesley Professional.
5. Gao, D., Wang, G. G., & Pedrycz, W. (2020). Solving fuzzy job-shop scheduling problem using DE algorithm improved by a selection mechanism. IEEE Transactions on Fuzzy Systems, 28(12), 3265-3275.
6. Gupta, S., Iyer, S., Agarwal, G., Manoharan, P., Algarni, A. D., Aldehim, G., & Raahemifar, K. (2022). Efficient prioritization and processor selection schemes for heft algorithm: A makespan optimizer for task scheduling in cloud environment. Electronics, 11(16), 2557.
7. Ismael, G. A., Salih, A. A., AL-Zebari, A., Omar, N., Merceedi, K. J., Ahmed, A. J., … & Yasin, H. M. (2021). Scheduling Algorithms Implementation for Real Time Operating Systems: A Review. Asian Journal of Research in Computer Science, 11(4), 35-51.
8. Mohmad Kahar, Mohd Nizam (2013): Heuristic approaches for real world examination timetabling problems. PhD thesis, University of Nottingham. Access from the University of Nottingham repository: http://eprints.nottingham.ac.uk/27677/1/598041.pdf.
9. Mccall, J.A., Richards, P.K. and Walters, G.F. (1977) Factors in Software Quality, Vol. I-III, Rome Air Development Centre, Italy.
10. Nansheng, P., & Qichen, M. (2023). Resource allocation in robust scheduling. Journal of the Operational Research Society, 74(1), 125-142.
11. Nilima N., Akshata J., Gunjan P. and Prachi P. (2017): Algorithm for efficient seat allocation process in college exam system. International Research Journal of Engineering and Technology (IRJET) e-ISSN: 2395 -0056.
12. Vasupongayya S., Noodam W., and Kongyong P. (2013): “Developing Examination Management System: Senior Capstone Project, a Case Study,” World Academy of Science, Engering and Technology, Vol:7 2013.
13. Wang, Y., & Zuo, X. (2021). An effective cloud workflow scheduling approach combining PSO and idle time slot-aware rules. IEEE/CAA journal of automatica sinica, 8(5), 1079-1094.