Pengembangan Sistem Penjadualan Kuliah Menggunakan Metode Backtracking dalam Constraint Satisfaction Problem

Abstract

Arranging class schedule has its own problems in a college such as classroom limitation, instructors' time to teaching, the change in curriculum, and the use of laboratory. They are still topical in the research for scientific work. The objective of the research was to find out how to arrange schedules in such a way that they could be optimal and fast in arranging the schedules in order to cope with being collided to one another. The components of scheduling consist of students, subjects, instructors, classrooms, and instructors ' time to teach with a number of constraints. This case study was conducted at the Faculty of Engineering, University of Sumatera Utara. The research compared the outcome of scheduling school subjects with backtracking method with the solution for constraint satisfaction problem. From the result of comparing random test of the schedule by using minimum remaining value (MRV) and forward checking (FC) backtracking method, and dynamic backtracking method, it was found that the two methods could meet the need for instructors ' time to teach with the minimum number of classrooms and with the presentation of instructors ' different teaching time. The minimum number of classrooms to be used in MRV and FC methods was eight classrooms with 54 percent of the need for instructors to teach. The number was more than what had been achieved through scheduling with dynamic backtracking method which had the minimum of six classrooms with 16% less than the need for instructors.