Generating Class Scheduling without Conflict based on Maximum Independent Set
Finding a timetable of undergraduate student that considers the maximum number of offered courses during his/her graduation semester without any conflict is necessary. Maximum Independent Set (MIS) in a graph is a well-known problem in the field of computer science and it can be used to implement class timetable without conflict. The offered classes in a semester can be represented as a graph that reflects institution regular and special rules. The MIS can be found by using a brute force algorithm for graph with small size, whereas approximation algorithms can be used to find the MIS in a graph of large size. In this paper, a representation of class timetable in a graph and two algorithms to find the MIS for classes are explained and implemented. The first algorithm is a brute force based on modified Wilf algorithm and the second is a meta-heuristic based on chemical reaction optimization. Both algorithms are implemented to find an undergraduate student maximum available timetable of offered courses in a semester. The implementation can be integrated in an institution management information system. It is found to be efficient in solving the problem of classes’ timetable without conflict.
Keywords - Chemical Reaction Optimization, Class Timetable, Graph, Maximum Independent Set, Modified Wilf Algorithm.