IMPLEMENTASI ALGORITMA TABU SEARCH PADA APLIKASI PENJADWALAN MATA PELAJARAN (STUDI KASUS: SMA NEGERI 4 KENDARI)

semanTIK, Vol.2, No.2, Jul-Des 2016, pp. 197-206 ISSN: 2502-8928 (Online)



197

IMPLEMENTASI ALGORITMA TABU SEARCH PADA APLIKASI PENJADWALAN MATA PELAJARAN (STUDI KASUS: SMA NEGERI 4 KENDARI) *1,2,3

Mayang Putri Khairunnisa1, Bambang Pramono2 , Rizal Adi Saputra3 Jurusan Teknik Informatika, Fakultas Teknik, Universitas Halu Oleo, Kendari e-mail : *[email protected], [email protected], 3 [email protected]

Abstrak Pembuatan jadwal kegiatan belajar mengajar merupakan pekerjaan rutin yang dilakukan oleh Kepala Bagian Kurikulum setiap menyambut tahun ajaran baru. Peran Kepala Bagian Kurikulum dalam pembuatan jadwal kegiatan belajar mengajar ini sangatlah penting dan tidak mudah karena jadwal yang akan diatur terdiri dari data yang sangat banyak. Untuk membantu pengolahan jadwal mata pelajaran di SMA Negeri 4 Kendari ini, diperlukan adanya suatu sistem informasi penjadwalan dengan menggunakan metode Tabu Search. Tabu Search adalah sebuah metode optimasi yang berbasis pada local search, dimana proses pencarian bergerak dari satu solusi ke solusi berikutnya dengan cara memilih solusi terbaik yang tidak tergolong solusi terlarang. Dengan memasukkan data-data yang diperlukan, seperti Data Kelas, Data Mata Pelajaran, Data Guru dan Data Waktu, sistem akan menghasilkan jadwal umum dan jadwal khusus dari proses penjadwalan menggunakan Tabu Search. Jadwal yang dihasilkan merupakan jadwal paling optimum yang telah memenuhi kriteria pemberhentian saat proses TabuSearch Kata kunci— Tabu Search, Sistem Informasi, Penjadwalan. Abstract Creating the courses scheduling activity is routine work that is performed by the Chief of Curriculum each new academic years. The role of the Chief of Curriculum in creating courses schedule is very important and not easy because of the course schedule that will be scheduled consisting of lot data. To assist the processing of courses schedule in Senior High School 4 Kendari, it needed a scheduling information system that using Tabu Search. Tabu Search is a local search–based optimizing method, in which the search process of moving from one solution to next solution by choosing the best solution that is not classified as the prohibited solution. By entering the required data, such as Class Data, Subject Data, Teacher Data and Time data, the system will generate a general schedule and particularly schedule from the process of using TabuSearch. The resulting schedule is the optimum schedule that has fulfilled the stopping criteria in the Tabu Search process. Keywords— Tabu Search, Information System, Scheduling. 1. PENDAHULUAN

P

erkembangan teknologi informasi yang semakin pesat dalam segala bidang mendorong manusia dari berbagai lembaga untuk memanfaatkannya. Teknologi informasi adalah suatu teknologi yang digunakan untuk mengolah data, seperti memproses, mendapatkan, menyusun,

menyimpan atau memanipulasi data dalam berbagai cara untuk menghasilkan informasi yang berkualitas. Wujud nyata dari teknologi itu sendiri adalah adanya penerapan sistem komputerisasi bahwa sistem tersebut diharapkan mampu menyelesaikan suatu pekerjaan secara efektif dan efisien yang digunakan untuk keperluan pribadi, bisnis, pendidikan, kesehatan atau

Received June 1st ,2012; Revised June 25th, 2012; Accepted July 10th, 2012

198

Implementasi Algoritma Tabu Search pada Aplikasi Penjadwalan

