Genetic Algorithm for Solving 3 Dimensional Time Table Problem Based on Traveling Salesman Problem (TSP) Method

Dwi Fatul Oktafiani*  -  Universitas Islam Walisongo Semarang, Indonesia
Muhammad Ardhi Khalif  -  Universitas Islam Walisongo Semarang, Indonesia

(*) Corresponding Author
Scheduling problems are problems that are often faced by educational institutions, especially at the university level. This is because there are several obstacles in the preparation of the schedule, namely first, there should be no duplication of space, day, and hour. Second, there should be no duplication of lecturers on the same day and time, even though in different rooms and in different subjects. Third, there should be no duplication of group classes (study groups). Therefore, the purpose of this study is to obtain a genetic algorithm as a solution in overcoming the three constraints of preparing the schedule by using the Traveling Salesman Problem (TSP) method in the crossover process. To make it easier to organize the schedule, a 3-dimensional matrix is used with the x-axis representing (space, day, hour), the y-axis representing (courses, lecturers, credits) and the z-axis representing (classes). This study simulates the scheduling of 20 courses, 50 credits, 8 lecturers, and 19 classes. Chromosomes in this study are permutations of integers 1-20. Each gene in a chromosome represents a course package. From the scheduling results, the fitness function is 0.96 for 48 schedule slots (2 rooms x 3 days x 8 hours). For schedule slots greater than 50 (3 rooms x 3 days x 8 hours, 2 rooms x 4 days x 8 hours, and 2 rooms x 3 days x 9 hours), this algorithm is successful in getting fitness function 1. ©2018 JNSMR UIN Walisongo. All rights reserved.

Keywords: Genetic Algorithm; 3D Time Table Problem; Traveling Salesman Problem; Fitness Function

  1. Rusdiana.2004.Judul Skripsi :Optimalisasi Penjadwalan Mata Kuliah menggunakan Metode Algoritma Genetika. Jakarta : Jurusan Teknik Informatika Fakultas Sains dan Teknologi Universitas Syarif Hidayatullah.
  2. A. Jain, D.S. Jain, dan D.P. Chande, "Formulation of Genetic Algorithm to Generate Good Quality Course Timetable". International Journal of Innovation, Management and Technology 1, (2010) 248-251.
  3. Fitri, R. (2004). Penjadwalan Perkuliahan Dengan Pengujian Tabel Waktu (Time-Table) Menggunakan Algoritma Genetika. 2004: Universitas Komputer Indonesia.
  4. Jenna Carr. 2014. An Introduction to Genetic Algorithms.
  5. Haupt, R. L., & Haupt, S. E. (2004). Practical Genetic Algorithms (2nd ed.). Hobo-ken: Wiley.
  6. Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Reading: Addison-Wesley.
  7. Zheng, Yingsong., Kiyooka, Sumio.(1999),"Genetic Algorithm Applications", Asia-Pacific Journal of Operational Research, 7 172-189.
  8. Saifullah, Shoffan., Arief Hermawan.2016. Pengembangan Sistem Penjadwalan Kuliah Menggunakan Algoritma Steepest Ascent Hill Climbing
  9. Simon, D. (2013). Evolutionary Optimization Algorithms: Biologically-Inspired and Population-Based Approaches to Computer Intelligence. Hoboken: Wiley.
  10. Fachrudin, A. (2010). Penerapan Algoritma Genetika Untuk Masalah Penjadwalan Job Shop Pada Lingkungan Industri Pakaian. Surabaya: Institut Teknologi Sepuluh Nopember.

Open Access Copyright (c) 2018 Journal of Natural Sciences and Mathematics Research
Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Journal of Natural Sciences and Mathematics Research
Published by Faculty of Science and Technology
Universitas Islam Negeri Walisongo Semarang

Jl Prof. Dr. Hamka Kampus III Ngaliyan Semarang 50185
Website: https://journal.walisongo.ac.id/index.php/JNSMR
Email:jnsmr@walisongo.ac.id

ISSN: 2614-6487 (Print)
ISSN: 2460-4453 (Online)

View My Stats

Lisensi Creative Commons

This work is licensed under a Creative Commons Lisensi Creative Commons .

apps