Exam Seating Arrangement System

Exam Seating Arrangement System

Academic institutions are moving toward automatedmanagement of the educational process. One aspect of thisprocess is the exam scheduling. The large number of students,classes, professors, and venues renders the manual schedulingprocess tedious and useless. In this paper, we describe the effortsof the Arab East College for High Education in Saudi Arabiain scheduling exams in the least number of conflicts, amongother constraints. We give the details for a two-stage solutionapproach; the first stage is a greedy algorithm and the secondone is a genetic algorithm. The two algorithms work in tandemto generate the best exam timetable. Automation of this processhas greatly reduced the number of conflicts, exam days, and therequired venues.

Problem Complexity:Now, given this initial set of con-straints, the technique complexity can be established; Theexam scheduling problem is an NP-hard problem. The otherparameters, like the class enrollment, can be further added totake into account the capacity of the exam venue. This willmake the problem even harder to solve.

 The following discussion demonstrates that the problem isNP-hard:•Consider the problem of schedulingMexams with threeavailable time slots.•Two exams are in conflict if they cannot be offered at thesame time.•Construct a graphG, such that the nodes represent exams.•If two exam nodes are conflicting then they are connectedwith an edge.•To schedule the exams with no conflicts, the nodesincident to the same edge cannot be scheduled duringthe same time slot.•Let the three available time slots represent colors, thennodes incident to the same edge can not have the samecolor.•The problem reduces to the 3-colorability graph, whichis a known NP-hard problem [20]

 We have chosen to compare our work with the workproposed by Jha in [21], since it is the closest to our workin terms of the problem size and assumptions.Jha used three constraints: each course is scheduled inexactly one period, no student is assigned two exams in thesame period, and no room is allocated to more than one course in one period. It is also assumed that any room is large enoughto accommodate the students of any course. https://codeshoppy.com/ He applied hispure genetic algorithm on a hypothetical scenario comprisingthirty six courses and twelve rooms. The solution resulted inthe need for twenty periods.In our work, we handle more constraints as mentionedearlier. 

We have also started with a valid solution using theGreedy Algorithm and proceeded to use the Genetic Algorithmto tune the solution such that the hard constraints are met andthe soft ones are maximally satisfied. On the other hand, wehave tested our algorithm on a real case with ninety sevencourses and twenty four rooms. The solution resulted in theneed for twenty four periods.

Even though the exam scheduling problem is a well-studiedproblem, practical solutions are still in need to be developed.In this paper, we have showcased the experience of the ArabEast College for High Education, KSA, in scheduling exams.The greedy and genetic algorithm that we presented offerreasonable arrangements for the students and the faculty.Yet, more constraints may also be required to increase thequality of the produced schedule. For example, minimizingthe number of exam days, maximizing the separation betweenexams for the same student to allow for sufficient preparationtime, prioritizing certain exams, proctors availability, or anyother arrangement that may be required. Moreover, makingthese solutions available as free or commercial tools is of greatbenefit

Know More