pemerintahan dalam mengambil keputusan dengan meminimalisir kesalahan-kesalahan yang terjadi. Pemanfaatan teknologi tentunya disesuaikan dengan kebutuhan dari desain sistem tersebut. Teknologi tidak lagi dipandang hanya sebagai pelengkap, tetapi sudah menjadi salah satu penentu atas terlaksananya sasaran dan strategi. Pengolahan data yang dikerjakan secara manual sudah tidak lagi diperlukan. Pada lembaga pendidikan khususnya lingkup akademik SMA (Sekolah Menengah Atas), penjadwalan mata pelajaran merupakan pekerjaan rutin yang dilakukan oleh bagian kurikulum setiap menyambut tahun ajaran baru. Peran bagian kurikulum dalam pembuatan jadwal kegiatan belajar mengajar sangatlah penting dan tidak mudah karena jadwal yang akan diatur ulang terdiri dari data yang sangat banyak. Berkaitan dengan pembuatan jadwal kegiatan belajar mengajar, saat ini SMA Negeri 4 Kendari dalam pembuatan jadwal mata pelajaran masih dikerjakan secara manual, yaitu menggunakan Microsoft Office Excel. Sistem penjadwalan yang diterapkan saat ini adalah berdasarkan hasil rapat guru. Selain itu, masih terdapat kesalahan-kesalahan yang terjadi, seperti adanya mata pelajaran dan guru yang akan mengajar di waktu yang sama tetapi di kelas yang berbeda. Untuk membantu pengolahan jadwal mata pelajaran di SMA Negeri 4 Kendari, diperlukan adanya suatu sistem informasi penjadwalan agar penjadwalan kegiatan belajar mengajar dapat terselesaikan dengan cepat dan akurat serta mengurangi tingkat kesalahan yang biasa terjadi. Sistem informasi penjadwalan ini menggunakan metode Tabu Search. Kelebihan dari algoritma ini adalah optimal dalam mencari jarak terdekat dan sudah mampu menghitung minimalisasi total time travel dengan kompleksitas yang banyak. Dengan menggunakan metode ini, komponenkomponen yang terdiri atas guru, mata pelajaran, kelas, dan waktu dengan sejumlah batasan dan syarat tertentu dapat disatukan [1]. Terdapat banyak literatur yang ditemukan untuk penelitian mengenai penjadwalan mata pelajaran menggunakan Algoritma Tabu Search. Salah satunya yaitu penelitian dengan judul “Tabu Search sebagai Local Search pada Algoritma Ant Colony untuk Penjadwalan Flowshop” oleh [2]

menjelaskan bahwa Ant Colony Optimization (ACO) adalah salah satu metode MetaHeuristic yang dikembangkan untuk mencari solusi bagi permasalahan optimasi seperti penjadwalan. Metode Local Search merupakan salah satu bagian dari ACO yang menentukan kualitas solusi yang dihasilkan. Dalam penelitian ini,Tabu Search diusulkan sebagai metode Local Search dalam Algoritma ACO untuk menyelesaikan masalah penjadwalan flowshop. Tujuan dari penjadwalan ini adalah untuk meminimalkan makespan. Hasil makespan dan computation time dari metode usulan dibandingkan dengan Algoritma ACO yang menggunakan job-index sebagai metode local search. Tabu search sebagai local search menghasilkan nilai makespan yang tidak berbeda secara signifikan dibandingkan dengan menggunakan metode job-index, kelebihannya terletak pada computation time yang lebih singkat. Penelitian lainnya yang berkaitan dengan penelitian ini, yaitu oleh [3] “Penerapan Algoritma Tabu Search Dalam Penjadwalan Job Shop”. Dalam penelitian ini, Tabu search diterapkan pada sebuah permasalahan penjadwalan Job Shop dengan tujuan untuk meminimalkan waktu proses total atau makespan (Cmax). Penjadwalan menggunakan Algoritma Tabu Search ini dilakukan terhadap tiga kasus, yaitu paket pesanan bulan September, Oktober dan November, dimana untuk setiap paket pesanan dilakukan variasi terhadap initial solution dan panjang tabu list. Hasil penjadwalan ini kemudian dibandingkan dengan hasil penjadwalan lain yang menggunakan empat macam metode basic dispatching rules, yaitu Shortest Processing Time (SPT), Earliest Due Date (EDD), Most Work Remaining (MWKR) dan First Come First Served (FCFS). Hasil pengolahan data menunjukkan bahwa penjadwalan yang menggunakan Algoritma Tabu Search sensitif terhadap perubahan yang diberikan pada variabel yang ada didalamnya dan makespan yang dihasilkan secara keseluruhan lebih kecil apabila dibandingkan dengan hasil penjadwalan menggunakan keempat metode lainnya. Penelitian selanjutnya dari [4] yang berjudul “Using Tabu Search to Solve the Job Shop Scheduling Problem with Sequence Dependent Setup Times”membahas tentang pengimplementasian Algoritma Tabu Search

