ABSTRAK
Penjadwalan ujian merupakan salah satu proses dalam kegiatan belajar mengajar dimana dalam proses penjadwalan terdapat beberapa permasalahan yang harus diselesaikan agar dapat terjadwal dengan baik dan sesuai dengan aturan. Terdapat beberapa metode yang dapat digunakan untuk menyelesaikan masalah penjadwalan ujian. Diantara metode tersebut sebagian besar digunakan untuk menyelesaikan masalah penjadwalan ujian untuk perkuliahan dan jarang yang digunakan untuk menyelesaikan penjadwalan ujian untuk sekolah menengah atas. Oleh karena itu dalam penelitian ini penulis akan melakukan pendekatan baru dalam penjadwalan ujian berdasarkan aturan pelaksanaan ujian yang sudah ada, baik hard constraint maupun soft constraint. Pendekatan baru ini terdiri dari tiga algoritma dengan kompleksitas masing-masing, yaitu: algoritma alokasi mata pelajaran dengan kompleksitas linear, algoritma alokasi pengawas dengan kompleksitas linear, dan algoritma alokasi tempat duduk siswa dengan kompleksitas polinomial. Berdasarkan penelitian yang telah dilakukan dapat disimpulkan bahwa pendekatan baru ini menghasilkan sebuah penjadwalan ujian dengan tidak melanggar hard constraint namun masih melanggar soft constraint. Kata Kunci: Penjadwalan ujian, Hard Constraint, Soft Constraint, Kompleksitas Algoritma  
ABSTRACT
Exam scheduling is one of process in learning activities. In this process, there are several problems usually while we arrange the schedule. We must solve the problems, in order to create a good schedule based on rules that already exist. Several methods can be used to solve this problem, but mostly of this methods are used in universities exam scheduling not in high school. To solve the problems in exam scheduling in high school, author propose a new approach based on existing exam rules, either hard constraint or soft constraint. The new approach consist of three algorithm with different complexity, which are subjects allocation algorithm with linear complexity, invigilator allocation algorithm with linear complexity, and seat allocation algorithm with polynomial complexity. Result of this research are an exam schedule that does not violate the hard constraint, but still violate the soft constraint. Key Words: Exam scheduling, Hard Constraint, Soft Constraint, Complexity of Algorithm