Paper Title :Generating Class Scheduling without Conflict based on Maximum Independent Set

Author :Ahmad A. Sharieh, Mohammad A. Asmaran, Basel A. Mahafzah

Article Citation :Ahmad A. Sharieh ,Mohammad A. Asmaran ,Basel A. Mahafzah , (2020 ) " Generating Class Scheduling without Conflict based on Maximum Independent Set " , International Journal of Advances in Science, Engineering and Technology(IJASEAT) , pp. 77-83, Volume-8,Issue-4

Abstract : 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.

Type : Research paper

Published : Volume-8,Issue-4

	|		PDF	|	Viewed - 60	|	Published on 2021-03-15