Resource Optimization in Examination timetabling using Graph Coloring

Abstract

The examination timetabling problem is a classical, old and famous problem in the field of optimization problems. Examination timetabling is an NP-Complete problem. Time table as a schedule requires to do work accurately and efficiently in an organized manner without any conflicts. Here, a novice approach for resource optimization in examination timetabling using graph coloring, is shown which specifically shows how examination can be scheduled efficiently considering No Room Splitting not even a soft constraint. This approach specifically describes two methods. First, in which examinations are removed from the independent set of examinations we got after graph coloring if the total students in examinations are more than the available seats in the institution. The second method describes if possible, how the removed examinations from all independent sets will be adjusted into independent sets other than it removed from, to minimize the total time slots and hence to utilize resources in better way. In the work, few constraints and assumptions, closely related to the general examination timetabling are considered.