IJCCS Vol. x, No. x, July 201x : first_page – end_page

Khairunnisa, Pramono dan Saputra

 199

1978-1520

untuk masalah penjadwalan Job Shop dan ekstensi penanganan kelas yang lebih luas dari masalah secara efisien, khususnya kasus Job Shop dimodelkan tergantung dengan urutan sistem waktu. Penelitian ini telah menunjukkan bahwa memungkinkan untuk mengambil Algoritma Tabu Search yang ada dan menyesuaikan mereka untuk memberikan solusi yang masuk akal dari sebuah masalah untuk kelas yang lebih besar. Seperti yang terlihat dari data, solusi awal yang diberikan oleh algoritma daftar penjadwalan dua arah secara substansial lebih buruk untuk kasus dengan urutan ketergantungan sistem waktu daripada contoh-contoh tanpa mereka. Hal ini mungkin karena algoritma daftar penjadwalan dua arah tidak melakukan apa-apa untuk mencegah sistem waktu yang melebar pada busur mesin yang menghubungkan bagian kiri dan kanan. Meski begitu, jadwal daftar dua arah biasanya ditemukan pada solusi awal yang lebih baik yang ditemukan oleh jadwal daftar searah yang diuji. 2. METODE PENELITIAN Tabu Search berasal dari Tongan, suatu bahasa Polinesia yang digunakan oleh suku Aborigin Pulau Tonga untuk mengindikasikan suatu hal yang tidak boleh “disentuh” karena sakralnya. Menurut kasus Webster, Taboo berarti larangan yang dipaksakan oleh kebudayaan social sebagai suatu tindakan pencegahan atau sesuatu yang dilarang karena berbahaya. Bahaya yang harus dihindari dalam Tabu Search adalah penjadwalan yang tidak layak dan terjebak tanpa ada jalan keluar. Dalam konteks lebih luas, larangan perlindungan dapat diganti jika terjadi tuntutan yang mendadak. Tabu Search adalah sebuah metode optimasi yang berbasis pada Local Search, dimana proses pencarian bergerak dari satu solusi ke solusi berikutnya dengan cara memilih solusi terbaik neighbourhood solusi sekarang (current) yang tidak tergolong solusi terlarang (tabu). Ide dasar dari algoritma Tabu Search adalah mencegah proses pencarian dari local search agar tidak melakukan pencarian ulang pada ruang solusi yang sudah pernah ditelusuri dengan memanfaatkan suatu struktur memori yang mencatat sebagian jejak proses pencarian yang telah dilakukan. Struktur memori

2.1 Analisa Kebutuhan Sistem a) Kebutuhan Data Masukan Pada penelitian penjadwalan mata pelajaran menggunakan metode Tabu Search menyediakan beberapa syarat yang berguna agar penjadwalan dapat optimal mengurangi kesalahan seperti perulangan, jadwal yang sama dan lain-lain. Adapun syaratnya adalah sebagai berikut. Syarat: 1. Satu jam pelajaran terdiri dari 45 menit 2. Hari Senin sampai Kamis dan Sabtu terdiri dari 8 jam pelajaran. Hari Jum’at terdiri dari 5 jam pelajaran dan 7 jam untuk nonmuslim. 3. Kelas Lintas Minat X berada pada jam ke dua sampai empat di Hari Senin dan jam pertama sampai tiga di Hari Kamis. Kelas Lintas Minat XI dimulai pada jam pertama selama dua jam di Hari Selasa dan jam empat sampai lima di Hari Jum’at. Kelas Lintas Minat XII berada pada jam ke satu sampai dua di Hari Rabu dan jam pertama sampai dua di Hari Sabtu. 4. Untuk mata pelajaran yang terdiri dari 4 jam pelajaran, dibagi 2 pertemuan dalam seminggu, masing-masing 2 jam pelajaran. 5. Mata Pelajaran Penjaskes harus dijadwalkan antara jam ke satu sampai enam jam pelajaran 6. Guru tidak boleh mengajar pada jam yang sama pada satu hari di kelas yang berbeda. Dalam penelitian penjadwalan mata pelajaran menggunakan Algoritma Tabu Search ini dibutuhkan data masukan dimana data masukan merupakan data master yang terdiri dari data guru, data mata pelajaran, data kelas dan data waktu. Tabel 1 menunjukkan Data Guru. Tabel 1 Data Guru No. 1

2

3

