NIK, nama dosen, alamat, dan nomo

BAB IV ANALISA DAN PERANCANGAN Analisa merupakan tahapan yang sangat penting dalam pembuatan sistem berbasis komputer. Pada tahap ini dilakukan proses pengidentikasian kebutuhankebutuhan sistem. Setelah tahap ini selesai dan hasil analisa didapatkan, maka dilanjutkan dengan tahap perancangan berdasarkan analisa permasalahan yang telah dilakukan. Perancangan yang dibuat harus memiliki kesesuaian dengan analisa sistem yang telah dilakukan pada tahapan sebelumnya.

1.1.

Analisa Analisa yang akan diuraikan pada bab ini terdiri dari beberapa tahapan,

antara lain sebagai berikut: 4.1.1. Analisa Kebutuhan Data Secara umum, proses penjadwalan penggunaan laboratorium dibutuhkan beberapa data pokok seperti kelas praktikum, asisten, dosen, ruangan laboratorium, waktu kosong asisten, waktu kosong dosen, waktu kosong kelas dalam hal ini adalah mahasiswa. 1. Kelas Praktikum Kelas Praktikum terdiri dari beberapa data diantaranya ID Kelas, Kode Pengajar, NIP Dosen Pengampu, Mata Praktikum, SKS. Setiap kelas praktikum tentunya memiliki pengajar yang berbeda, dan setiap kelas dapat memiliki seorang pengajar atau lebih. Pengajar dapat berasal dari data dosen, atau data asisten. SKS menentukan lamanya kelas praktikum tersebut berlangsung. Dalam kasus ini, 1 SKS bernilai 50 menit. 2. Asisten Data asisten berfungsi sebagai data pengajar untuk kelas praktikum. Data asisten terdiri dari NIM dan Nama mahasiswa.

IV-1

3. Dosen Data dosen berfungsi sebagai data pengajar atau pengampu untuk kelas praktikum. Data Dosen terdiri dari NIP/NIK, nama dosen, alamat, dan nomor handphone. 4. Ruang laboratorium Ruang laboratorium berfungsi sebagai variable tempat untuk meletakkan pelaksanaan kelas praktikum berdasarkan waktu tertentu. Data ruang laboratorium terdiri dari ID Ruang, dan nama ruang. 5. Waktu Kosong asisten Waktu kosong asisten berfungsi sebagai variable penentu pengambilan keputusan penyusunan jadwal, jika asisten yang bersangkutan mengajar pada suatu kelas yang akan dijadwalkan. Waktu kosong berupa range atau jarak selama kurun waktu tertentu yang mana pada saat itu asisten tidak memiliki kegiatan yang lain. Data waktu kosong asisten terdiri dari NIM, hari, pukul awal, dan pukul akhir. 6. Waktu Kosong dosen Sama seperti waktu kosong asisten, waktu kosong dosen juga berfungsi sebagai variable penentu pengambilan keputusan jika dosen yang bersangkutan mengajar pada kelas yang akan dijadwalkan. Data waktu kosong dosen terdiri dari NIP/NIK, hari, pukul awal, dan pukul akhir. 7. Waktu Kosong kelas Sama seperti waktu kosong asisten dan dosen, waktu kosong kelas juga berfungsi sebagai variable penentu pengambilan keputusan. Dalam hal ini, data waktu kosong kelas berupa waktu kosong yang dimiliki mahasiswa pada kelas tersebut. Data waktu kosong kelas terdiri dari ID Kelas, hari, pukul awal, dan pukul akhir.

4.1.2. Analisa Model Fungsional Sistem Pada tahap ini dilakukan proses pemodelan sistem secara bertahap. Yang mana secara keseluruhan pemodelan ini menggambarkan input yang diproses pada sistem, menjadi output yang dibutuhkan bagi pengguna sistem. Pemodelan

IV-2

fungsional sistem meliputi Data Flow Diagram (DFD) yang terdiri dari Context Diagram (Diagram konteks), DFD level 1, dan DFD level 2. DFD merupakan suatu diagram yang menjelaskan alur data pada suatu sistem dengan menggunakan notasi-notasi tertentu, yang penggunaannya sangat membantu untuk memahami sistem secara logika, tersruktur dan jelas. DFD diawali dengan penentuan Entitas yang terlibat di sistem. Setelah itu, merancang Context Diagram sebagai level tertinggi dalam sebuah DFD yang menggambarkan hubungan entitas terhadap sistem secara umum. Kemudian merancang DFD Level 1 yang mengklasifikasikan sistem menjadi beberapa proses utama. Selanjutnya merancang DFD Level 2 yang menggambarkan aliran data secara khusus dengan mengklasifikasikan proses utama menjadi beberapa subproses. 4.1.2.1. Context Diagram

Gambar 4.1. Diagram Konteks

Entitas yang terlibat pada sistem ini adalah kepala laboratorium(kalab), dosen, asisten, dan laboran. Seorang kalab mengirimkan data matapraktikum, data dosen, data asisten, ruang labor, data pegawai labor, serta data hak akses ke sistem. Kemudian, seorang kalab juga menerima data jadwal dari sistem. Entitas IV-3

berikutnya adalah dosen. Dosen mengirimkan data kelas praktikum, data waktu kosong dosen, data waktu kosong mahasiswa, pengajar, dan data asisten dosen. Seorang dosen juga menerima data yang terdiri dari jadwal, hak_akses, data matapraktikum, dan data asisten. Entitas berikutnya adalah asisten. Asisten hanya mengirimkan waktu kosong asisten. Selain mengirim data, seorang asisten juga menerima data jadwal dan hak_akses dari sistem. Entitas yang terakhir adalah laboran. Pada sistem ini, laboran hanya menerima data berupa data jadwal dan hak_akses. 4.1.2.2. DFD Level 1 Sistem Penjadwalan Ruang Laboratorium

Gambar 4.2. DFD Level 1

IV-4

Dalam DFD level 1 ini terdapat 4 proses utama yakni : 1. Pengolahan data master 2. Registrasi 3. Input waktu kosong 4. Penjadwalan Entitas pertama yang terlibat adalah kalab. Kalab memberikan data mata praktikum, data asisten, data ruang labor, data dosen, dan data pegawai labor ke proses pengolahan data master. Kalab juga memberikan hak akses pada proses registrasi. Kalab juga menerima data jadwal dari proses penjadwalan. Entitas kedua yang berperan ialah dosen. Dosen memberikan data kelas praktikum, pengajar, dan asisten dosen ke dalam proses registrasi. Dosen juga menerima data hak akses, data asisten dan data mata praktikum dari proses registrasi, data jadwal dari proses penjadwalan. Dosen juga memberikan data waktu kosong dosen, dan waktu kosong mahasiswa pada proses input waktu kosong. Asisten menerima data hak akses dari proses registrasi, dan data jadwal dari proses penjadwalan. Asisten juga memberikan data waktu kosong asisten pada proses input waktu kosong. Selain itu, Laboran hanya menerima data jadwal dari proses penjadwalan. Poses DFD level 1 akan dijelaskan melalui tabel 4.1. Tabel 4.1. Proses DFD level 1 Nama

Deskripsi

Pengolahan Data master

Berisi proses penginputan dan pengolahan data master dosen, asisten, matapraktikum, ruang labor, dan pegawai labor.

Registrasi

Berisi proses pemberian hak_akses bagi user untuk mengakses sistem, dan meregistrasikan kelas praktikum yang akan di jadwalkan, serta meregistrasikan asisten dosen.

Input waktu kosong

Berisi proses penginputan waktu kosong mahasiswa, dosen, dan asisten.

Penjadwalan

Berisi proses penyusunan jadwal oleh sistem.

IV-5

4.1.2.3. DFD Level 2 1. Proses Pengolahan Data Master

Gambar 4.3. DFD Level 2 Pengolahan data master

Pada DFD level 2 untuk proses pengolahan data master ini kalab memberikan data dosen kedalam proses master data dosen, data mata praktikum kedalam proses master data praktikum, data asisten kedalam proses master asisten, dan data ruang labor pada proses master data ruang labor, serta data pegawai labor pada proses master data pegawai labor. Proses DFD level 2 untuk proses pengolahan data master akan dijelaskan pada tabel 4.2. Tabel 4.2. Proses DFD level 2 proses 1 Nama Master data dosen

Deskripsi Berisi proses penginputan dan pengolahan data master dosen

Master data mata praktikum

Berisi proses penginputan dan pengolahan data master mata praktikum

Master data asisten

Berisi proses penginputan dan pengolahan data asisten

Master data ruang labor

Berisi proses penginputan dan pengolahan data ruang labor

Master data pegawai labor

Berisi proses penginputan dan pengolahan data pegawai labor

IV-6

Dari tabel diatas terlihat bahwa proses pengolahan data master terdiri dari 5 jenis pengolahan data, Namun bentuk pengolahan kelima data tersebut pada dasarnya adalah sama, yakni seorang kepala laboratorium dapat menambah, mengedit atau menghapus data master. 2. Proses Registrasi

Gambar 4.4. DFD Level 2 Registrasi

Pada DFD level 2 proses registrasi ini entitas yang terlibat ialah dosen, asisten, laboran, dan kalab. Dosen mendapatkan hak akses dari proses pemberian hak akses. Dosen juga mengirimkan data kelas praktikum dan pengajar kepada proses registrasi kelas praktikum. Dosen menerima data mata praktikum dari proses registrasi kelas praktikum. Entitas kedua ialah kepala laboratorium(kalab). Kalab memberikan hak akses ke proses pemberian hak akses, dan entitas yang lain menerima data hak akses. Proses DFD level 2 untuk registrasi dijelaskan pada tabel 4.3. IV-7

Tabel 4.3. Proses DFD level 2 proses 2 Nama

Deskripsi

Pemberian hak akses

Berisi proses pemberian hak akses kepada user

Registrasi asisten dosen

Berisi proses registrasi data asisten dosen oleh dosen yang bersangkutan

Registrai kelas praktikum

Berisi proses registrasi data kelas praktikum

3. Proses Input Waktu Kosong

Gambar 4.5. DFD Level 2 Input waktu kosong

Pada proses input waktu kosong, terdapat 3 subproses yaitu waktu kosong dosen, waktu kosong mahasiswa, dan waktu kosong asisten. Pada subproses waktu kosong dosen, entitas dosen mengirimkan data waktu kosong dosen. Sementara itu, pada subproses waktu kosong mahasiswa, entitas dosen mengirimkan data waktu kosong mahasiswa. Entitas asisten mengirimkan data waktu kosong asisten pada subproses waktu kosong asisten. Proses DFD level 2 untuk proses input waktu kosong akan dijelaskan pada tabel 4.4. Tabel 4.4. Proses DFD level 2 proses 3 Nama Waktu kosong dosen

Deskripsi Berisi proses penginputan data waktu kosong yang dimiliki dosen.

Waktu kosong mahasiswa

Berisi proses penginputan waktu kosong mahasiswa.

Waktu kosong asisten

Berisi proses penginputan waktu kosong asisten.

IV-8

4.1.3. Analisa Data Sistem Analisa data sistem menggambarkan seluruh data-data yang terlibat dalam proses pada sistem atau disebut dengan database. Analisa data digambarkan melalui ERD (Entity Relationship Diagram). ERD merupakan salah satu metode pemodelan basisdata yang digunakan untuk menghasilkan pemodelan konseptual untuk data semantik sistem. Yang mana pada ERD akan di jelaskan hubungan antar entitas yang dalam hal ini adalah tabel data. Pemodelan yang digambarkan pada ERD merupakan lanjutan dari pemodelan oleh DFD. Data yang menjadi objek pemodelan ERD merupakan basis data hasil pemodelan pada DFD yang telah digambarkan sebelumnya. Pada ERD akan digambarkan secara jelas bagaimana hubungan setiap data, mulai dari derajat kardinalitas sampai dengan atribut-atribut setiap data. Pemodelan ERD sistem penjadwalan penggunaan laboratorium dijelaskan pada gambar 4.6.

Gambar 4.6. Entity Relationship Diagram (ERD)

IV-9

Dari gambar ERD diatas terlihat bahwa tabel dosen memiliki hubungan “memiliki” dengan tabel hak akses dengan derajat kardinalitas one to one yang berarti satu orang dosen hanya memiliki satu hakakses. Dosen juga memiliki hubungan “memiliki” dengan tabel waktu kosong dosen dengan derajat kardinalitas one to many yang artinya satu dosen dapat memiliki banyak waktu kosong. Dosen juga memiliki hubungan many to many dengan tabel data mata praktikum sehingga menghasilkan tabel relasi kelas praktikum. Tabel kelas praktikum memiliki hubungan many to many dengan data ruang labor sehingga menghasilkan tabel relasi jadwal. Keterangan setiap entitas pada ERD diatas terlampir pada tabel 4.5. Tabel 4.5. Keterangan Entitas Pada ERD No 1

Nama Data_dosen

Deskripsi Penyimpanan master dosen

Atribut data #nip

Primary key #nip

nama no_hp Alamat

2

hak_akses

Penyimpanan

data #id_user

#id_user

hak akses user yang ##nip akan

