Course Scheduling Using Dynamic-Order Backjumping (Case Study: STIKA Madiun)

Abstract

Scheduling is one of constraint satisfaction problem (CSP). CSP could be solved by Backtracking (BT) algorithm. BT algorithm usually searches for already known wrong node or thrashing. To reduce thrashing on BT, we can use Backjumping (BJ) algorithm. In BT and ordinary BJ, they form a search tree that has fixed sequential variables. This order of variables has an effect on how much node created. Bad order could increase thrashing. Dynamic-order Backjumping (DOBJ) algorithm uses dynamic sequence variables to reduce thrashing. In the implementation, this research used data from the Science College of Train (STIKA) Madiun during 2015/2016 academic year on second semester. Data used in this research, including majors, lecturers, courses, and hour choice. The limits in this research only used hard constraint. From one of a result test, DOBJ has shorten runtime by making 29 times BJ became 5 times order change and 28 times BT. Because of the changes in varying order, it could change BJ step to BT step, so the execution time would be faster.