Publish In |
International Journal of Advances in Science, Engineering and Technology(IJASEAT)-IJASEAT |
Journal Home Volume Issue |
||||||||
Issue |
Volume-8,Issue-4 ( Oct, 2020 ) | |||||||||
Paper Title |
Generating Class Scheduling without Conflict based on Maximum Independent Set | |||||||||
Author Name |
Ahmad A. Sharieh, Mohammad A. Asmaran, Basel A. Mahafzah | |||||||||
Affilition |
The University of Jordan, Al-Balqa Applied University, The University of Jordan | |||||||||
Pages |
77-83 | |||||||||
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. | |||||||||
View Paper |