mengakses username

sistem

pwd Jenis

3

Data_asisten

Penyimpanan master asisten

data #nim

#nim

Nama Alamat No_hp

4

Data_pegawai_labor

Penyimpanan master labor

data #nik

#nik

pegawai Nama Alamat No_hp

IV-10

Tabel 4.6. Lanjutan keterangan Entitas Pada ERD No

Nama

Deskripsi

5

kls_praktikum

Penyimpanan

Atribut data #id_kelas

kelas_praktikum

Primary Key #id_kelas

##nip

yang di registrasikan ##kode_matapraktikum dosen pengampu 6

Waktu_kosong_dose

Penyimpanan

n

waktu

Kelas data #kode_Pengajuan

#kode_pengajuan

ketersediaan ##nip

dosen

untuk hari

menggunakan labor

pukul_awal pukul_akhir

7

Waktu_kosong_

Penyimpanan

mahasiswa

waktu

data #kode_waktu

#kode_waktu

kosong ##id_kelas

mahasiswa

untuk hari

praktikum

pukul_awal pukul_akhir

8

Waktu_kosong_

Penyimpanan

asisten

waktu

data #kode_pengajuan

#kode_pengajuan

ketersediaan ##nim

asisten

untuk hari

menggunakan labor

pukul_awal pukul_akhir

9

Asisten_dosen

Penyimpanan

data ##nip

asisten untuk setiap ##nim dosen pengampu. 10

Pengajar

Penyimpanan

data ##id_kelas

pengajar setiap kelas, ##pengajar dapat

berasal

dari

data

asisten

atau

dosen. 11

Data_matapraktikum

Penyimpanan mata_praktikum

data #kode_matapraktikum mata_praktikum

#kode_ matapraktikum

sks

IV-11

Tabel 4.7. Lanjutan keterangan Entitas Pada ERD No 12

Nama

Deskripsi

Jadwal

Penyimpanan jadwal

Atribut

Primary Key

data ##id_ruang ##id_kelas hari jam

13

Data_ruang_labor

Penyimpanan ruang labor

data #id_ruang

#id_ruang

Ruang

4.1.4. Analisa Penyelesaian Secara umum, proses penjadwalan dapat digambarkan melalui gambar 4.7.

Gambar 4.7. Prosedur sistem secara umum

Setiap kelas praktikum yang akan dijadwalkan untuk menggunakan ruangan laboratorium tentunya memiliki pengajar dan mahasiswa yang berbedabeda. Begitu pula waktu kosong yang dimiliki keduanya. Untuk itu, sistem ini akan mengelola waktu kosong yang dimiliki pengajar dan mahasiswa setiap kelas. Mengambil kecocokan waktu diantara kedua belah pihak yang disimbolkan dengan nilai irisan diantara keduanya. Kemudian hasilnya akan diolah kembali dengan beberapa tahapan untuk mencocokkan waktu setiap kelas dengan ruangan IV-12

yang tersedia. Sehingga dari proses itu dihasilkan jadwal penggunaan ruangan yang tepat tanpa adanya bentrokan dan sesuai dengan waktu kosong yang dimiliki pengajar dan mahasiswa. Proses penyusunan jadwal direpresentasikan dengan menggunakan struktur data graph berbobot. Setiap state adalah kandidat solusi yang merupakan pemasangan kelas pada suatu waktu tertentu pada ruang tertentu. Setiap sisi graph memiliki bobot tertentu. Bobot akan menentukan solusi terbaik yang akan dipilih melalui penelusuran graph tersebut. Solusi terbaik adalah jalur graph dengan total bobot terkecil, dan untuk menelusuri jalur terpendek graph digunakan metode Modified BiDirectional A*. Contoh kasus penjadwalan penggunaan ruang labor ditunjukkan pada tabel 4.8. Tabel 4.8. Contoh kasus penjadwalan penggunaan ruang labor No 1

Kelas Praktikum Kelas 1

SKS 3

Pengajar A

Waktu kosong mahasiswa Selasa(10:30-12:10), Senin(08:00-10:30), Rabu(08:00-12:10)

2

Kelas 2

2

B,C

Selasa(10:30-12:10), Kamis(08:00-10:30)

3

Kelas 3

3

D

Senin(08:00-10:30), Jum'at(13:00-15:30)

4

Kelas 4

3

D

Senin(08:00-12:10), Selasa(08:00-12:10)

5

Kelas 5

2

E

Senin(08:00-12:10), Selasa(08:00-15:30), Rabu(10:30-12:10)

Dari tabel diatas terlihat bahwa pada contoh kasus kelas yang ingin dijadwalkan terdiri dari 5 kelas. Setiap kelas memiliki pengajar yang berbeda. Data waktu kosong pengajar ditunjukkan pada tabel 4.9.

IV-13

Tabel 4.9. Waktu kosong pengajar No 1

Pengajar A

Waktu kosong Senin(08:00-12:10), Selasa(10:30-14:40)

2

B

Senin(09:40-12:10) Selasa(10:30-12:10)

3

C

Selasa(08:00-12:10)

4

D

Senin(08:00-15:30), Selasa(08:00-10:30)

5

E

Senin(08:00-10:30), Selasa(08:00-12:10)

Berikut adalah langkah-langkah yang dilakukan pada tahap penyusunan jadwal sesuai dengan contoh kasus diatas: 1. Mengumpulkan semua simpul kemungkinan jadwal 2. Merepresentasikan kasus dalam bentuk graph 3. Menentukan bobot setiap edge atau sisi pada graph 4. Penelusuran jalur terpendek dengan algoritma MBDA* 2. Membersihkan data simpul dari simpul yang sudah terjadwal 3. Mengulangi langkah 1-5 sebagai solusi akhir jadwal

1. Mengumpulkan semua simpul kemungkinan jadwal Langkah awal adalah dengan mengumpulkan semua simpul kemungkinan pasangan parameter yang dapat disusun menjadi jadwal. Berikut adalah tahapan untuk mendapatkan hasil pada langkah awal ini, yakni simpul yang akan menjadi kandidat solusi: a. Cocokkan waktu semua pengajar pada setiap kelas (khusunya jika pengajar pada satu kelas lebih dari 1). Pada tahap ini, dari semua waktu kosong yang dimiliki setiap pengajar ditentukan waktu yang dapat digunakan secara bersama oleh setiap pengajar. Contoh pada kelas 2: Waktu kosong pengajar B : Senin(09:40-12:10), Selasa(10:30-12:10). IV-14

Waktu kosong pengajar C : Selasa(08:00-12:10). Waktu yang dapat digunakan secara bersama oleh pengajar B dan C (Waktu B ∩ Waktu C) : Selasa(10:30-12:10). Karena pada saat itu dosen B dan C sama-sama memiliki waktu luang. Berikut adalah algoritma untuk melakukan tahap ini: Algoritma fungsi ”iriskan” 1

Function iriskan(larik1, larik2)

2

i<-0;

3

While (larik1)

4

j<-0;

5

While (larik2)

6

If(larik1[i]== larik2[j])

7

Hasil <- larik1[i]

8

endif

9

j<-j+1

10

endwhile

11

i<-i+1;

12

endwhile

13

iriskan  hasil;

14

endfunction

No 1

Pada baris 1 terlihat bahwa pada fungsi ini parameter inputan terdiri dari dua larik yang akan diiriskan.

No 3-12

Merupakan proses pemeriksaan isi larik1 terhadap isi larik2.

No 6

Jika terdapat nilai yang sama diantara kedua larik, maka nilai yang sama akan disimpan sebagai hasil irisan. Fungsi ”iriskan” merupakan fungsi yang akan diterapkan pada saat

mengiriskan waktu kosong setiap pengajar pada suatu kelas. Sehingga didapat waktu kosong yang dapat digunakan oleh seluruh pengajar pada suatu kelas secara bersamaan. Dari fungsi ”iriskan”, isi larik1 dan larik2 yang memiliki nilai sama akan disimpan sebagai hasil irisan. Untuk lebih memperjelas perhatikan contoh berikut: IV-15

Larik_1= {A, B, C, D} Larik_2= { B, C, E,F} Jika dari fungsi ”iriskan” dipanggil dengan parameter inputan kedua larik diatas maka, hasil fungsi tersebut adalah larik baru dengan isi B & C. Setelah fungsi ”iriskan” dirancang, maka langkah selanjutnya adalah menerapkan fungsi tersebut pada proses utama tahap pengirisan waktu kosong pengajar pada suatu kelas. Berikut adalah algoritma utama tersebut: 1

While (pengajar)

2

while(waktu_pengajar)

3

idx_waktu<-0;

4

batas_awal<- pukul_awal;

5

batas_akhir<- pukul_akhir;

6

waktu_awal<- pukul_awal;

7

while ((waktu_awal>=batas_awal)and

8

(waktu_awal<= batas_akhir))

9

waktu_pengajar[idx_waktu]<- hari+waktu_awal;

10

idx_waktu<- idx_waktu+1;

11

date_add(waktu_awal, +50 minutes);

12

endwhile

13 14

endwhile If (idx_pengajar==1)

15 16

Hasil<- waktu_pengajar end else

17

Hasil <- iriskan(hasil, waktu_pengajar)

18

endif

19

Idx_pengajar <- idx_pengajar+1

20

endwhile

No 2-13

Merupakan proses mencacah seluruh waktu kosong setiap pengajar.

No 7-12

Merupakan proses pemecahan setiap waktu kosong dalam 50 menit. Pengulangan akan dilakukan selama waktu awal berada diantara batas awal dan batas akhir.

No 9

Menyimpan

hasil

waktu_pengajar[idx_pengajar].

pemecahan Data

dalam

disimpan

dalam

larik format

“hari+jam”. IV-16

No 14-16

Jika pengajar pada suatu kelas hanya satu, maka waktu kosong tidak perlu diiriskan.

Dari algoritma diatas dan contoh kasus diatas dapat diperoleh hasil irisan waktu kosong pengajar sebagai terlampir pada tabel 4.10. Tabel 4.10. Hasil irisan waktu kosong pengajar No

Kelas Praktikum

Pengajar

Hasil irisan waktu kosong pengajar

1

Kelas 1

A

Senin(08:00-12:10), Selasa(10:30-14:40)

2

Kelas 2

B,C

Selasa(10:30-12:10)

3

Kelas 3

D

Senin(08:00-15:30), Selasa(08:00-10:30)

4

Kelas 4

D

Senin(08:00-15:30), Selasa(08:00-10:30)

5

Kelas 5

E

Senin(08:00-10:30), Selasa(08:00-12:10)

b. Mencocokkan waktu kosong mahasiswa dengan hasil irisan waktu pengajar Pada tahap ini, prosedur yang dilakukan hampir sama dengan tahap sebelumnya. Perbedaannya hanyalah pada parameter yang akan diiriskan. Pada tahap ini, waktu kosong mahasiswa setiap kelas akan diiriskan dengan hasil irisan waktu pengajar setiap kelas berdasarkan tahap sebelumnya. Hal tersebut dilakukan dengan fungsi ”iriskan” yang telah dideskripsikan diatas. Dari tahap ini, maka akan didapat hasil irisan antara waktu kosong seluruh pengajar dan mahasiswa pada suatu kelas, yang berarti bahwa pada waktu tersebut kedua pihak dapat dijadwalkan secara bersamaan sebagaimana terlampir pada tabel 4.11.

IV-17

Tabel 4.11. Hasil irisan waktu kosong pengajar dan mahasiswa No

Kelas

Pengajar

Praktikum

Hasil irisan waktu

Waktu kosong

Hasil Irisan waktu

kosong pengajar

Mahasiswa

mahasiswa dan pengajar

1

Kelas 1

A

Senin(08:00-12:10),

Selasa(10:30-12:10),

Senin(08:00-10:30),

Selasa(10:30-14:40)

Senin(08:00-10:30),

Selasa(10:30-12:10),

Rabu(08:00-12:10) 2

Kelas 2

B,C

Selasa(10:30-12:10)

Selasa(10:30-12:10),

Selasa(10:30-12:10)

Kamis(08:00-10:30) 3

4

5

Kelas 3

Kelas 4

Kelas 5

D

D

E

Senin(08:00-15:30),

Senin(08:00-10:30),

Senin(08:00-10:30)

Selasa(08:00-10:30)

Jum'at(13:00-15:30)

Senin(08:00-15:30),

Senin(08:00-12:10),

Senin(08:00-12:10),

Selasa(08:00-10:30)

Selasa(08:00-12:10)

Selasa(08:00-10:30)

Senin(08:00-10:30),

Senin(08:00-12:10),

Senin(08:00-10:30),

Selasa(08:00-12:10)

Selasa(08:00-15:30),

Selasa(08:00-12:10)

Rabu(10:30-12:10)

c. Menguraikan setiap kelas berdasarkan waktu kosong pengajar dan mahasiswa sesuai SKS Setelah waktu kosong hasil irisan antara mahasiswa dan pengajar telah didapatkn. Kemudian hasil tersebut diuraikan sesuai SKS kelas praktikum yang bersangkutan. Hasil penguraian tersebut merupakan simpul yang akan menjadi kandidat solusi terakhir proses penjadwalan. Prosedur penamaan simpul harus memenuhi aturan atau formasi berikut: Penamaan simpul = Kode_kelas(5digit)+hari+pukul_awal+pukul_akhir