Nama Guru Drs. Tenggarudin, M.Pd St. Suraedah A.D., S.Ag., M.Pd Hj. Chairunnisa, S.Ag., M.Pd

No.

Nama Guru

50

Wasiti, S.Pd

51

Dra. Wa Noni

52

Dra. Suhartina

Title of manuscript is short and clear, implies research results (First Author)


200 4 5 6 7 8 9

Sitti Rahma, S.Pd.I Dra. Hj. Nurnela Sabar Suryanagara, S.Ag., M.Ag Diana R.S.P., S.P.AK Muhamad Jafar, S.Pd Drs. H. Abd. Halid

53

Dra. Wa Haima

54

Wahyuni, S.Pd

32

Jufrianto, S.Pd Agustini, S.Pd Drs. La Saye Drs. Edy Husain Hj. Sahria, S.Pd Hj. Hadijah, S.Pd Muh. Daril, S.Pd., S.H Darwis, S.Pd H. Mangalisu, S.Pd., M.Si Suradin Daaba, M.Pd Suhartini, S.Pd Mardati, S.Pd Hartono, S.Pd Wa Ode Rasni, S.Pd Dra. Hj. Siti Halna, M.Pd Hj. St. Aisyah, S.Pd Agus Waliman, S.Pd Kamudina, S.Pd

33

55 56 57 58

10

Drs. Haseng

59

11

Salida, S.Pd

60

12 13 14

15 16

Abdurohman , S.Pd Dra. Yanci Lanjaa Puspadewi Putri, S.Pd Hj. Wd. St. Sufiah, S.Pd., M.Pd Wa Ode Rusni, S.Pd

61 62 63

64 65

17

Karni, S.Pd

66

18

La Ode Samia, S.Pd

67

19

La Mui, S.Pd

68

20

Drs. L. Ameruddin

69

21

Drs. Zainudin

70

22

Drs. Sahama, M.Pd

23

24

25 26 27 28

H. Sami, S.Pd Mikyal Pelango, S.Pd., M.Hum Ferdinand N. B., S.Pd., M.Pd Sri Lestari, S.Pd., M.Si Baharudin, S.Pd., S.Kom Drs. H. Ahmad Daaba, M.Pd

71 72

73

Drs. M. Sinardin Rizal, M.Pd

74

Dra. Hj. Sitti Nuriati

75 76 77

29

Liyu, S.Pd., M.Pd

78

30

Drs. Sultan

79

31

34

35

36 37 38 39 40 41

Drs. Azhar

80

Arman Kari, S.Pd., M.Pd Hj. Andi Dessy, S.Pd., M.Pd Andi Yuliana R, S.Pd., M.Pd Taty Andriati, S.Pd Muh. Syahrani, S.Si Erna Sari Sujito, S.Pd

81 82

Muliati Tahir, S.E

83

Samlia, S.Pd

84

Nurdiana Arsyik. S.Pd

85

Wa Faria, S.Ag., M.A

86

Drs. La Babu

87

Sukadi Linta, S.Pd., M.Pd Dra. Nurmariah Darnisa, S.Pd., M.Pd

88 89 90

42

Dra. Naniatri

91

43

Rosli Pabesak, S.E

92

44

Drs. Arimapa

93

45 46 47 48 49

Drs. Muh. Haryansah Safiilu, S.Pd., M.Pd Sumaeni S.Pd., M.Pd Syamsul Bahri, S.Pd., M.Kes La Ode Salama, S.Pd

Nurjani Siah, S.Pd La Ogo, S.Pd

94 95 96 97

Anita Silva, S.Ag Munawarah, S.S Anas, S.Pd., M.Si Dra. Sri Bulan Dra. Ritha B. Allo Dra. Wa Ode Muliati R. Umi Hanikah, S.Pd Emiriyanti Basrin, S.Pd H. Syamsuddin Nurhasanah, S.S Syamsiar, S.Pd Asniar, S.Pd

Tabel 2 menunjukkan Data Pelajaran. Tabel 2 Data Mata Pelajaran

Amran, S.Pd., M.Pd Dra. Murni Lakoro Dra. Hj. Misbah Ahmad Agustina Pasang, S.Pd Dra. Ilmi, M.Pd


No.

Mata Pelajaran

Mata

No.

Mata Pelajaran

1

Agama Islam

17

Biologi (Praktikum & Kewirausahaan)

2

Agama Protestan

18

Fisika