Aturan tersebut bertujuan untuk mempermudah penyusunan jadwal dan penyimpanan hasil akhir jadwal kedalam database. Karena pada proses penyimpunan dilakukan pemecahan kembali setiap simpul untuk mendapatkan data pokok seperti kode kelas praktikum, hari, serta jam.

IV-18

Pada proses penguraian simpul, semua kemungkinan pasangan kelas terhadap slot waktu akan dibangkitkan. Sehingga jika kelas 4 diuraikan menjadi simpul kandidat solusi, maka hasilnya adalah sebagai berikut: Senin(08:00-12:10) dan Selasa(08:00-10:30). SKS Kelas 4 adalah 3, sehingga jarak waktu disetiap simpul adalah 50x3SKS= 150 menit. Jika diuraikan kedalam bentuk state kandidat solusi, maka akan dihasilkan simpul berikut: Simpul 1 : Kelas4Senin08:00-10:30 Simpul 2 : Kelas4Senin08:50-11:20 Simpul 3 : Kelas4Senin09:40-12:10 Simpul 4 : Kelas4Selasa08:00-10:30 Berikut adalah algoritma pada proses ini: 1

While (kelas)

2

while(waktu_kemungkinan)

3

batas_awal<- waktu_kemungkinan.pukul_awal;

4

batas_akhir<- waktu_kemungkinan.pukul_akhir;

5

interval= kelas.sks*50;

6

waktu_awal<- batas_awal;

7

waktu_akhir<- waktu_awal + interval minutes

8

While(((waktu_awal>=batas_awal) and

9

(waktu_awal<= batas_akhir)) and

10

((waktu_akhir>=batas_awal)and

11

(waktu_akhir<= batas_akhir)))

12

Data_simpul<- hari+waktu_awal+waku_akhir

13

waktu_awal  waktu_awal+50 minutes

14

waktu_akhir  waktu_akhir +50 minutes

15

endwhile

16 17

endwhile endwhile

No 2-16

Merupakan proses mencacah seluruh waktu kemungkinan setiap kelas.

IV-19

No 3-4

Inisialisasi batas_awal dan batas akhir dalam setiap waktu kemungkinan. Untuk membatasi pengulangan dalam memecahkan setiap kemungkinan waktu kosong berdasarkan jumlah SKS.

No 6-7

Inisialisasi waktu_awal dan waktu_akhir dalam setiap waktu kemungkinan. Sebagai iterasi dalam proses pemecahan waktu menjadi simpul. Setiap pengulangan, nilai ini akan ditambahkan dengan jumlah SKS.

No 8-15

Merupakan proses pemecahan setiap waktu kemungkinan sesuai SKS. Pengulangan akan dilakukan selama waktu awal dan waktu akhir berada diantara batas awal dan batas akhir.

No 12

Menyimpan hasil pemecahan dalam larik data_simpul. Data disimpan dalam format “hari+waktu_awal_waktu_akhir”. Sehingga dari algoritma diatas, dapat dihasilkan data simpul dalam variabel

”data_simpul”sebagai berikut: Simpul = ( Kelas1Senin08:00-10:30, Kelas2Selasa10:30-12:10, Kelas3Senin08:00-10:30, Kelas4Senin08:00-10:30, Kelas4Senin08:50-11:20, Kelas4Senin09:40-12:10, Kelas4Selasa08:00-10:30, Kelas5Senin08:00-09:40, Kelas5Senin08:50-10:30, Kelas5Selasa08:00-09:40, Kelas5Selasa08:50-10:30,Kelas5Selasa09:40-11:20, Kelas5Selasa10:30-12:10 ) 2. Merepresentasikan kasus dalam bentuk graph Setelah semua simpul terkumpul, setiap simpul akan menjadi state yang akan direpresentasikan dalam bentuk struktur data graph. Graph yang digunakan adalah graph berarah. Karena setiap simpul yang terhubung akan menjadi kandidat solusi akhir penjadwalan, dan setiap simpul memiliki waktu yang berbeda. Begitu juga dengan urutan simpul. Simpul A yang terhubung dengan B, tidak sama dengan simpul B yang terhubung dengan simpul A. IV-20

A  B ≠ BA Suatu simpul akan terhubung dengan simpul lainnya jika memenuhi sarat tertentu. Sarat tersebut adalah jika simpul tersebut dapat diurutkan dengan simpul lainnya berdasarkan urutan waktu, dan tidak ada simpul lain yang dapat mengisi diantara keduanya. Jika terdapat data simpul sebagai berikut: ASenin08:00-10:30, BSelasa10:30-12:10, CSenin08:50-11:20, DSenin10:30-12:10. Dari simpul diatas simpul A tidak dapat dihubungkan atau dijadikan parent bagi simpul C (AC), karena A bukan merupakan urutan waktu yang sesuai. Seharusnya urutan yang sesuai dengan A adalah simpul yang memiliki waktu hari senin jam 10:30 keatas. Jika demikian, maka simpul A dapat dipasangkan dengan simpul D(AD), karena keduanya merupakan urutan waktu yang sesuai. Meskipun simpul A dan B merupakan urutan waktu yang sesuai, keduanya tidak dapat dihubungkan. Karena diantara simpul lain terdapat simpul yang lebih dekat jarak waktunya terhadap simpul A, yaitu simpul D. Dengan ketentuan diatas, dapat disusun suatu fungsi untuk menentukan apakah suatu simpul dapat dipasangkan atau dijadikan parent langsung bagi simpul lain. Fungsi tersebut diberi nama fungsi ”can_be_child”. Didalam fungsi tersebut terdapat fungsi pendukung yang membantu fungsi dalam memberikan output,yaitu fungsi ”is_bigger” dan ”is_smaller”. Fungsi ”is_bigger” memiliki dua parameter, yaitu state1 dan state2. Kedua parameter tersebut merupakan data simpul yang akan diperiksa waktu keduanya. Fungsi ini akan mengembalikan nilai true jika waktu state1 lebih besar dari waktu state2. Lebih besar dalam hal ini adalah waktu yang lebih akhir. Contohnya adalah senin 09:00-10:00 lebih akhir dari pada senin 08:00-09:00. Begitu juga selasa 08:00-10:30 lebih akhir dari pada senin 08:00-10:30. Sementara itu fungsi ”is_smaller” adalah kebalikan dari fungsi sebelumnya. Fungsi ini akan mengembalikan nilai true jika waktu state1 lebih IV-21

kecil dari waktu state2. Lebih kecil dalam hal ini adalah waktu yang lebih dini atau lebih awal. Contohnya adalah senin 08:00-09:00 lebih awal dari senin 09:0010:00. Begitu juga senin 08:00-10:30 lebih awal dari pada selasa 08:00-10:30. Ketiga fungsi diatas merupakan fungsi yang dibutuhkan dalam proses penyusunan data simpul kedalam struktur data graph. Ketiga fungsi tersebut akan dideskripsikan melalui algoritma berikut ini: Algoritma fungsi ”is_bigger” 1

function is_bigger(state1,state2)

2