3

Agama Katolik

19

Fisika (Praktikum & Kewirausahaan)

4

Agama Hindu

20

Kimia

5 6 7 8 9

10 11 12 13 14 15 16

PKN Bahasa Indonesia Bahasa dan Sastra Indonesia Bahasa Inggris Bahasa dan Sastra Inggris Matematika Matematika Peminatan Sejarah Indonesia Sejarah Seni Budaya Penjas Orkes Biologi

 201

1978-1520


21

Kimia (Praktikum & Kewirausahaan)

22

Geografi

23

Sosiologi

24

Antropologi

25

Ekonomi

26

Ekonomi (Praktikum & Kewirausahaan)

27

Bahasa Arab

28

TIK

29

TIK (Praktikum & Kewirausahaan)

30

BK

31

Bahasa Jepang

15 16

X Lintas Minat 1 X Lintas Minat 2

38

XII MIPA 4

39

XII MIPA 5

17

XI MIPA CIBI

40

XII MIPA 6

18

XI MIPA OLIMPIADE

41

XII IPS OLIMPIADE

19

XI MIPA 1

42

XII IPS 1

20

XI MIPA 2

43

XII IPS 2

21

XI MIPA 3

44

22

XI MIPA 4

45

23

XI MIPA 5

XII BAHASA XII Lintas Minat

Tabel 4 menunjukkan Data Waktu. Tabel 4 Data Waktu

Tabel 3 menunjukkan Data Kelas. Tabel 3 Data Kelas No.

Kelas

No.

1

X MIPA CIBI

24

XI MIPA 6

2

X MIPA OLIMPIADE

25

XI MIPA 7

3

X MIPA 1

26

XI MIPA 8

4

X MIPA 2

27

XI MIPA 9

5

X MIPA 3

28

XI IPS OLIMPIADE

6

X MIPA 4

29

XI IPS 1

7

X MIPA 5

30

XI IPS 2

8

X MIPA 6

31

XI BAHASA

9

X MIPA 7

32

10

X MIPA 8

33

11

X IPS OLIMPIADE

34

12

X IPS 1

35

XII MIPA 1

13

X IPS 2

36

XII MIPA 2

14

X BAHASA

37

XII MIPA 3

Hari

Senin Kamis dan Sabtu

Kelas

XI Lintas Minat XII MIPA CIBI XII MIPA OLIMPIADE

Jum'at

Jam 1. 07.00 – 07.45 2. 07.45 – 08.30 3. 08.30 – 09.15 ISTIRAHAT 09.15 09.40 4. 09.40 – 10.25 5. 10.25 – 11.10 6. 11.10 – 11.55 ISTIRAHAT 11.55 12.20 7. 12.20 – 13.05 8. 13.05 – 13.50 06.45 – 07.15 (IMTAQ) 1. 07.15 – 08.00 2. 08.00 – 08.45 3. 08.45 – 09.30 ISTIRAHAT 09.30 09.45 4. 09.45 –



202 10.30 5. 10.30 – 11.15

b) Kebutuhan Data Keluaran Keluaran sistem ini berupa jadwal umum dan jadwal khusus. Jadwal umum merupakan jadwal dari seluruh kelas yang berada di SMA Negeri 4 Kendari, sedangkan jadwal khusus hanya mencakup jadwal dari kelas tertentu yang ingin dicetak. 2.2

Gambaran Sistem Menjelaskan tentang aktivitas yang dilakukan oleh admin, yaitu login, mengelola data pengguna, mengelola data master, yaitu data kelas, pelajaran, guru, dan waktu, melakukan penjadwalan, dan mengakses menu tentang. Gambar 1 menunjukkan use case diagram untuk sistem informasi ini.