index= array("Senin"=1,"Selasa"=2,"Rabu”=3,"Kamis"=4,"Jum'at"=5)

3

if(state1.hari.index > state2.hari.index) is_bigger  true;

4 5

end else if (state1.hari.index == state2.hari.index)

6

if (state1.jam >= state2.jam) is_bigger  true;

7 8

end else is_bigger  false;

9 10

endif

11

end else is_bigger  false;

12 13 14

endif endfunction

No 3-5

Merupakan proses pemeriksaan hari untuk setiap parameter. Jika index hari pada state1 lebih besar, maka aksi fungsi akan mengembalikan nilai true.

No 5-11

Untuk hari yang sama dapat dilakukan pemeriksaan terhadap jam. Jika state1 memiliki jam yang lebih besar, maka fungsi akan mengembalikan

nilai

true.

Jika

tidak

maka

fungsi

akan

mengembalikan nilai false. No 11-13

Jika hari pada state 1 memiliki index yang lebih kecil maka fungsi akan mengembalikan nilali false

IV-22

Algoritma fungsi ”is_smaller” 1

function is_smaller(state1,state2)

2

index array("Senin"=1,"Selasa"=2,"Rabu”=3,"Kamis"=4,"Jum'at"=5)

3

if(state1.hari.index < state2.hari.index) is_smaller  true;

4 5

end else if (state1.hari.index == state2.hari.index)

6

if (state1.jam <= state2.jam) is_smaller  true;

7 8

end else is_smaller  false;

9 10

endif

11

end else is_smaller  false;

12 13 14

endif endfunction

No 3-5

Merupakan proses pemeriksaan hari untuk setiap parameter. Jika index hari pada state1 lebih kecil, maka aksi fungsi akan mengembalikan nilai true.

No 5-11

Untuk hari yang sama dapat dilakukan pemeriksaan terhadap jam. Jika state1 memiliki jam yang lebih kecil, maka fungsi akan mengembalikan

nilai

true.

Jika

tidak

maka

fungsi

akan

mengembalikan nilai false. No 11-13

Jika hari pada state 1 memiliki index yang lebih besar maka fungsi akan mengembalikan nilali false

Algoritma fungsi ”can_be_child” 1 2

function can_be_child(parent, child, data_simpul) if(is_bigger(child,parent))

3

data_simpul  data_simpul-child;

4

data_simpul  data_simpul-parent;

5

i0;

6

while((ketemu== false) and (data_simpul[i]))

7

if(is_bigger(data_simpul[i],parent) and

8

is_smaller(datas_simpul[i],child))

9 10

ketemu true; end else

IV-23

11

Ketemu false;

12

endif

13

i i+1;

14

endwhile

15

if(ketemu== true) can_be_child  false;

16 17

end else can_be_child  true;

18 19

endif

20

end else can_be_child  false;

21 22 23

endif endfunction

No 2-20

Jika waktu parent lebih awal dari waktu child, maka periksa data simpul dan cari simpul yang lebih dekat jarak waktunya terhadap parent.

No 3-4

Menghapus data parent dan child pada Data simpul

No 6-14

Proses pencarian simpul yang waktunya terlatak diantara waktu parent dan child pada data simpul. Penelusuran dilakukan selama nilai ketemu = false dan data simpul masih ada.

No 15-17

Jika pencarian ditemukan, maka fungsi akan mengembalikan nilai false.

No 17-19

Jika pencarian tidak ditemukan, maka fungsi akan mengembalikan nilai true.

No 20-21

Jika waktu child lebih awal dari waktu parent atau sama, maka fungsi akan mengembalikan nilai false.

Fungsi ”can_be_child” diatas akan mengembalikan nilai true jika parameter parent yang dimasukkan dapat menjadi parent yang tepat bagi parameter child. Fungsi datas berguna dalam proses penyusunan simpul kedalam bentuk graph. Berikut adalah algoritma lengkap proses pembentukan graph dari data simpul yang telah dikumpulkan pada tahap sebelumnya:

IV-24

1

Idx_child  0;

2

J  1;

3

Child  array("s")

4

while (child[idx])

5

i0;

6

temp1;

7

while(data_simpul[i])

8 if(is_canbe_child(child[idx_child],data_simpul[i],data_simpul) 9

child[idx]->connectTo(data_simpul[i]);

10

if (in_array(data_state[i], child))

11

end else child  data_state[i]

12 13

endif

14

temp temp*0;

15

end else temp  temp*1;

16 17

endif

18

ii+1;

19

endwhile

20

if (temp== 1)

21

child[idx_child]->connectTo('g');

22

endif

23

Idx_child idx_child+1;

24

endwhile

No 3

Inisialisasi nilai pada larik child dengan “s” menandakan simpul dimulai dari “s”.

No 4-24

Proses penelusuran larik child untuk mencari simpul-simpul yang dapat dihubungkan dari child tersebut.

No 7-19

Untuk setiap child dilakukan proses penelusuran data simpul untuk mencari simpul-simpul yang dapat dihubungkan dari child tersebut.

No 9

Jika ditemukan simpul yang dapat dihubungkan dari child, maka hubungkan child ke simpul tersebut.

10-13

Jika ditemukan simpul yang dapat dihubungkan dari child, maka periksa simpul tersebut apakah sudah pernah berada di larik child atau belum. Jika belum, maka simpan simpul tersebut kedalam larik child. IV-25

No 14

Jika ditemukan simpul yang dapat dihubungkan dari child, maka kalikan nilai temp dengan 0. Sehingga berapapun nilai temp pada saat itu akan menjadi 0.

No 18

Jika tidak ditemukan simpul yang dapat dihubungkan dari child, maka kalikan nilai temp dengan 1. Sehingga berapapun nilai temp pada saat itu tidak akan berubah.

No 20-22

Jika nilai temp ==1 berarti bahwa pada child tersebut tidak pernah ditemukan simpul yang bisa dihubungkan dari child tersebut. Maka pada saat itu, hubungkan child tersebut ke simpul terakhir atau simpul “g”.

Dari algoritma diatas dan untuk data simpul yang telah didapat sebelumnya, maka hasil graph yang terbentuk diilustrasikan melalui gambar 4.8.

Gambar 4.8. Hasil akhir proses pembentukan graph IV-26

3. Menentukan bobot setiap edge atau sisi pada graph Setelah semua kemungkinan tersusun dalam bentuk graph, langkah selanjutnya adalah menetapkan bobot untuk setiap sisi yang menghubungkan setiap simpul. Langkah ini merupakan langkah yang sangat penting, karena bobot akan menentukan state yang terpilih dalam proses penelusuran oleh algoritma MBDA*.

Simpul-simpul

yang

terpilih

merupakan

jalur

graph

yang

menggambarkan solusi dari hasil penjadwalan. Dalam proses pemilihannya, bobot yang terendah memiliki kemungkinan terpilih lebih tinggi. Karena algoritma MBDA* pada dasarnya dirancang untuk menentukan jalur terpendek berdasarkan bobot terpendek. Dalam pencarian heuristik tidak terkecuali algoritma MBDA*, bobot ditentukan dengan fungsi heuristik. Algoritma MBDA* melakukan penelusuran graph secara dua arah, sehingga fungsi heuristik terdiri dari fungsi heuristik pencarian maju dan fungsi heuristik pencarian mundur. Penerapan algortima MBDA* untuk penjadwalan pada kasus ini sedikit memodifikasi fungsi heuristik MBDA* pada persamaan 2.4 dan 2.5. Modifikasi dilakukan terhadap selisih antara biaya perkiraan dari simpul n ke simpul G (hs(n)) dan biaya perkiraan dari simpul n ke simpul S (hg(n)) menjadi bernilai mutlak. Sehingga fungsi heuristik untuk simpul n pada pencarian maju (dari simpul start ke simpul goal) adalah: =

,

+ |ℎ

− ℎ

|

(4.1)

− ℎ

|

(4.2)

Sedangkan fungsi heuristik untuk simpul n pada pencarian mundur (dari simpul goal ke simpul start) adalah:

Dimana : ( , )

( , )

=

,

+ |ℎ

: Biaya sebenarnya dari S ke n : Biaya sebenarnya dari G ke n

hs(n)

: Biaya perkiraan dari n ke G

hg(n)

: Biaya perkiraan dari n ke S

Perubahan nilai mutlak tersebut dilakukan karena penerapan MBDA* pada penjadwalan dalam kasus ini menggunakan satu bobot heuristik dari dua arah IV-27

pencarian. Sehingga dari kedua fungsi heuristik(pencarian maju dan mundur) tidak akan memberikan perubahan nilai selisih antara biaya perkiraan dari simpul n ke simpul G (hs(n)) dan biaya perkiraan dari simpul n ke simpul S (hg(n)). Untuk itu, nilai selisih yang konstant antara pencarian maju dan pencarian mundur tidak akan memberikan perbedaan bobot heuristik suatu simpul dari kedua arah pencarian. Dari persamaan diatas terlihat bahwa dalam proses penjadwalan bobot graf terdiri dari dua jenis bobot, yaitu bobot sebenarnya (g(G,n) atau g(S,n)) dan bobot heuristik. Bobot sebenarnya merupakan total bobot sisi-sisi graf yang sedang ditelusuri. Pemberian bobot untuk setiap sisi graf ditentukan oleh beberapa kriteria, yakni sisa waktu terbuang, kelas yang berulang, dan status dosen atau pengajar yang sudah terjadwal di jam yang sama. a. Sisa waktu terbuang Pembobotan pada kriteria ini dilakukan melalui perhitungan banyaknya rongga waktu terbuang ketika kelas praktikum tersebut dijadwalkan. Rongga waktu yang dimaksud adalah ruang waktu yang tersisa diantara dua buah simpul yang bersangkutan. Sisa waktu yang terbuag dihitung berdasarkan satuan SKS. Jika dua buah simpul yang terhubung dijadwalkan pada hari yang sama, maka sisa SKS dihitung berdasarkan selisih antara jam berakhirnya simpul 1 dengan jam bermulanya simpul 2. Untuk mempermudah dalam memahaminya, perhatikan contoh 2 simpul berikut ini: Simpul 1 = Asenin08:00-09:40 Simpul 2 = Bsenin11:20-12:10 Jika simpul 1 terhubung dengan simpul 2, maka sisa waktu yang terbuang diantara kedua simpul adalah 2 SKS. Karena selisih antara pukul 09:40 dan 11:20 adalah 100 menit yang berarti 2 SKS. Contoh diatas menggambarkan untuk kedua simpul yang memiliki hari yang sama. Sedangkan untuk simpul yang memiliki hari berbeda, maka untuk sisa waktu terbuang dihitung berdasarkan jam awal dari simpul 2. Sisa waktu merupakan selisih antara pukul berawal laboratorium digunakan yaitu pukul 08:00 dan pukul awal simpul 2. Perhatikan contoh kedua simpul berikut: Simpul 1 = Asenin08:00-09:40 Simpul 2 = Bselasa09:40-12:10 Jika simpul 1 terhubung dengan simpul 2, maka sisa waktu yang terbuang diantara kedua simpul adalah 2 SKS. Karena selisih antara pukul 09:40 dan 08:00 adalah 100

IV-28

menit yang berarti 2 SKS. Semakin banyak sisa waktu yang terbuang, maka semakin kecil prioritas state untuk dipilih. Dari pernyataan diatas dapat disimpulkan bahwa semakin banyak sisa waktu yang terbuang, maka bobot akan bernilai besar. Untuk mengimbangi perhitungan bobot dengan kriteria yang sebelumnya, maka untuk perhitungan bobot berdasarkan kriteria ini dihasilkan dari sisa waktu terbuang dikalikan 2. Angka 2 diambil karena untuk menjaga prioritas bobot utuk kriteria ini. Sehingga jika digambarkan secara matematis, berikut adalah rumusnya: Bobot = Sisa waktu * 2 Dari rumus diatas dapat dirancang suatu fungsi untuk menghitung bobot berdasarkan kriteria ini. Fungsi tersebut diberi nama fungsi ”bobot_sisa_waktu” dan dideskripsikan dengan algoritma berikut. Algoritma Fungsi ”bobot_sisa_waktu” 1 2

function bobot_sisa_waktu(state1, state2) if (state1.hari== state2.hari) batas_awal  state1.pukul_akhir

3

batas_akhir  state2.pukul_awal

4 5

end else

6

batas_awal  ”08:00”

7

batas_akhir  state2.pukul_awal

8 9 10

endif jumlah_sisa_waktu  0 while(batas_awal < batas_akhir)

11

batas_awal  batas_awal + 50 minutes

12

jumlah_sisa_waktu  jumlah_sisa_waktu + 1

13

endwhile

14

bobot_sisa_waktu  jumlah_sisa_waktu*2;

15

endfunction

No 2-4

Jika hari pada simpul 1 sama dengan hari pada simpul 2, maka batas awal diisi dengan pukul akhir pada simpul 1, dan batas akhir diisi dengan pukul awal simpul 2.

No 5-7

Jika hari pada simpul 1 berbeda dengan hari pada simpul 2, maka batas awal diisi dengan pukul 08:00, dan batas akhir diisi dengan pukul awal simpul 2.

No 9

Inisialisasi jumlah sisa waktu dengan nilai 0.

IV-29

No 10-13

Proses perhitungan jarak antara batas awal dengan batas akhir, dengan satuan SKS

No 11

Menambahkan batas awal 50 menit setiap perulangan menandakan jumlah sisa waktu dihitung setiap 50 menit atau 1 SKS.

No 12

Menghitung jumlah sisa waktu dengan menambahkan variabel jumlah sisa waktu dengan nilai 1 untuk setiap perulangan

b. Kelas yang berulang Kelas yang berulang adalah ketika dua simpul yang terhubung memiliki kelas praktikum yang sama meskipun memiliki waktu yang berbeda. Jika terdapat sisi atau edge yang menghubungkan kelas yang sama, maka sisi tersebut akan menjadi prioritas untuk tidak dipilih. Karena solusi yang akan dihasilkan tidak akan optimal ketika dalam satu jalur terdapat kelas praktikum yang sama. Hal itu menandakan kelas yang sama dijadwalkan pada ruang yang sama, dan berarti mengulangi kelas praktikum yang sudah ditetapkan sebagai solusi pada waktu tertentu. Tentunya hal tersebut dapat membuang slot waktu yang seharusnya dapat diletakkan untuk kelas praktikum yang lain. Untuk itu, jika suatu sisi atau edges menghubungkan dua simpul yang merupakan kelas yang sama, maka sisi tersebut akan diberi bobot 5. Pemilihan angka 5 dipertimbangkan berdasarkan prioritas pada kriteria ini yang juga penting dibandingkan kriteria yang lain, namun nilai bobot tidak boleh diambil terlalu tinggi agar tidak menutupi point kriteria lain. Perhitungan bobot pada kriteria ini dilakukan melalui fungsi ”bobot_kelas_berulang” yang dideskripsikan melalui algoritma berikut: Algoritma Fungsi ”bobot_kelas_berulang” 1

function bobot_kelas_berulang(simpul1, simpul2)

2

if(simpul1.kelas == simpul2.kelas) bobot_kelas_berulang  5

3 4

end else bobot_kelas_berulang  0

5 6 7

No 2-3

endif endfunction

Jika kelas pada simpul 1 sama dengan kelas pada simpul 2, maka nilai bobot adalah 5.

IV-30

No 4-5

Jika kelas pada simpul 1 berbeda dengan kelas pada simpul 2, maka nilai bobot adalah 0.

c. Sudah terjadwal di ruang yang lain Kriteria terakhir adalah ketika pengajar kelas praktikum sudah terjadwal pada jam yang sama di ruangan yang lain, maka state tersebut akan mustahil untuk dipilih. Hal ini ditujukan untuk menghindari bentrokan waktu pengajar pada proses penjadwalan. Bobot ini akan bernilai 100 jika state memiliki pengajar yang sudah terjadwal pada jam yang sama di ruang yang lain. Bobot ini hanya akan dimiliki oleh graf untuk proses pengulangan ruang 2 dan seterusnya. Karena setiap ruangan memiliki prioritas yang sama dan ruang satu menjadi ruang pertama yang akan disusun, maka graf ruang 1 akan menjadi patokan untuk pemberian bobot di ruang berikutnya. Dalam proses pemberian bobot pada proses penjadwalan dilakukan dengan fungsi “bobot_pengajar_bentrok” yang dideskripsikan melalui algoritma berikut: Algoritma Fungsi ”bobot_pengajar_bentrok” 1function bobot_pengajar_bentrok(state1, state2, pengajar_terjadwal){ 2

hasil_uji 1

3

while(state2.pengajar)

4

hari_state state2.pengajar.hari

5

jamstate_awalstate2.pengajar.jam_awal

6

jamstate_akhirstate2.pengajar.jam_akhir

7

i0

8

while (pengajar_terjadwal[state2.pengajar][i])

9

hari_terjadwalpengajar[state2.pengajar][i].hari

10

jam_awal_jadwalpengajar[state2.pengajar][i].jam_awal

11 12 13 14

jam_akhir_jadwalpengajar[state2.pengajar][i].jam_akhir if(hari_state <> hari_terjadwal) hasil_uji hasil_uji*1 End else

15

If(((jamstate_awal >= jam_awal_jadwal)and

16

(jamstate_awal<jam_akhir_jadwal))or

17

((jamstate_akhir>jam_awal_jadwal)and

18

(jamstate_akhir<=jam_akhir_jadwal))or

19

((jamstate_akhi)>=jam_akhir_jadwal)and

20

(jamstate_awal<=jam_awal_jadwal)))

IV-31

21

Hasil_uji hasil_uji*0

22

end else

23

Hasil_uji hasil_uji*1

24

endif

25

endif

26

i i+1

27

endwhile

28

endwhile

29

If(hasil_uji== 1) bobot_pengajar_bentrok  0

30 31

end else bobot_pengajar_bentrok  100

32 33

endif

34

endfunction

No 3-27

Menguji setiap pengajar pada state, apakah waktu yang akan dijadwalkan sudah terjadwal sebelumnya .

No 4-6

Inisialisasi waktu pengajar yang akan dijadwalkan seperti hari, pukul awal, dan pukul akhir.

No 8-27

Memeriksa waktu pengajar yang akan dijadwalkan ke daftar pengajar yang telah terjadwal sebelumnya.

No 15-21

Jika waktu pengajar yang akan dijadwalkan bentrok pada pengajar yang telah dijadwalkan, maka nilai variable hasil uji akan dikalikan dengan 0.

No 22-24

Jika waktu pengajar yang akan dijadwalkan tidak bentrok pada

pengajar yang telah dijadwalkan, maka nilai variable hasil uji akan dikalikan dengan 1. No 29-30

Jika hasil uji bernilai 1 berarti pengajar belum pernah djadwalkan

pada

waktu

yang

sama

sebelumnya

dan

fungsi

akan

mengembalikan nilai 0. No 31-32

Jika hasil uji bernilai 0 berarti pengajar sudah pernah djadwalkan

pada

waktu

yang

sama

sebelumnya

dan

fungsi

akan

mengembalikan nilai 100.

IV-32

Dari 3 kriteria diatas akan ditentukan nilai bobot suatu edge atau sisi yang menghubungkan antara simpul yang dalam hal ini adalah kelas praktikum yang akan dijadwalkan. Dalam penerapannya ketiga fungsi diatas akan diterapkan pada proses utama pemberian bobot pada graph. Algoritma pemberian bobot graph, pada dasarnya sama dengan algoritma pembentukan state menjadi graph. Yang membedakannya adalah ketika pada algoritma pembentukan bobot, ketika menjumpai simpul yang anak kemudian dilakukan penghubungan sisi atau edge. Sedangkan pada algoritma pemberian bobot dilakukan proses perhitungan bobot simpul tersebut. Proses utama pemberian bobot pada graph dideskripsi melalui algoritma berikut: Algoritma proses utama pemberian bobot graph 1

Idx_child  0;

2

J  1;

3

Child  array("s")

4

while (child[idx])

5

i0;

6

temp1;

7 8

while(data_simpul[i]) if(is_canbe_child(child[idx_child],data_simpul[i],data_simpul)

9

a  bobot_sisa_waktu(child[idx_child], data_simpul[i])

10

bbobot_kelas_berulang(child[idx_child],data_simpul[i])

11

cbobot_pengajar_bentrok(child[idx_child],

12

data_simpul[i], jadwal_pengajar) total_bobot  a+b+c

13 14

child[idx_child].set_bobot(data_simpul[i],total_bobot)

15

if (in_array(data_state[i], child))

16

end else child  data_state[i]

17 18

endif

19

temp temp*0;

20

end else temp  temp*1;

21 22

endif

23

ii+1;

24

endwhile

25

if (temp== 1)

26

child[idx_child].set_bobot(data_simpul[i],0)

27

endif

28

Idx_child idx_child+1;

29

endwhile

IV-33

No 3

Inisialisasi nilai pada larik child dengan “s” menandakan simpul dimulai dari “s”.

No 4-30

Proses penelusuran larik child untuk mencari simpul-simpul yang dihubungkan dari child tersebut.

No 7-24

Untuk setiap child dilakukan proses penelusuran data simpul untuk mencari simpul-simpul yang dapat dihubungkan dari child tersebut.

No 9-13

Jika ditemukan simpul yang dapat dihubungkan dari child, maka hitung bobot kedua simpul yang terhubung dengan 3 kriteria diatas.

No 14

Menyimpan jumlah ketiga kriteria bobot pada sisi

yang

menghubungkan kedua simpul. No 15-18

Jika ditemukan simpul yang dapat dihubungkan dari child, maka periksa simpul tersebut apakah sudah pernah berada di larik child atau belum. Jika belum, maka simpan simpul tersebut kedalam larik child.

No 19

Jika ditemukan simpul yang dapat dihubungkan dari child, maka kalikan nilai temp dengan 0. Nilai temp pada saat itu akan menjadi 0.

No 20-21

Jika tidak ditemukan simpul yang dapat dihubungkan dari child, maka kalikan nilai temp dengan 1. Sehingga berapapun nilai temp pada saat itu tidak akan berubah.

No 25-26

Jika nilai temp = 1 berarti pada child tersebut tidak pernah ditemukan simpul yang bisa dihubungkan dari child tersebut. Maka pada saat itu, child terhubung dengan simpul “g” dan berikat nilai bobot 0.

Dari proses pemberian bobot diatas, maka hasil pembobotan diilustrasikan melalui gambar 4.9.

IV-34

Gambar 4.9. Hasil pembobotan graph

Bobot heuristik merupakan bobot setiap simpul yang menggambarkan jarak heuristik atau jarak perkiraan antara simpul n dengan simpul goal atau simpul start. Sehingga pada metode MBDA* yang proses penelusuranya dilakukan secara dua arah, maka bobot heuristik terdiri dari hs(n) dan hg(n). hs(n) adalah biaya perkiraan dari simpul n ke simpul goal, sementara itu hg(n) adalah biaya perkiraan dari simpul n ke simpul start. Bobot heuristik dihitung dengan menggunakan fungsi euclidean distance. Euclidean distance merupakan jarak garis lurus antara dua buah vektor yang didefinisikan dengan suatu koordinat lokasi sumbu x dan y. Meskipun terdapat metode lain yang digunakan untuk menghitung bobot heuristik seperti manhattan IV-35

distance, pemilihan euclidean distance dilakukan karena menghasilkan jarak yang lebih pendek dibandingkan manhattan distance. Penggunaan euclidean distance akan efektif jika digunakan pada garis yang menghubungkan dua buah vektor dimana garis tersebut dapat berposisi kesegala arah, baik vertikal, horizontal, ataupun diagonal. Pada penerapannya dalam penjadwalan, bobot heuristik simpul n ke simpul start (hg(n)) akan diisi dengan nilai 0. Sementara itu, bobot heuristik simpul n ke simpul goal (hs(n)) akan dihitung dengan menggunakan euclidean distance sebagaimana yang telah dijelaskan sebelumnya. Perhitungan euclidean distance untuk nilai hs(n) dilakukan dengan persamaan 2.2. Dalam proses penjadwalan, sumbu x untuk simpul tujuan (x.tujuan) merupakan jumlah sks mata praktikum simpul n. Sementara itu, sumbu x untuk simpul n (x.n) merupakan jumlah slot waktu kelas praktikum pada simpul n. Sumbu y untuk simpul n (y.n) adalah hasil pembagian antara jumlah slot waktu dan jumlah sks mata praktikum simpul n. Sementara itu, untuk nilai y.tujuan akan selalu bernilai 0. Slot waktu kelas praktikum merupakan jumlah kemungkinan kelas praktikum dapat diletakkan sesuai jarak waktu yang dimiliki. Slot waktu tersebut dapat dihitung dari total SKS yang disimpan oleh kelas praktikum berdasarkan irisan waktu antara waktu kosong pengajar dan waktu kosong mahasiswa yang pada suatu kelas, yang dapat disimbolkan dengan:

WaktuKosong(pengajar) ∩ WaktuKosong(mhs) Total SKS tersebut didapat dari pemecahan hasil irisan waktu menjadi beberapa bagian dengan rentang 1SKS untuk setiap bagian. Contohnya adalah kelas A yang memiliki 2 SKS (100 menit). Kelas A tersebut memiliki hasil irisan waktu pengajar dan dosen yaitu Senin 08:00 sampai dengan jam 12:10. Maka total SKS yang disimpan kelas tersebut digambarkan dengan ilustrasi berikut: Senin 08:00-08:50

08:50-09:40

09:40-10:30

10:30-11:20

11:20-12:10

Dari ilustrasi diatas, terlihat bahwa kelas A memiliki total slot waktu sebanyak 5 SKS. Dalam aturannya, semakin sedikit total slot suatu kelas praktikum maka akan semakin tinggi prioritas untuk dipilih. Karena semakin banyak total slot berarti semakin

IV-36

banyak waktu alternatif peletakan kelas praktikum. Dari beberapa pernyataan diatas, dapat kita simpulkan bahwa semakin sedikit total SKS maka semakin tinggi prioritas untuk dipilih. Semakin tinggi prioritas yang dipilih berarti semakin kecil bobot heuristiknya. Dari contoh kelas A diatas, dapat dihitung nilai bobot heuristik kelas A terhadap simpul goal (hs(n)) sebagai berikut:

ℎ

=

,

=

,

= ( .

=

− . ) + ( .

5− 2

= √9 + 6.25

− . )

+ (5/2) − 0

= √15.25

= = = = 3.9

Berikut adalah algoritma untuk menghitung bobot heuristik berdasarkan persamaan diatas: Algoritma fungsi ”bobot_heuristik” 1 2 3 4

function bobot_heuristik(kelas_praktikum) while(waktu_irisan[kelas_praktikum]) batas_awal  waktu_irisan[kelas_praktikum].pukul_awal batas_akhir waktu_irisan[kelas_praktikum].pukul_akhir

5

interval  kelas_praktikum.sks*50;

6

waktu_awal batas_awal;

7

waktu_akhir  waktu_awal+interval;

8

idx_slot=0;

9

while((waktu_awal >= batas_awal) and

10

(waktu_awal <= batas_akhir) and

11

(waktu_akhir >= batas_awal) and

12

(waktu_akhir <= batas_akhir))

13

waktu_awal  waktu_awal + 50minutes

14

waktu_akhir  waktu_akhir + 50minutes

15

if(kk==0)

16

total_slot  total_slot+kelas_praktikum.sks

17

end else

18

total_slot  total_slot+1;

19

endif kk  kk+1;

20 21 22 23 24 25

endwhile endwhile bobot sqrt(sqr(total_slot-kelas_praktikum.sks)+ sqr(total_slot/ kelas_praktikum.sks)) bobot_heuristik  bobot

IV-37

26

endfunction

No 2-22

Proses perhitungan total SKS.

No 3-4

Inisialisasi batas awal dan batas akhir sebagai pembatas pengulangan waktu dalam proses pemecahan bagian SKS.

No 6-7

Inisialisasi waktu awal dan waktu akhir sebagai iterasi dalam proses pemecahan bagian SKS.

No 9-21

Proses pemecahan waktu kelas praktikum menjadi beberapa bagian sesuai batas awal hingga batas akhir. Dan setiap kali pengulangan range waktu selalu berjumlah sesuai SKS kelas praktikum

No 9-12

Proses pemecahan waktu kelas praktikum berlangsung selama waktu awal dan waktu akhir berada diantara batas awal dan batas akhir

No 15-17

Total SKS dihitung berdasarkan jumlah pengulangan. Ketika pengulangan pertama total SKS diawali dengan jumlah sesuai dengan SKS kelas praktikum.

No 17-19

Untuk pengulangan selanjutnya total SKS selalu bertambah satu.

No 23

Perhitungan bobot sesuai rumus diatas Dari proses pemberian bobot heuristik diatas, maka hasil pembobotan untuk kasus

yang telah dideskripsikan sebelumnya dilampirkan melalui tabel 4.12. Tabel 4.12. Hasil perhitungan bobot heuristik No

Kelas Praktikum

Bobot heuristik (hg(n))

1

Kelas 1

2.6

2

Kelas 2

1

3

Kelas 3

1

4

Kelas 4

5.7

5

Kelas 5

7.2

4. Penelusuran jalur terpendek dengan algoritma MBDA* Jalur terpendek pada graph akan menjadi solusi dalam proses penjadwalan. Jalur terpendek ditentukan berdasarkan total bobot jalur yang ditelursuri. Setiap IV-38

jalur terpendek yang ditelusuri merupakan solusi jadwal untuk setiap ruangan yang tersedia pada laboratorium. Setiap simpul yang berstatus sebagai calon solusi terbaik akan dibangkitkan untuk ditelusuri. Seperti yang telah dijelaskan pada landasan teori, bahwasannya algoritma MBDA* pada dasarnya adalah algoritma A* yang disempurnakan atau dimodifikasi. Prinsip utama kerja metode MBDA* adalah menggunakan 2 algoritma A* yang diterapkan secara serentak untuk setiap perulangan. Sehingga pada metode ini penelusuran simpul-simpul pada graph dilakukan secara dua arah, yakni pencarian maju dan pencarian mundur. Pencarian maju dimulai dari simpul ”s”(start), sementara pencarian mundur dimulai dari simpul ”g”(goal). Kedua arah penelusuran ini sama-sama menggunakan metode A*. Pada penerapannya, metode ini memiliki 2 buah larik utama, yaitu OPEN dan CLOSE. OPEN merupakan larik penyimpanan simpul yang akan menguraikan anak-anaknya untuk ditelusuri. Sementara itu CLOSED merupakan larik penyimpanan simpul terbaik sebagai calon solusi jalur terpendek. Sedangkan BestNode merupakan variabel penyimpanan simpul dengan bobot terbaik yang telah terpilih sebagai solusi jalur terpendek. Simpul terbaik dipilih berdasarkan total bobot yang terkecil. Ketika suatu simpul dibangkitkan, maka terdapat tiga kondisi yang akan diperiksa. Ketiga kondisi tersebut tentunya memiliki aksi yang berbeda-beda. Ketiga kondisi tersebut adalah ketika simpul sudah berada di OPEN, ketika simpul sudah berada di CLOSED, dan ketika simpul tidak berada di OPEN ataupun CLOSED. Pada kondisi pertama, yakni ketika simpul sudah pernah berada di OPEN, maka akan dilakukan pemeriksaan apakah perlu dilakukan perubahan parent atau tidak. Perubahan parent perlu dilakukan jika bobot total pada parent baru lebih kecil dari pada bobot total pada parent yang lama. Karena bobot total yang kecil akan menentukan solusi terbaik dalam proses pencarian jalur terpendek. Jika perubahan parent tersebut dilakukan, maka nilai total bobot jalur yang ditelusuri juga diperbaharui sesuai bobot total parent yang baru. Pada kondisi kedua, yaitu ketika simpul sudah berada di CLOSED. Perlu dilakukan pemeriksaan terhadap perubahan parent, seperti pada kondisi pertama. IV-39

Ketika parent perlu dilakukan perubahan, maka total bobot jalur sebelumnya yang pernah tersimpan dalam larik OPEN juga diperbaharui. Pada kondisi ketiga, yaitu ketika simpul tidak berada di OPEN ataupun CLOSED. Pada kondisi ini simpul tersebut akan disimpan kedalam larik OPEN dan disimpan sebagai jalur terbaik. Pada sistem penjadwalan ini, fungsi A* dideskripsikan melalui algoritma berikut: Algoritma fungsi A* 1

function Astar(s,g,nodes){

2

OPEN[0]  s

3

f_OPEN[s]  0

4

CLOSED = array()

5

While((goal== false) and OPEN != null)

6 7

if (OPEN == null) Gagal

8

end else

9

BestNode  OPEN[array_search(min(f_OPEN), f_OPEN)]

10

OPEN  OPEN - BestNode

11

f_OPEN  f_OPEN - f_OPEN[BestNode]

12

array_push(CLOSED, BestNode)

13

if(BestNode== g)

14 15

goal  true end else

16

suksesor  nodes[BestNode].getNeighbours()

17

while(suksesor)

18

if(nodes[BestNode]-> connectsTo(nodes[suksesor]))

19

g[suksesor]g[BestNode]+

20

BestNode.getBobot(nodes[suksesor])

21

if(in_array(suksesor, OPEN))

22

old  suksesor

23

array_push(suksesor,nodes[old])

24

if(g[old]
25

array_pop(old, data_parent)

26

array_push(nodes[BestNode],data_parent)

27

array_push(old, data_parent)

28

g[suksesor]  g[old]

29

f_open[suksesor]  f_open[old]

30

endif

31

end

32

else if(in_array(suksesor, CLOSED))

IV-40

33

old  suksesor

33

array_push(suksesor,nodes[old])

34

f_open[old]f_open[nodes[BestNode]+

35

f_open[suksesor]

36

if(f_open[old]
37

array_pop(old, data_parent)

38

array_push(nodes[BestNode],data_parent)

39

array_push(old,data_parent)

40

f_open[suksesor]  f_open[old]

41

endif

42

end

43

else

44

array_push(suksesor, OPEN)

45

f_open[suksesor]g[suksesor]+(1/2|hs-hg|)

46

endif

47

endif

48

endwhile

49

endif

50

endif

51

endwhile

52

endfunction

No 2

Inisialisasi larik OPEN dengan “s” menandakan penelusuran dimulai dari “s”.

No 3

Inisialisasi larik f_OPEN yang merupakan larik penyimpanan nilai fungsi heuristik total simpul terhadap simpul parent sebelumnya

No 5-50

Lakukan pengulangan sampai goal ditemukan atau sampai tidak ada simpul didalam OPEN.

No 9

Simpul terbaik yang ada diOPEN yang merupakan simpul dengan nilai f_open minimal akan disimpan kedalam larik BestNode.

No 10

Menghapus BestNode dari larik OPEN.

No 11

Menghapus BestNode dari larik f_open.

No 12

Memasukkan BestNode kedalam larik CLOSED.

No 13-14

Goal ditemukan.

No 16

Membangkitkan suksesor simpul BestNode yang merupakan child dari BestNode.

No 17-47

Menelusuri setiap suksesor. IV-41

No 19

Menghitung bobot aktual suksesor terhadap parent sebelumnya dan menyimpannya kedalam larik g.

No 21-31

Aksi yang dilakukan ketika suatu suksesor berada didalam OPEN.

No 22

old merupakan suksesor yang berada diOPEN.

No 23

Menambahkan old sebagai suksesor atau child BestNode.

No 24

Menghitung bobot total simpul old.

No 25-30

Jika fungsi heuristik simpul old lebih kecil dari pada f_open suksesor, maka ubah parent suksesor menjadi BestNode dan ubah nilai f_open simpul suksesor menjadi nilai f_open yang baru.

No 32-42

Aksi yang dilakukan ketika suatu suksesor berada didalam CLOSED.

No 33

old merupakan suksesor yang berada di CLOSED.

No 34

Menambahkan old sebagai suksesor atau child BestNode.

No 35

Menghitung bobot total simpul old.

No 36-41

Jika nilai fungsi heuristik total simpul old lebih kecil dari pada f_open suksesor, maka ubah parent suksesor menjadi BestNode dan ubah nilai f_open simpul suksesor menjadi nilai f_open yang baru.

No 43-46

Jika suksesor tidakberda pada larik OPEN ataupun CLOSED, maka simpal suksesor kedalam OPEN, dan hitung fungsi heuristik suksesor tersebut.

Fungsi ”Astar” diatas akan diterapkan pada algoritma utama pencarian solusi jalur terpendek pada graph yaitu algoritma MBDA. Berbeda halnya dengan algoritma A*, pada algoritma MBDA larik OPEN terdiri dari 2 jenis, yaitu OPENs dan OPENg. OPENs. Larik OPENs merupakan larik yang menyimpan simpul yang akan dibangkitkan anaknya pada pencarian maju atau dari arah simpul ”s”. Sedangkan larik OPENg merupakan larik yang menyimpan simpul yang akan dibangkitkan anaknya pada pencarian mundur dari arah simpul ”g”. Hal itu juga terjadi pada larik CLOSED dan variabel BestNode. Berikut adalah deskripsi algoritma MBDA yang diterapkan untuk pencarian solusi penjadwalan:

IV-42

Algoritma fungsi MBDA 1

function MBDA(s,g,nodes){

2

While(goal== false)

3

BNs, OPENs, CLOSEDs  Astar(s,g,nodes)

4

if(in_array(BNs, CLOSEDg))

5

goal  true

6

v  nodes[BNs]

7

g_terbaik  get_bobot[v]

8

suksesor  nodes[v]->getNeighbours()

9

while(suksesor == CLOSEDg)

10

g_newparentsuksesor.get_bobot(v)

11

if(g_newparent < g_terbaik)

12

g_terbaik  g_newparent

13

new_parent  suksesor

14

endif

15

endwhile

16

fopen_g[v]  g_terbaik

17

data_parent[v] new_parent

18

endif

19

BNg, OPENg, CLOSEDg  Astar(g,s,nodes)

20

if(in_array(BNg, CLOSEDs))

21

goal  true

22

u  nodes[BNg]

23

g_terbaik  get_bobot[u]

24

suksesor  nodes[u].getNeighbours()

25

while(suksesor == CLOSEDs)

26

g_newparentsuksesor.getbobot(u)

27

if(g_newparent < g_terbaik)

28

g_terbaik  g_newparent

29

new_parent  suksesor

30

endif

31

endwhile

32

fopen_s[u]  g_terbaik

33

data_parent[u] new_parent

34

endif

35

endwhile

36

endfunction

No 2-35

Pencarian solusi terus dilakukan hingga goal ditemukan.

No 3

Pencarian Astar arah maju yang dilakukan dari simpul “s”. IV-43

No 4-18

Ketika BNs (BestNode dari arah s) berada pada CLOSEDg artinya goal sudah ditemukan, maka periksa pergantian parent.

No 6

Mengisi variable “v” dengan simpul BNs.

No 7

Mengisi variable g_terbaik dengan total bobot aktual antara simpul “g” dengan simpul “v”.

No 9-15

Menelusuri suksesor dari v yang berada pada CLOSEDg .

No 11-14

Jika bobot actual total melalui suksesor lebih keci dari pada g_terbaik, maka ubah nilai g_terbaik menjadi gnewparent dan jadikan suksesor sebagai parent baru.

No 19

Pencarian Astar arah mundur yang dilakukan dari simpul “g”.

No 20-34

Ketika BNg (BestNode dari arah g) berada pada CLOSEDs artinya goal sudah ditemukan, maka periksa pergantian parent.

No 22

Mengisi variable “u” dengan simpul BNg.

No 23

Mengisi variable g_terbaik dengan total bobot aktual antara simpul “s” dengan simpul “u”.

No 25-31

Menelusuri suksesor dari u yang berada pada CLOSEDs .

No 27-30

Jika total bobot aktual melalui suksesor lebih keci dari pada g_terbaik, maka ubah nilai g_terbaik menjadi g_newparent dan jadikan suksesor sebagai parent baru.

Dari algoritma MBDA diatas terlihat bahwa fungsi ”Astar” digunakan sebanyak dua kali dalam setiap pengulangan. Kedua fungsi tersebut dibedakan menjadi dua jenis, yaitu pencarian maju dan pencarian mundur. Jika algoritma MBDA tersebut diterapkan pada kasus contoh yang telah dirancang sebelumnya, maka berikut adalah langkah penyelesaian solusi jalur terpendek graph. Pada pengulangan pertama, menghasilkan BestNode dari arah ”s” atau BNs=

”s”.

OPENs

=

Kelas5Senin08:50-10:30,

[Kelas1Senin08:00-10:30,

Kelas5Senin08:00-09:40,

Kelas3Senin08:00-10:30,

Kelas4Senin08:00-10:30,

kelas4Senin08:50-11:20]. CLOSEDs = [s]. Karena BNs tidak berada pada CLOSEDg, maka dilanjutkan dengan pencarian mundur. Pencarian mundur menghasilkan

BestNode

dari

arah

”g”

atau

BNg=

”g”.

OPENg

=

IV-44

[Kelas2Selasa10:30-12:10, Kelas5Selasa09:40-11:20, Kelas5Selasa10:30-12:10]. CLOSEDg = [g]. Kerena BNg tidak berada pada CLOSEDs maka penelusuran dilanjutkan

pada

pengulangan

kedua.

Penjelasan

pengulangan

pertama

digambarkan pada gambar 4.10.

Gambar 4.10. Visualisasi pengulangan pertama

Pada pengulangan kedua, menghasilkan BestNode dari arah ”s” atau BNs= ”Kelas3Senin08:00-10:30”.

OPENs

=

[Kelas5Senin08:00-09:40,

Kelas5Senin08:50-10:30,

Kelas4Selasa08:00-10:30,

Kelas1Senin08:00-10:30,

Kelas5Senin08:00-09:40,

Kelas5Senin08:50-10:30,

Kelas4Senin08:00-10:30,

Kelas4Senin08:50-11:20]. CLOSEDs = [s, Kelas3Senin08:00-10:30]. Karena BNs tidak berada pada CLOSEDg, maka dilanjutkan dengan pencarian mundur. Pencarian mundur menghasilkan Kelas2Selasa10:30-12:10.

BestNode dari

OPENg

=

arah ”g” atau BNg= [Kelas5Selasa09:40-11:20,

Kelas5Selasa10:30-12:10, Kelas5Selasa08:00-09:40, Kelas5Selasa08:50-10:30, Kelas4Selasa08:00-10:30]. CLOSEDg = [g, Kelas2Selasa10:30-12:10]. Kerena BNg tidak berada pada CLOSEDs maka penelusuran dilanjutkan pada

IV-45

pengulangan ketiga. Penjelasan pengulangan kedua digambarkan pada gambar 4.11.

Gambar 4.11. Visualisasi pengulangan kedua

Pada pengulangan ketiga, menghasilkan BestNode dari arah ”s” atau BNs= ”Kelas1Senin08:00-10:30”. Seluruh suksesor ”Kelas1Senin08:00-10:30” yakni Kelas5Selasa08:00-09:40,

Kelas5Selasa08:50-10:30,

Kelas4Selasa08:00-10:30

sudah pernah berada di OPENs maka dilakukan pemeriksaan pergantian parent. Untuk

mencapai

suksesor

”Kelas5Selasa08:00-09:40”

melalui

simpul

”Kelas1Senin08:00-10:30” memiliki total bobot yang lebih kecil atau sama dari pada melalui ”Kelas3Senin08:00-10:30”, sehingga tidak perlu merubah parent. Hal tersebut berlaku untuk kedua suksesor yang lainnya. Oleh karena itu, nilai

OPENs

=

[Kelas5Senin08:00-09:40,

Kelas5Senin08:50-10:30,

kelas4Senin08:50-11:20,

Kelas5Selasa08:00-09:40,

Kelas4Senin08:00-10:30, Kelas5Selasa08:50-10:30,

Kelas4Selasa08:00-10:30].

CLOSEDs

=

[s,

Kelas3Senin08:00-10:30, Kelas1Senin08:00-10:30]. Karena BNs tidak berada pada CLOSEDg, maka dilanjutkan dengan pencarian mundur. Pencarian mundur menghasilkan BestNode dari arah ”g” atau BNg= ” Kelas4Selasa08:00-10:30”.

OPENg

=

[Kelas5Selasa10:30-12:10,

Kelas5Selasa08:00-09:40, Kelas5Selasa08:50-10:30, Kelas5Selasa09:40-11:20, IV-46

Kelas1Senin08:00-10:30,

Kelas5Senin08:50-10:30,

Kelas4Senin09:40-12:10,

Kelas3Senin08:00-10:30,

Kelas4Senin08:00-10:30,

Kelas4Senin08:50-11:20].

CLOSEDg = [g, Kelas2Selasa10:30-12:10, Kelas4Selasa08:00-10:30]. Kerena BNg tidak berada pada CLOSEDs maka penelusuran dilanjutkan pada pengulangan empat. Penjelasan pengulangan ketiga digambarkan pada gambar 4.12.

Gambar 4.12. Visualisasi pengulangan ketiga

Pada pengulangan keempat, menghasilkan BestNode dari arah ”s” atau BNs= ”Kelas4Senin08:00-10:30”. Seluruh suksesor ”Kelas4Senin08:00-10:30” yakni Kelas5Selasa08:00-09:40, Kelas5Selasa08:50-10:30, Kelas4Selasa08:0010:30 sudah pernah berada di OPENs maka dilakukan pemeriksaan pergantian parent. Untuk mencapai suksesor ”Kelas5Selasa08:00-09:40” melalui parent lama yaitu simpul ”Kelas1Senin08:00-10:30” memiliki total bobot yang lebih kecil atau sama dari pada melalui ”Kelas4Senin08:00-10:30”, sehingga tidak perlu merubah parent. Hal tersebut berlaku untuk kedua suksesor yang lainnya. Oleh karena itu IV-47

nilai

OPENs

=

[Kelas5Senin08:00-09:40,

Kelas4Senin08:50-11:20,

Kelas5Selasa08:00-09:40,

Kelas4Selasa08:00-10:30].

CLOSEDs

=

[s,

Kelas5Senin08:50-10:30, Kelas5Selasa08:50-10:30, Kelas3Senin08:00-10:30,

Kelas1Senin08:00-10:30, Kelas4Senin08:00-10:30]. Karena BNs tidak berada pada CLOSEDg, maka dilanjutkan dengan pencarian mundur. Pencarian mundur menghasilkan BestNode dari arah ”g” atau BNg= ”Kelas3Senin08:00-10:30”. Suksesor ”Kelas3Senin08:00-10:30” yakni simpul S belum pernah berada di OPENg ataupun CLOSEDg, maka dihasilkan OPENg = [Kelas5Selasa10:30-12:10, Kelas5Selasa08:00-09:40, Kelas5Selasa08:50-10:30, Kelas5Selasa09:40-11:20,

Kelas1Senin08:00-10:30,

Kelas5Senin08:50-10:30,

Kelas4Senin09:40-12:10, S, Kelas4Senin08:00-10:30, Kelas4Senin08:50-11:20]. CLOSEDg=

[g,

Kelas2Selasa10:30-12:10,

Kelas4Selasa08:00-10:30,

Kelas3Senin08:00-10:30]. Kerena BNg sudah berada pada CLOSEDs maka penelusuran dihentikan. Penjelasan pengulangan keempat diilustrasikan pada gambar 4.13.

Gambar 4.13. Visualisasi pengulangan keempat

IV-48

Dari proses MBDA diatas didapat solusi jalur terpendek adalah Kelas3Senin08:00-10:30,

Kelas4Selasa08:00-10:30,

Kelas2Selasa10:30-12:10.

Ketiga simpul diatas merupakan solusi jadwal pada ruang pertama dari proses penjadwalan. Sekaligus ketiga simpul tersebut merupakan hasil akhir dari tahap keempat dalam proses penjadwalan. 5. Membersihkan data simpul dari simpul yang sudah terjadwal Ketika solusi untuk ruangan pertama didapatkan, maka pada saat itu graph harus bebas dari simpul yang kelas praktikumnya sudah terjadwal. Hal ini bertujuan untuk meminimasir memory penyimpanan data graph sekaligus untuk mempersingkat pencarian solusi untuk ruangan selanjutnya. Karena, ketika suatu kelas praktikum sudah terjadwal disuatu ruangan, maka tidak mungkin kelas praktikum tersebut dijadwalkan kembali pada ruangan yang lain. Hasil dari pembersihan graph ini akan digunakan sebagai graph pada pengulangan selanjutnya. Sehingga dari proses ini untuk kasus diatas, akan menghasilkan data simpul sebagai berikut: Simpul = (Kelas1Senin08:00-10:30, Kelas5Senin08:00-09:40, Kelas5Senin08:50-10:30, Kelas5Selasa08:00-09:40, Kelas5Selasa08:50-10:30,Kelas5Selasa09:40-11:20, Kelas5Selasa10:30-12:10 ) 6. Mengulangi langkah 1-5 sebagai solusi akhir jadwal Pengulangan kelima langkah diatas dilakukan sebanyak jumlah ruangan pada laboratorium. Karena setiap pengulangan akan menghasilkan solusi jadwal untuk satu ruangan. Sebelum memasuki pengulangan kedua dan seterusnya, data pengajar terjadwal harus disimpan terlebih dahulu. Data pengajar terjadwal merupakan data waktu bagi pengajar yang telah terjadwal pada pengulangan pertama untuk satu ruangan. Dari pengulangan pertama pada kasus diatas, maka didapatkan data pengajar terjadwal yang dilampirkan pada tabel 4.13.

IV-49

Tabel 4.13. Data pengajar yang telah terjadwal No

Pengajar

Kelas Praktikum

Waktu yang telah terjadwal

1

D

Kelas 3

Senin(08:00-10:30)

2

B

Kelas 2

Selasa(10:30-12:10)

3

C

Kelas 2

Selasa(10:30-12:10)

4

D

Kelas 4

Selasa(08:00-10:30)

Pada ruangan berikutnya pengajar yang sama tidak boleh diletakkan pada waktu yang sama, hal ini bertujuan untuk menghindari bentrokan antar pengajar. Oleh karena itu, pada pengulangan kedua dan seterusnya berlaku perhitungan bobot dengan kategori keempat yaitu ”sudah terjadwal di ruang yang lain”. Sehingga untuk pengulangan kedua, graph berbobot yang berlaku divisualisasikan pada gambar 4.14.

Gambar 4.14. Visualisasi graph berbobot untuk pengulangan kedua

Dari seluruh proses penjadwalan diatas, untuk kasus yang telah dideskripsikan sebelumnya. Maka hasil akhir proses penjadwalan dilampirkan pada tabel 4.14. IV-50

Tabel 4.14. Hasil akhir proses penjadwalan Hari

Waktu

Senin

Selasa

4.2.

Ruang 1 Kelas Praktikum

Ruang 2 Pengajar

Kelas Praktikum

08:00-08:50

Kelas3

08:50-09:40

Kelas3

09:40-10:30

Kelas3

Kelas1

08:00-08:50

Kelas4

Kelas5

08:50-09:40

Kelas4

09:40-10:30

Kelas4

10:30-11:20

Kelas2

11:20-12:10

Kelas2

Pengajar

Kelas1 D

D

Kelas1

Kelas5

A

E

B, C

Perancangan Pada tahapan ini dilakukan perancangan terhadap sistem berdasarkan

analisa permasalahan yang telah dilakukan sebelumnya.

4.2.1. Perancangan Basis Data Berikut merupakan rancangan basis data untuk melengkapi komponen data sistem. Data setiap tabel pada database yang berupa kolom(field), type kolom, panjang data, serta keterangan field. Untuk keterangan field Primary key berarti field tersebut sebagai kode unik pada tabel tersebut. Dan kode unik berarti setiap baris tidak dibenarkan memiliki nilai yang sama. Sedangkan Foreign Key berarti field tersebut sebagai kandidat yang mewakili suatu tabel terhadap tabel lain. Artinya, kedua tabel tersebut memiliki relasi.

4.2.1.1.Tabel dosen Nama Tabel

: data_dosen

Deskripsi isi : Berisi data dosen. Volume

:-

IV-51

Tabel 4.15. Rincian field tabel dosen pada database Field

Type

Length

Keterangan

#nip

Varchar

21

Primary Key

Nama

Varchar

40

Nama dosen

Alamat

Varchar

50

Alamat dosen

no_hp

Varchar

12

Nomor HP dosen

4.2.1.2. Tabel hak akses Nama Tabel

: hak_akses

Deskripsi isi : Berisi data hak akses pengguna sistem. Volume

:-

Tabel 4.16. Rincian field tabel hak_akses pada database Field

Type

Length

Keterangan

#id_user

Integer

3

Primary Key, auto increament

##nip

Varchar

21

Foreign Key dari tabel dosen, asisten, atau pegawai labor

Username

Varchar

35

Username untuk masuk sistem

Password

Varchar

35

Kata kunci untuk masuk sistem

Jenis

Varchar

7

Jenis

pengguna

sistem

(kalab,laboran, dosen, atau asisten)

4.2.1.3. Tabel asisten Nama Tabel

: data_asisten

Deskripsi isi : Berisi data master seluruh asisten dosen. Volume

:-

Tabel 4.17. Rincian field tabel asisten pada database Field

Type

Length

Keterangan

#nim

Varchar

11

Primary Key

Nama

Varchar

40

Nama asisten

Alamat

Varchar

50

Alamat asisten

no_hp

Varchar

12

Nomor HP asisten

IV-52

4.2.1.4. Tabel pegawai laboratorium Nama Tabel

: data_pegawai_labor

Deskripsi isi : Berisi data master pegawai laboratorium. Volume

:-

Tabel 4.18. Rincian field tabel pegawai laboratorium pada database Field

Type

Length

Keterangan

#nik

Varchar

21

Primary Key

Nama

Varchar

40

Nama pegawai laboratorium

Alamat

Varchar

50

Alamat pegawai laboratorium

no_hp

Varchar

12

Nomor HP pegawai laboratorium

4.2.1.5. Tabel kelas praktikum Nama Tabel

: kls_praktikum

Deskripsi isi : Berisi data kelas praktikum yang akan menggunakan laboratorium. Volume

:-

Tabel 4.19. Rincian field tabel kelas praktikum pada database Field

Type

Length

Keterangan

#id_kelas

Varchar

8

Primary Key

##nip

Varchar

21

Foreign key dari tabel data dosen

##kode_matapraktikum

Varchar

5

Foreign key dari tabel mata praktikum

Kelas

Varchar

30

Nama kelas praktikum

4.2.1.6. Tabel waktu kosong dosen Nama Tabel

: waktu_kosong_dosen

Deskripsi isi : Berisi data waktu kosong yang dimiliki dosen dalam satu minggu. Volume

:-

Tabel 4.20. Rincian field tabel waktu kosong dosen pada database Field

Type

Length

Keterangan

#kode_pengajuan

Varchar

8

Primary Key

##nip

Varchar

25

Foreign key dari tabel data dosen

Hari

Varchar

8

Hari waktu kosong dosen

Pukul_awal

Varchar

5

Pukul awal waktu kosong dosen

Pukul_akhir

Varchar

5

Pukul akhir waktu kosong dosen

IV-53

4.2.1.7. Tabel waktu kosong mahasiswa Nama Tabel

: waktu_kosong_mahasiswa

Deskripsi isi : Berisi data waktu kosong mahasiswa kelas praktikum Volume

:-

Tabel 4.21. Rincian field tabel waktu kosong mahasiswa pada database Field

Type

Length

Keterangan

#kode_waktu

Varchar

8

Primary Key

##id_kelas

Varchar

8

Foreign key dari kelas praktikum

Hari

Varchar

8

Hari waktu kosong mahasiswa

Pukul_awal

Varchar

5

Pukul awal waktu kosong mahasiswa

Pukul_akhir

Varchar

5

Pukul akhir waktu kosong mahasiswa

4.2.1.8. Tabel waktu kosong asisten Nama Tabel

: waktu_kosong_asisten

Deskripsi isi : Berisi data waktu kosong yang dimiliki asisten dalam satu minggu. Volume

:-

Tabel 4.22. Rincian field tabel waktu kosong asisten pada database Field

Type

Length

Keterangan

#kode_pengajuan

Varchar

8

Primary Key

##nim

Varchar

11

Foreign key dari data asisten

Hari

Varchar

8

Hari waktu kosong asisten

Pukul_awal

Varchar

5

Pukul awal waktu kosong asisten

Pukul_akhir

Varchar

5

Pukul akhir waktu kosong asisten

4.2.1.9. Tabel asisten dosen Nama Tabel

: asisten_dosen

Deskripsi isi : Berisi data asisten untuk setiap dosen. Volume

:-

Tabel 4.23. Rincian field tabel asisten dosen pada database Field

Type

Length

Keterangan

##nip

Varchar

21

Foreign key dari data dosen

##nim

Varchar

11

Foreign key dari data asisten

IV-54

4.2.1.10.

Tabel pengajar

Nama Tabel

: pengajar

Deskripsi isi : Berisi data pengajar setiap kelas praktikum. Volume

:-

Tabel 4.24. Rincian field tabel pengajar pada database Field

Type

Length

Keterangan

##id_kelas

Varchar

8

Foreign key dari data kelas praktikum

##pengajar

Varchar

21

Foreign key dari data asisten atau dosen.

4.2.1.11.

Tabel data mata praktikum

Nama Tabel

: data_matapraktikum

Deskripsi isi : Berisi master data mata praktikum. Volume

:-

Tabel 4.25. Rincian field tabel data mata praktikum pada database Field

Type

Length

Keterangan

#kode_matapraktikum

Varchar

5

Primary Key

mata_praktikum

Varchar

25

Nama mata praktikum

Sks

Int

1

Jumlah SKS mata praktikum yang dapat diisi dengan bilangan 2 atau 3

4.2.1.12.

Tabel jadwal

Nama Tabel

: jadwal

Deskripsi isi : Berisi data hasil akhir proses penjadwalan. Volume

:-

Tabel 4.26. Rincian field tabel Jadwal pada database Field

Type

Length

Keterangan

##id_ruang

Varchar

5

Foreign key dari tabel ruang labor

##id_kelas

Varchar

8

Foreign Key dari tabel kls_praktikum

Hari

Varchar

8

Hari jadwal

Jam

Varchar

11

Pukul awal dan pukul berakhirnya kelas praktikum

IV-55

4.2.1.13.

Tabel Ruangan Laboratorium

Nama Tabel

: data_ruang_labor

Deskripsi isi : Berisi data ruangan pada laboratorium. Volume

:-

Tabel 4.27. Rincian field tabel ruangan laboratorium pada database Field

Type

Length

Keterangan

#id_ruang

Varchar

5

Primary key

Ruang

Varchar

25

Nama ruangan

Dari detail tabel database diatas, dapat diterapkan pada Aplikasi Database Management System. Yang mana pada penelitian ini digunakan MySQL.

4.2.2. Perancangan Struktur Menu Perancangan struktur menu digambarkan pada gambar 4.15.

Gambar 4.15. Perancangan Struktur Menu Dari struktur menu diatas, untuk menu “Pengolahan Data Master” dan seluruh submenunya hanya dapat diakses oleh kepala laboratorium. Sementara itu, IV-56

untuk menu “Registrasi”, hanya submenu “Pemberian Hak Akses” yang diakses oleh seorang kepala laboraotium. Submenu yang lainnya diakses oleh dosen. Untuk menu “Input Waktu Kosong”, submenu “Waktu Kosong Dosen” dan “Waktu Kosong Mahasiswa” dapat diakses oleh dosen. Sementara itu submenu “Waktu Kosong Asisten” dapat diakses oleh asisten. Menu yang terakhir adalah “Penjadwalan”. Pada menu ini terdapat submenu “Penyusunan Jadwal”

yang

dapat diakses oleh seorang Kepala Laboratorium dan submenu “Lihat Jadwal” yang diakses oleh semua pengguna.

4.2.3. Perancangan Antar Muka (Interface) Berikut adalah rancangan antar muka (interface) dari sistem yang akan dibangun. 4.2.3.1. Pengolahan Data Master 1. Data Dosen

Gambar 4.16. Data master dosen Untuk halaman data master dosen, sistem juga menyediakan menu “tambah data” yang digunakan kepala laboratorium untuk menambah data dosen melalui form pengisisan. Pada menu ini data dapat diinputkan secara satu persatu. Kemudian pada halaman ini juga terdapat menu “Import Data” yang digunakan IV-57

untuk menginputkan data dosen menggunakan file excel. Pada layanan ini daya dapat diinputkan dalam jumlah yang banyak sekaligus. Data dosen juga dapat diubah atau dihapus karena pada setiap baris terdapat menu layanan “Ubah” dan “Hapus”.

2. Data Matapraktikum

Gambar 4.17. Data master matapraktikum Berbeda halnya dengan data master dosen, halaman data master matapratikum hanya menyediakan menu “tambah data” yang digunakan kepala laboratorium untuk menambah data mata praktikum melalui form pengisian. Hal ini di rancang karena untuk penambahan mata praktikum diasumsikan dalam jumlah yang sedikit.

IV-58

3. Data Asisten

Gambar 4.18. Master data asisten Untuk halaman data master asisten, sistem menyediakan menu “tambah data” yang digunakan oleh kepala laboratorium untuk menambah data asisten melalui form pengisian. Dan “import data” yang digunakan untuk menginputkan data asisten menggunakan file excel. Pada tabel “data asisten” sistem akan menampilkan seluruh data asisten yang tersimpan pada database. Berikut ini akan di tampilkan rancangan interface untuk halaman “tambah data”. Tambah data

Gambar 4.19. Tambah data master asisten IV-59

Pada saat tombol “simpan” di tekan, sistem akan menyimpan data asisten. Sebelumnya sistem akan memvalidasi Nomor induk Mahasiswa (NIM) terlebih dahulu. Jika NIM sudah pernah disimpan, maka sistem akan menampilkan pesan “NIM sudah ada”. Jika NIM belum tersimpan di database, maka sistem akan menyimpan data tersebut.

4. Data Ruang Laboratorium

Gambar 4.20. Master data ruang laboratorium Untuk halaman data master ruang laboratorium, sistem menyediakan menu “tambah data” yang digunakan oleh kepala laboratorium untuk menambah data ruang laboratorium. Berikut ini akan di tampilkan rancangan interface untuk halaman “tambah data”. Tambah data

Gambar 4.21. Tambah data master ruang laboratorium IV-60

5. Data Pegawai Laboratorium

Gambar 4.22. Master data pegawai laboratorium Untuk halaman data master pegawai laboratorium, sistem menyediakan menu “tambah data” yang digunakan oleh kepala laboratorium untuk menambah data pegawai laboratorium. Berikut ini akan di tampilkan rancangan interface untuk halaman “tambah data”. Tambah data

Gambar 4.23. Tambah data master pegawai laboratorium IV-61

4.2.3.2. Registrasi 1. Pemberian Hak Akses

Gambar 4.24. Pemberian hak akses Untuk halaman pemberian hak akses seorang kepala labor harus memilih data master pengguna yang akan ditampilkan terlebih dahulu. Kemudian, memilih pengguna yang akan diberikan hak akses. Setelah itu, kalab mengisi form pengisian yang lain seperti username dan password yang akan digunakan ketika pengguna login, serta jenis user untuk memberikan jenis hak akses yang diterima oleh pengguna. Kemudian kalab menekan tombol “simpan” dan sistem akan memvalidasi apakah data pengguna sudah pernah didaftarkan atau belum. Jika belum maka data akan disimpan, jika tidak sistem akan memberikan pemberitahuan dan data tidak disimpan. IV-62

2. Registrasi Asisten Dosen

Gambar 4.25. Registrasi asisten dosen Untuk halaman ini seorang dosen harus memilih asisten yang akan diregistrasikan sebagai asistennya. Kemudian dosen menekan tombol “tambah” dan data akan disimpan.

3. Registrasi Kelas Praktikum

Gambar 4.26. Registrasi kelas IV-63

Selain merubah dan menghapus kelas yang sudah ada, seorang dosen dapat menambah kelas pada halaman kelas praktikum, merubah data, serta mendaftarkan pengajar pada kelas tersebut. Untuk menambah data dapat dilakukan melalui menu “tambah data”.

Tambah data

Gambar 4.27. Tambah data kelas Untuk penambahan data kelas praktikum yang diampu oleh dosen yang sedang login, dosen cukup mengisi form pengisian dan menekan tombol “simpan”. Untuk pengisian mata praktikum, sistem akan memberikan pilihan sesuai dengan data mata praktikum yang tersimpan di database. Untuk merubah data pegajar kelas praktikum, dosen dapat

menekan

tombol “ubah” pada kolom pengajar. Setelah itu, maka interface halaman yang akan ditampilkan sistem adalah sebagai berikut:

IV-64

Ubah Pengajar

Gambar 4.28. Menambah pengajar pada kelas praktikum

4.2.3.3. Input Waktu Kosong 1. Waktu Kosong Dosen

Gambar 4.29. Waktu kosong yang dimiliki seorang dosen Untuk halaman waktu kosong dosen, sistem menyediakan menu “tambah data” yang digunakan oleh dosen untuk menambahkan waktu kosong yang IV-65

dimilikinya dalam waktu satu minggu. Berikut ini akan di tampilkan rancangan interface untuk halaman “tambah data”. Tambah data

Gambar 4.30. Tambah data waktu kosong dosen

2. Waktu Kosong Mahasiswa

Gambar 4.31. Waktu kosong yang dimiliki mahasiswa suatu kelas Untuk halaman waktu kosong mahasiswa, sistem menyediakan menu “tambah data” yang digunakan oleh dosen untuk menambahkan waktu kosong yang dimiliki oleh mahasiswa suatu kelas praktikum dalam waktu satu minggu. Berikut ini akan di tampilkan rancangan interface untuk halaman “tambah data”. IV-66

Tambah data

Gambar 4.32. Tambah data waktu kosong mahasiswa kelas praktikum

3. Waktu Kosong Asisten

Gambar 4.33. Waktu kosong yang dimiliki asisten dosen Untuk halaman waktu kosong asisten, sistem menyediakan menu “tambah data” yang digunakan oleh asisten dosen untuk menambahkan waktu kosong yang dimilikinya dalam waktu satu minggu. Berikut ini akan di tampilkan rancangan interface untuk halaman “tambah data”. IV-67

Tambah data

Gambar 4.34. Tambah data waktu kosong asisten dosen 4.2.3.4. Penjadwalan 1. Penjadwalan

Gambar 4.35. Penjadwalan Dalam melakukan proses penjadwalan, seorang kepala laboratorium cukup menekan tombol “proses”, dan sistem akan menyusun jadwal dengan “metode MBDA*”. Dan parameter yang terlibat dalam penyusunan tersebut adalah waktu kosong pengajar dan kelas praktikum yang diregistrasikan oleh dosen. IV-68

2. Lihat Jadwal

Gambar 4.36. Interface menu “lihat jadwal”

4.2.4. Perancangan Procedural Berikut ini merupakan pseudocode dari algoritma MBDA*: function Astar (input s: Simpul start, g: Simpul goal, nodes: Himpunan simpul) { Masukan: simpul start, simpul goal, dan semua simpul pada graf Keluaran: himpunan solusi hasil jalur terpendek graf }

Deklarasi OPEN

: Himpunan simpul yang akan dibangkitkan suksesor(anaknya)

f_OPEN

: Himpunan total bobot dari simpul s hingga simpul OPEN.

CLOSED

: Himpunan simpul yang terpilih sebagai jalur terpendek

BestNode

: Simpul yang terpilih sebagai simpul yang terbaik

IV-69

Algoritma: OPEN[0]  s f_OPEN[s]  0 While((goal== false) and OPEN != null) if (OPEN == null) Gagal end else BestNode  OPEN[array_search(min(f_OPEN), f_OPEN)] OPEN  OPEN - BestNode f_OPEN  f_OPEN - f_OPEN[BestNode] array_push(CLOSED, BestNode) if(BestNode== g) goal  true end else suksesor  nodes[BestNode].getNeighbours() while(suksesor) if(nodes[BestNode]  connectsTo(nodes[suksesor])) f_suksesor  nodes[BestNode].getBobot(nodes[suksesor]) if(in_array(suksesor, OPEN)) old  suksesor array_push(suksesor,nodes[old])

f_oldf_open[nodes[BestNode]+f_suksesor[suksesor] if(f_old
old  suksesor array_push(suksesor,nodes[old])

f_oldf_open[nodes[BestNode]+f_suksesor[suksesor] if(f_old
function MBDA (input s: Simpul start, g: Simpul goal, nodes: Himpunan simpul) { Masukan: simpul start, simpul goal, dan semua simpul pada graf Keluaran: himpunan solusi hasil jalur terpendek graf } Deklarasi OPENs

: Himpunan simpul yang akan dibangkitkan anaknya dari simpul s

f_OPENs

: Himpunan total bobot dari simpul s hingga simpul OPEN.

CLOSEDs

: Himpunan simpul yang terpilih sebagai jalur terpendek dari simpul s

BNs

: Simpul yang terpilih sebagai simpul terbaik dari simpul s IV-71

OPENg

: Himpunan simpul yang akan dibangkitkan anaknya dari simpul g

f_OPENg

: Himpunan total bobot dari simpul g hingga simpul OPEN.

CLOSEDg

: Himpunan simpul yang terpilih sebagai jalur terpendek dari simpul g

BNg

: Simpul yang terpilih sebagai simpul terbaik dari simpul g

Algoritma: While(goal== false) BNs, OPENs, CLOSEDs  Astar(s,g,nodes) if(in_array(BNs, CLOSEDg)) goal  true v  nodes[BNs] b_terbaik  fopen_g[v] suksesor  nodes[v].getNeighbours() while(suksesor == CLOSEDg)

fnewparentfopen_g[suksesor]+suksesor.getbobot(v) if(fnewparent < b_terbaik) b_terbaik  fnewparent new_parent  suksesor endif endwhile fopen_g[v]  b_terbaik data_parent[v] new_parent endif BNg, OPENg, CLOSEDg  Astar(g,s,nodes) if(in_array(BNg, CLOSEDs)) goal  true u  nodes[BNg] b_terbaik  fopen_s[u] IV-72

suksesor  nodes[u].getNeighbours() while(suksesor == CLOSEDs)

fnewparentfopen_s[suksesor]+suksesor.getbobot(u) if(fnewparent < b_terbaik) b_terbaik  fnewparent new_parent  suksesor endif endwhile fopen_s[u]  b_terbaik data_parent[u] new_parent endif endwhile

IV-73