memilih sebuah solusi awal, di mana solusi ini diperoleh dari tahap inisialisasi. Kemudian membuat sebuah daftar kandidat perpindahan (solusi), jika daftar tersebut dipakai, maka setiap perpindahan akan menghasilkan sebuah solusi baru dari solusi saat ini. Selanjutnya, melakukan evaluasi setiap kandidat dan memilih kandidat terbaik. Kandidat solusi terbaik memberi nilai tujuan yang lebih baik dibanding kandidat lain. Kemudian periksa status tabu dari kandidat solusi tersebut. Jika kandidat bersifat tidak tabu maka kandidat tersebut dicalonkan sebagai kandidat yang diterima terbaik. Namun jika kandidat bersifat tabu maka akan diperiksa level aspirasi dari calon kandidat tabu, jika memenuhi kriteria aspirasi maka perpindahan (status tabu ke status tidak tabu) tersebut diterima atau dicalonkan sebagai kandidat diterima yang terbaik (status tidak tabu). Sebagai tambahan dari tabu list, dikenal adanya aspiration criteria (kriteria aspirasi) yaitu suatu penanganan khusus terhadap move (perpindahan) yang dinilai dapat menghasilkan solusi yang baik namun move tersebut berstatus tabu. Dalam hal ini, jika movetersebut memenuhi kriteria aspirasi yang telah ditetapkan sebelumnya, maka move tersebut dapat digunakan untuk membentuk solusi terbaik berikutnya (status tabu dibatalkan) Tahap selanjutnya, periksa daftar kandidat terbaik apakah masih terdapat sebuah “kemungkinan yang lebih baik” dari perpindahan yang tersisa (belum diperiksa). Jika tidak maka ambil perpindahan terbaik. Selanjutnya, jika kondisi pemberhentian terpenuhi, maka hentikan seluruh prosedur. Sebaliknya, jika masih ada maka akan dilanjutkan dengan membuat kembali daftar kandidat perpindahan dari perpindahan terbaik terakhir.

Gambar 1 Diagram Use case 2.3

Ilustrasi Algoritma Tabu Search Terhadap Perencanaan Aplikasi Flowchart Algoritma Tabu Search untuk sistem informasi yang akan dibangun ditunjukkan pada Gambar 2. Dimulai dengan IJCCS Vol. x, No. x, July 201x : first_page – end_page


1978-1520

 203

Gambar 3 Halaman Proses Jadwal

Gambar 2 Flowchart Diagram Tabu Search 3. HASIL DAN PEMBAHASAN Pada halaman proses Tabu Search, yaitu halaman inti dari pembuatan sistem informasi penjadwalan ini karena pada halaman tersebut melakukan proses penjadwalan mata pelajaran baru menggunakan algoritma Tabu Search yang dapat dilihat pada Gambar 3. Aksi yang dapat dilakukan, yaitu proses jadwal, download jadwal, cancel jadwal, dan load jadwal terbaru. Proses jadwal adalah proses pembentukan jadwal pelajaran baru menggunakan metode Tabu Search yang dapat dilihat pada Gambar 3. Load jadwal terbaru dilihat pada Gambar 4 menampilkan data kategori kelas yang telah memiliki jadwal mata pelajaran terbaru. Download jadwal, yaitu mengunduh jadwal pelajaran per kategori kelas yang dapat dilihat pada Gambar 5.

Gambar 4 Halaman Load Jadwal Terbaru

Gambar 5 Halaman Download Jadwal


204


3.1

Begitu seterusnya hingga indeks mencapai batas.

Hasil Penjadwalan Gambar 6 menunjukkan tampilan dari Hasil Penjadwalan Baru yang telah dibuat. Jadwal baru yang telah diunduh ini dapat dilihat pada Microsoft Excel.

Langkah 3 Memilih solusi terbaik di antara solusi alternatif yang telah didapat pada langkah. Solusi terbaik yang diperoleh dari iterasi pertama dipilih sebagai solusi optimum sementara. Langkah 4 Apabila nilai solusi terbaik pada langkah 2 lebih kecil dari nilai solusi optimal awal, maka solusi optimum terbaik yang didapat dipilih sebagai solusi optimum. Langkah 5 Memperbaharui tabulist dengan menambahkan rute solusi optimum yang diperoleh di langkah 4.

Gambar 6 Hasil Penjadwalan 3.2

Pengujian Perangkat Lunak Langkah-langkah dari proses perhitungan manual pembuatan jadwal mata pelajaran berdasarkan Algoritma TabuSearch. Langkah 1. Memilih solusi awal dan menentukan solusi awal tersebut sebagai solusi optimum pada iterasi ke-0. Solusi awal ditentukan dengan cara acak. Dengan metode tersebut, diperoleh solusi awal untuk kelas X MIPA 1, misalnya jadwal [4 7 5 3 9 1 2 8] dan secara otomatis solusi tersebut masuk dalam tabulist pada iterasi ke-0 sekaligus sebagai solusi optimum awal. Langkah 2 Menentukan iterasi selanjutnya dan mencari solusi alternatif yang tidak melanggar kriteria tabu. Solusi alternatif diperoleh dengan menukar posisi variabel jadwal berdasarkan indeks. Pada iterasi ke-0 diperoleh tabulist [4 7 5 3 9 1 2 8], maka solusi alternatif yang didapat, yaitu: Jika indeks (1), maka posisi titik pertama ditukar dengan posisi titik ke-2. Diperoleh jalur alternatif: [7 4 5 3 9 1 2 8]. Jika indeks (2), maka posisi titik pertama ditukar dengan posisi titik ke-3. Diperoleh jalur alternatif: [5 7 4 3 9 1 2 8].

Langkah 6 Apabila kriteria pemberhentian dipenuhi, maka proses berhenti. Jika tidak, proses diulang kembali mulai langkah 2 dan akan berhenti ketika kriteria pemberhentian dipenuhi. Dalam tugas akhir ini, kriteria pemberhentian yang dipakai, yaitu setelah didapatkan jadwal optimum yang sama pada tabulist atau tidak terdapat lagi pelanggaran pada jadwal yang dibuat.

4. KESIMPULAN Kesimpulan pada penelitian ini adalah sebagai berikut. 1. Sistem informasi ini dapat dijadikan dasar dalam pembuatan penjadwalan mata pelajaran pada SMA Negeri 4 Kendari. 2. Sistem informasi penjadwalan berbasis Algoritma Tabu Search dapat mengoptimalkan proses pembelajaran dengan menekan adanya bentrok jadwal, seperti adanya guru yang mengajar di kelas yang berbeda, tetapi di waktu yang sama. 3. Semua fungsi yang terdapat pada sistem informasi penjadwalan mata pelajaran telah berjalan dengan baik saat dilakukan uji blackbox sehingga sudah bisa digunakan oleh Kepala Bagian Kurikulum SMA Negeri 4 Kendari



1978-1520

4. Algoritma Tabu Search dapat digunakan untuk mengoptimalkan penyusunan jadwal mata pelajaran SMA Negeri 4 Kendari sehingga dapat mempermudah proses penjadwalan yang dilakukan dibanding dengan memakai sistem yang lama.

 205 Problem with Sequence Dependent Setup Times, http://cs.brown.edu /research/pubs/theses/masters/2001/kas. pdf., diakses tanggal 11 September 2015 pukul 10.01

5. SARAN Berdasarkan hasil penelitian, ada beberapa saran untuk pengembangan sistem lebih lanjut, diantaranya sebagai berikut : 1. Perkembangan perangkat lunak lebih diperluas. Tidak hanya terbatas pada kegiatan pengolahan jadwal mata pelajaran saja, tetapi juga membahas pengolahan data yang lain. 2. Penelitian dapat dilanjutkan dengan menggunakan beberpa teknik penggabungan dengan metode algoritma pencarian yang lain. DAFTAR PUSTAKA [1]

Setiawan. A., Andriyanto, F., Putro L. S., Nurcahya, P. T. P. dan Permana, U., 2014, Perbandingan Algoritma Ant Colony Optimization, Disjktra, Tabu Search, Multiple Ant Colony System untuk Vehicle Routing Problem dengan Time Window, https://www.scribd.com/doc /209087834/Perbandingan-AlgoritmaAnt-Colony-Optimization-DisjktraTabu-Search-Multiple-Ant-ColonySystem-untuk-Vehicle-Routing-Problemdengan-Time-Window, diakses tanggal 14 November 2015 pukul 15.00

[2]

Sahputra, I. H., Octavia, Tanti dan Chandra A. S., 2009, Tabu Search Sebagai Local Search pada Algoritma Ant Colony Untuk Penjadwalan Flowshop, Jurnal Teknik Industri, Fakultas Teknologi Industri, Universitas Kristen Petra, Surabaya, Vol. 11, No. 2, pp. 188-194.

[3]

Aryawan, P. T. dan Betrianis, 2003, Penerapan Algoritma Tabu Search Dalam Penjadwalan Job Shop, Fakultas Teknik, Universitas Indonesia, Depok.

[4]

Schmidt, K., 2001, Using Tabu Search to Solve the Job Shop Scheduling Title of manuscript is short and clear, implies research results (First Author)

206



IMPLEMENTASI ALGORITMA TABU SEARCH PADA APLIKASI PENJADWALAN MATA PELAJARAN (STUDI KASUS: SMA NEGERI 4 KENDARI)

Recommend Documents