plagiat merupakan tindakan tidak terpuji - core.ac.uk fileperusahaan salah satunya adalah manager...

i

SISTEM PENJADWALAN KARYAWAN PARUH WAKTU

DENGAN ALGORITMA GENETIKA

(Studi Kasus : Kedai 24 Jam)

SKRIPSI

Diajukan untuk Memenuhi Salah Satu Syarat

Memperoleh Gelar Sarjana Komputer (S.Kom)

Program Studi Teknik Informatika

Disusun oleh :

MARIA KARMELIA FAJAR LESTARI

115314067

PROGRAM STUDI TEKNIK INFORMATIKA

JURUSAN TEKNIK INFORMATIKA

FAKULTAS SAINS DAN TEKNOLOGI

UNIVERSITAS SANATA DHARMA

YOGYAKARTA

2015

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJIPLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

ii

PART-TIME EMPLOYEE SCHEDULING SYSTEM

WITH GENETIC ALGORITHM

Case Study at Kedai 24 Jam

Presented as Partial Fulfillment of the Requirements

To Obtain the Sarjana Komputer (S.Kom) Degree

In Informatics Engineering

Present by :

MARIA KARMELIA FAJAR LESTARI

115314067

INFORMATION ENGINEERING STUDY PROGRAM

DEPARTMENT OF INFORMATION ENGINEERING

FACULTY OF SCIENCE AND TECNOLOGY

SANATA DHARMA UNIVERSITY

YOGYAKARTA

2015


iii

SKRIPSI

SISTEM PENJADWALAN KARYAWAN PARUH WAKTU

DENGAN ALGORITMA GENETIKA

(Studi Kasus : Kedai 24 Jam)

Disusun Oleh :

Maria Karmelia Fajar Lestari

NIM : 115314067

Telah dipertahankan di depan Panitia Penguji dan

Pada tanggal 24 November 2015

Dan dinyatakan memenuhi syarat

Susunan Panitia Penguji :

Ketua : P.H. Prima Rosa, S.Si., M.Kom. ……………...

Sekretaris : Agnes Maria Polina, S.Kom., M.Sc. ………………

Anggota : Drs. Haris Sriwindono, M.Kom. ………………

Yogyakarta, Desember 2015

Fakultas Sains dan Teknologi


iv


v


vi


vii

HALAMAN PERSEMBAHAN

Nikmati dan berhati-hatilah dalam proses, karena proses jauh lebih berharga

daripada hasil

Karya ini saya persembahkan teristimewa kepada :

Tuhan Yesus,

yang selalu melimpahkan berkat dan rahmat karunia-Nya

Dosen & Karyawan USD,

yang selalu memberi bantuan dan bimbingan dalam proses

Keluarga & Sahabat,

yang selalu memberi doa, perhatian, semangat dan motivasi


viii

ABSTRAK

Penjadwalan karyawan merupakan masalah umum yang dihadapi manager dalam sebuah

perusahaan salah satunya adalah manager kedai 24 jam, proses penjadwalan karyawan paruh

waktu di kedai 24 jam masih dilakukan secara manual dan belum menggunakan sistem yang

mendukung proses penjadwalan tersebut. Oleh karena itu Sistem Penjadwalan Karyawan Paruh

Waktu dibuat untuk membantu manager dalam proses pembuatan jadwal karyawan paruh waktu.

Penjadwalan karyawam paruh waktu ini terkait dengan jumlah hari, jumlah shift per hari,

jumlah shift karyawan dalam satu bulan, kualitas kerja karyawan, jadwal sebelumnya dan

permintaan jadwal karyawan paruh waktu yaitu permohonan jadwal shift karyawan paruh waktu

sebelum jadwal disusun. Hasil yang diharapkan adalah jadwal karyawan yang sesuai dengan

aturan-aturan yang ditetapkan dengan proses yang lebih cepat dibandingkan proses penjadwalan

secara manual.

Persoalan penjadwalan karyawan paruh waktu ini diselesaikan dengan algoritma

Genetika yaitu algoritma yang mempunyai fungsi untuk mendapatkan suatu nilai solusi optimal

terhadap suatu permasalahan yang mempunyai banyak kemungkinan solusi. Dari beberapa aspek

yang ada yaitu jumlah hari, jumlah karyawan dan jumlah shift digunakan untuk membentuk

model kromosom, panjang kromosom diperoleh dari hasil kali jumlah hari yang akan

dijadwalkan dan jumlah shift dalam satu hari, kemudian jumlah karyawan akan menempati

setiap gen dalam kromosom sebagai nilai dari gen (allele). Aspek yang lain yaitu jumlah shift

karyawan dalam satu bulan, kualitas kerja karyawan, jadwal sebelumnya dan permintaan jadwal

karyawan paruh waktu digunakan untuk membuat aturan-aturan penjadwalan yang nantinya

digunakan untuk mencari nilai fitness tiap kromosom.

Proses algoritma Genetika dimulai dengan membangkitkan 10 kromosom secara random,

kemudian dicari nilai fitness untuk setiap kromosom sesuai aturan-aturan yang ditetapkan

sebelumnya. Selanjutnya kromosom-kromosom diseleksi dengan metode seleksi roda roulette

untuk menentukan 1 atau 2 kromosom yang akan melakukan proses reproduksi, yaitu mutasi dan

perkawinan silang/crossover. Proses mutasi melibatkan 1 kromosom dengan probabilitas mutasi

0% - 5% untuk satu kali proses penjadwalan. Proses crossover melibatkan 2 kromosom dengan

jenis crossover 2 titik atau crossover 4 titik. Kedua proses reproduksi ini akan menghasilkan

offspring atau kromosom baru hasil reproduksi, jika offspring yang dihasilkan ini lebih baik atau

nilai fitness-nya lebih sedikit dari kromosom yang ada dalam populasi, maka posisi kromosom

dalam populasi akan digantikan dengan offspring, proses seperti ini yang dinamakan update

kromosom.

Proses algoritma genetika ini akan berlangsung sebanyak jumlah iterasi yang ditentukan.

Proses ini akan berhenti jika iterasi sudah dilakukan sebanyak iterasi yang telah ditentukan

sebelumnya atau ditemukan nilai fitness kromosom = 0 (tidak terjadi pelanggaran pada aturan-

aturan yang ditentukan). Terakhir satu kromosom terpilih menjadi hasil akhir yang mewakili

jadwal karyawan paruh waktu.


ix

ABSTRACT

Employee scheduling is a common problem faced by a company management, including

“Kedai 24 jam” management, most of part-time employee scheduling in “Kedai 24 jam” are

done manually and not using computerized system yet. Therefore Part Time Employee

Scheduling System is designed to help manager handling part-time employee scheduling process.

Part-time employee scheduling is related to number of working days, number of daily

shift, number of employees’ shift monthly, employees’ performance, previous schedule, and also

request made by employees prior to scheduling process. The expected result is employee

schedule meets company rules with faster process compared to the manual process.

Part-time employee scheduling’s problem can be solved using Genetic algorithm which

has the function to get optimal solution value of a problem that has certain number of possible

solutions. Some available aspects which are number of working days, number of employee, and

number of shift are being used to form chromosome model, length of chromosome is number of

working days multiply by number of shift in one day, number of employees will be fitted to each

gen in a chromosome as the value of the gen (allele). Another aspect which is number of

employees’ shift monthly, employees’ performance, previous schedule, and employees’ request

are being used to form scheduling rules that in the future will be used to search fitness value of

each chromosome.

Genetic algorithm process is started by randomly form 10 chromosomes and then search

for the fitness value of each chromosome based on rules that had been pre-developed. In the next

step, the chromosomes are being selected using roulette wheel selection to determine 1 or 2

chromosomes that will be used for reproduction process, which are mutation and crossover.

Mutation process involves 1 chromosome with mutation probability 0%-5% for one time

scheduling process. On the other hand, crossover involves 2 chromosomes with either 2 points or

4 points crossover. Both reproduction processes will deliver offspring or new chromosome as the

result of reproduction, if the offspring result is better or has less fitness value compared to all the

chromosomes in the population, then the position of chromosomes in the population will be

replaced with this offspring, this process is called chromosome update.

This genetic algorithm process will be repeated as many as iteration number that has

been pre-defined. This process will be stopped if the iteration has been done as many as iteration

number that has been pre-defined or until chromosome fitness value = 0 is found (no infraction

of the rules). At last the chosen chromosome is being the final result that represent part-time

employee’s schedule.


x

KATA PENGANTAR

Puji dan syukur penulis panjatkan kepada Tuhan Yang Maha Esa atas berkat rahmat dan

karunia-Nya penulis dapat menyusun dan menyelesaikan skripsi yang berjudul “Sistem

Penjadwalan Karyawan Paruh Waktu dengan Algoritma Genetika” dengan baik.

Skripsi ini disusun untuk memenuhi salah satu syarat kelulusan jenjang Strata I Jurusan

Teknik Informatika Fakultas Sains dan Teknologi Universitas Sanata Dharma Yogyakarta.

Dalam proses penyusunan skripsi ini banyak mengalami hambatan, namun berkat bantuan,

bimbingan, dan kerjasama dari berbagai pihak akhirnya segala hambatan tersebut dapat teratasi

dengan baik.

Ucapan terima kasih penulis sampaikan khususnya kepada Bapak Drs. Haris Sriwindono,

M.Kom. selaku pembimbing yang telah sabar dan ikhlas meluangkan waktu, tenaga dan pikiran

dalam memberikan bimbingan, motivasi dan saran-saran selama proses penyusunan skripsi ini.

Penulis menyampaikan terima kasih pula kepada:

1. Ibu PH. Prima Rosa, S.Si., M.Sc yang telah membimbing penulis dalam pemilihan

topik dan metodologi penelitian

2. Pak Puspa selaku dosen pembimbing akademik

3. Seluruh Dosen Fakultas Sains dan Teknologi yang telah membekali ilmu sehingga

penulis dapat menyelesaikan studi di Universitas Sanata Dharma

4. Bapak Ibuk, mas Arif dan mas Thomas yang memberi motivasi dan selalu mendukung

penulis selama masa kuliah

5. Kezia, Meity, Dion, terima kasih atas kebersamaan kalian selama ini, terima kasih juga

untuk doa, dukungan, semangat dan perhatian kalian, kalian teman terluar biasa

6. Mas Adit yang telah mendukung, memberi perhatian dan selalu menemani penulis

dalam mengerjakan skripsi

7. Monic, Ria, Anggit, untuk doa dan dukungan kalian

8. Teman-teman Teknik Informatika 2011

9. Keluarga besar Kedai 24jam yang telah memberi kesempatan penulis untuk belajar

kasus penjadwalan dan selalu memberi tempat penulis dalam mengerjakan skripsi


xi

10. Semua pihak yang tidak dapat penulis sebutkan satu persatu yang telah membantu

terselesaikanya skripsi ini, terima kasih.

Penulis menyadari bahwa skripsi ini jauh dari sempurna, maka dengan segala kerendahan

hati penulis mengharapkan kritik dan saran yang bersifat membangun demi kesempurnaan

skripsi ini. Dengan segala keterbatasan yang dimiliki penulis juga berharap skripsi ini dapat

berguna dan mempunyai manfaat bagi berbagai pihak.

Penulis


xii

DAFTAR ISI

HALAMAN JUDUL ..................................................................... Error! Bookmark not defined.

HALAMAN PERSETUJUAN PEMBIMBING ............................ Error! Bookmark not defined.

HALAMAN PENGESAHAN ..................................................... Error! Bookmark not defined.v

PERNYATAAN KEASLIAN KARYA ......................................................................................... v

PERNYATAAN PERSETUJUAN PUPLIKASI………………...………………………………vi

HALAMAN PERSEMBAHAN .................................................. Error! Bookmark not defined.i

ABSTRAK ..................................................................................... Error! Bookmark not defined.

ABSTRACT ..................................................................................................................................... ix

KATA PENGANTAR .................................................................................................................... x

DAFTAR ISI .................................................................................. Error! Bookmark not defined.

DAFTAR GAMBAR ................................................................... Error! Bookmark not defined.v

DAFTAR TABEL ...................................................................... Error! Bookmark not defined.iii

BAB I PENDAHULUAN ............................................................................................................... 1

1.1. Latar Belakang .............................................................................................................. 1

1.2. Rumusan Masalah ......................................................................................................... 3

1.3. Manfaat dan Tujuan ...................................................................................................... 3

1.4. Batasan Masalah ........................................................................................................... 3

1.5. Metodologi Penelitian ................................................................................................... 4

1.6. Sistematika Penulisan .................................................. Error! Bookmark not defined.

BAB II LANDASAN TEORI ......................................................................................................... 6

2.1. Algoritma Genetika ....................................................................................................... 6

2.1.2. Pengertian Algoritma Genetika ......................................................................... 6


xiii

2.1.3. Istilah-istilah dalam Algoritma Genetika .......................................................... 6

2.1.4. Struktur Umum Algoritma Genetika ................................................................ 7

2.1.5. Basis Algoritma Genetika ................................................................................. 8

2.1.6. Operator Algoritma Genetika ........................................................................... 9

2.1.7. Hal-hal yang Harus Dilakukan dalam Algoritma Genetika .. Error! Bookmark

not defined.15

BAB III ANALISA DAN PERANCANGAN .............................................................................. 17

3.1 Definisi Masalah ......................................................................................................... 17

3.1.1 Analisis Sistem................................................................................................ 17

3.1.2 Gambaran Umum Sistem ................................................................................ 19

3.2 Perancangan Antarmuka ............................................................................................. 22

3.2.1 Perancangan Menu .......................................................................................... 22

3.2.2 Perancangan Input dan Output ........................................................................ 22

3.3 Perancangan Basisdata ................................................................................................ 28

3.3.1 Entitas dan Atribut .......................................................................................... 28

3.3.2 Relasi dan Entitas ............................................................................................ 29

3.3.3 ER Diagram .................................................................................................... 30

3.3.4 Diagram Fisikal ............................................................................................... 30

3.3.5 Perancangan Tabel .......................................................................................... 31

3.4 Perancangan Algoritma Genetika ............................................................................... 33

3.4.1 Representasi Masalah...................................................................................... 33

3.4.2 Pembentukan dan Pemodelan Kromosom ...................................................... 34

3.4.3 Pembangkitan Kromosom ............................................................................... 35

3.4.4 Pencarian Nilai Fitness ................................................................................... 35


xiv

3.4.5 Seleksi Kromosom .......................................................................................... 37

3.4.6 Proses Reproduksi ........................................................................................... 38

3.4.7 Update Generasi.............................................................................................. 40

3.4.8 Kondisi Berhenti ............................................................................................. 40

3.5 Penerapan Algoritma Genetika ................................................................................... 40

3.5.1 Pembangkitan Kromosom ............................................................................... 42

3.5.2 Pencarian Nilai Fitness ................................................................................... 45

3.5.3 Seleksi Kromosom .......................................................................................... 46

3.5.4 Reproduksi Kromosom ................................................................................... 47

BAB IV IMPLEMENTASI DAN ANALISA HASIL ................................................................. 54

4.1 Flowchart ................................................................................................................... 54

4.2 Implementasi Program ............................................................................................... 55

4.2.1 Form Utama .......................................................................................................... 55

4.2.2 Form Data Lokasi ................................................................................................ 55

4.2.3 Form Data Shift ................................................................................................... 56

4.2.4 Form Data Karyawan .......................................................................................... 57

4.2.5 Form Data Permintaan Jadwal ............................................................................ 58

4.2.6 Proses Penjadwalan ............................................................................................. 59

4.2.7 Jadwal Karyawan ................................................................................................ 60

4.3 Analisis Hasil Program ............................................................................................... 61

4.3.1 Pengujian Program .............................................................................................. 61

4.3.2 Kelebihan dan Kekurangan Program .................................................................. 66

BAB V PENUTUP ....................................................................................................................... 68

5.1 Kesimpulan ................................................................................................................. 68

5.2 Saran .......................................................................................................................... 68


xv

DAFTAR PUSTAKA ................................................................................................................... 69

DAFTAR GAMBAR

Gambar 2.1 Diagram alir proses algoritma genetika ............................................................ 9

Gambar 2.2 Contoh Seleksi Roda Roulette ........................................................................ 10

Gambar 2.3 Contoh Seleksi Rangking ................................................................................ 12

Gambar 2.4 Contoh Single Point Crossover ....................................................................... 13

Gambar 2.5 Contoh Multiple Point Crossover ................................................................... 14

Gambar 2.6 Contoh Uniform Crossover ............................................................................. 14

Gambar 2.7 Contoh Mutasi ................................................................................................. 15

Gambar 3.1 Flowchart sistem ............................................................................................. 20

Gambar 3.2 Flowchart pengaturan algoritma Genetika ...................................................... 20

Gambar 3.3 Flowchart algoritma Genetika ......................................................................... 21

Gambar 3.4 Perancangan menu .......................................................................................... 22

Gambar 3.5 Perancangan form utama................................................................................. 22

Gambar 3.6 Perancangan form data lokasi ......................................................................... 23

Gambar 3.7 Perancangan form data shift............................................................................ 24

Gambar 3.8 Perancangan form data karyawan ................................................................... 25

Gambar 3.9 Perancangan form permintaan jadwal ............................................................. 26

Gambar 3.10 Perancangan proses penjadwalan ................................................................... 27

Gambar 3.11 Perancangan jadwal karyawan ....................................................................... 28

Gambar 3.12 Diagram ER ................................................................................................... 30

Gambar 3.13 Diagram Fisikal .............................................................................................. 30

Gambar 3.14 Ilustrasi model kromosom.............................................................................. 34


xvi

Gambar 3.15 Ilustrasi proses crossover 2 titik .................................................................... 39

Gambar 3.16 Ilustrasi proses crossover 4 titik .................................................................... 39

Gambar 3.17 Ilustrasi proses mutasi .................................................................................... 39

Gambar 3.18 Diagram probabilitas total nilai fitness .......................................................... 47

Gambar 3.19 Representasi kromosom 7 sebagai induk 1 crossover 2 titik ......................... 48


Gambar 3.21 Representasi offspring 1 dari crossover 2 titik .............................................. 49






Gambar 3.27 Representasi kromosom 7 sebagai induk mutasi ........................................... 53

Gambar 3.28 Representasi offspring mutasi ........................................................................ 53

Gambar 4.1 Flowchart Sistem Penjadwalan Karyawan Paruh Waktu............................... 54

Gambar 4.2 Form Utama ................................................................................................... 55

Gambar 4.3 Form Data Lokasi .......................................................................................... 55

Gambar 4.4 Form Data Shift.............................................................................................. 56

Gambar 4.5 Form Data Karyawan ..................................................................................... 58

Gambar 4.6 Form Data Permintaan Jadwal Karyawan...................................................... 58

Gambar 4.7 Form Lokasi File ............................................................................................ 58

Gambar 4.8 Form Proses Penjadwalan .............................................................................. 59

Gambar 4.9 Form Pengaturan Algoritma Genetika ........................................................... 59

Gambar 4.10 Form Jadwal Karyawan ................................................................................. 60


xvii

Gambar 4.11 Grafik hubungan jumlah iterasi dengan rata-rata fitness terbaik ................... 61

Gambar 4.12 Grafik hubungan jenis crossover dengan rata-rata fitness terbaik ................. 62

Gambar 4.13 Grafik hubungan probabilitas mutasi dengan rata-rata fitness terbaik ........... 63

Gambar 4.14 Grafik hubungan jenis crossover dan probabilitas mutasi dengan rata-rata

fitness terbaik ................................................................................................. 65

Gambar 4.15 Grafik hubungan aturan permintaan jadwal dengan rata-rata fitness terbaik 66


xviii

DAFTAR TABEL

Tabel 3.1 Perancangan tabel lokasi .................................................................................... 31

Tabel 3.2 Perancangan tabel shift ...................................................................................... 31

Tabel 3.3 Perancangan tabel karyawan .............................................................................. 31

Tabel 3.4 Perancangan tabel permintaan jadwal ................................................................ 32

Tabel 3.5 Aturan-aturan penjadwalan karyawan ............................................................... 36

Tabel 3.6 Contoh Data Lokasi ........................................................................................... 41

Tabel 3.7 Contoh Data Karyawan ...................................................................................... 41

Tabel 3.8 Contoh Data Shift .............................................................................................. 41

Tabel 3.9 Contoh Data Permintaan Jadwal ........................................................................ 41

Tabel 3.10 Kromosom 1-10, Gen 1-18 ................................................................................ 42

Tabel 3.11 Kromosom 1-10, Gen 19-36 .............................................................................. 43




Tabel 3.15 Kromosom 1-10, Gen 91-108 ............................................................................ 44

Tabel 3.16 Kromosom 1-10, Gen 109-124 .......................................................................... 44

Tabel 3.17 Nilai fitness dan hasil konversi nilai fitness tiap kromosom .............................. 45

Tabel 3.18 Probabilitas total nilai fitness tiap kromosom .................................................... 46

Tabel 4.1 Hubungan jumlah iterasi dengan rata-rata fitness terbaik dengan permintaan

jadwal tidak aktif................................................................................................ 61

Tabel 4.2. Hubungan jenis crossover dengan rata-rata fitness terbaik ................................ 62


xix

Tabel 4.3 Hubungan probabilitas mutasi dengan rata-rata fitness terbaik ......................... 63

Tabel 4.4 Hubungan jenis crossover dan probabilitas mutasi dengan rata-rata fitness

terbaik ................................................................................................................ 64

Tabel 4.5 Hubungan aturan permintaan jadwal dengan rata-rata fitness terbaik ............... 66


1

BAB I

PENDAHULUAN

1.1. Latar Belakang

Berkembangnya teknologi pada era globalisasi ini telah memberi pengaruh besar

dalam dunia kerja, terutama pada penggunaan dan efisiensi sistem yang telah ada

sebelumnya. Selain itu fasilitas-fasilitas yang memadai dan mendukung pekerjaan sangat

dibutuhkan untuk terpenuhinya kebutuhan dan pengembangan usaha. Salah satunya

adalah penggunaan aplikasi yang membantu proses penyusunan jadwal karyawan paruh

waktu, aplikasi ini dapat menjadi salah satu contoh aplikasi yang mempermudah kegiatan

usaha dalam hal pengolahan data, juga efektif dan efisien dalam proses kinerjanya.

Kedai 24 Jam merupakan satu dari sekian banyak usaha kuliner di Jogja.

Konsumen dari kegiatan usaha ini sebagian besar adalah anak muda terutama para

mahasiswa yang sedang menetap di Jogja. Kegiatan usaha ini mempunyai 3 cabang yang

terletak di 3 daerah yang berbeda di Jogja dan mempunyai kurang lebih 25 orang

karyawan di setiap cabangnya. Dari keseluruhan karyawan yang bekerja, lebih dari 60%

diantaranya adalah karyawan paruh waktu.

Penyusunan jadwal karyawan paruh waktu tidak semudah menyusun

jadwal untuk karyawan full time, karena aspek yang mempengaruhi penyusunan jadwal

karyawan paruh waktu lebih banyak dan kompleks. Aspek – aspek tersebut antara lain

jumlah hari, jumlah shift per hari, jumlah shift karyawan dalam satu bulan, kualitas kerja

karyawan, jadwal sebelumnya dan permintaan jadwal karyawan paruh waktu yaitu

permohonan jadwal shift karyawan paruh waktu sebelum jadwal disusun. Setiap aspek

yang disebutkan tidak jarang menjadi masalah dalam penyusunan jadwal karyawan.

Sebagai contoh masalah yang dihadapi dari aspek jumlah shift karyawan adalah suatu

karyawan mempunyai jumlah shift yang kurang atau lebih dari jumlah shift tiap

karyawan yang sudah ditentukan sebelumnya.


2

Proses penjadwalan karyawan paruh waktu di Kedai 24 Jam selama ini masih

menggunakan sistem manual, para karyawan mengumpulkan permohonan jadwal tertulis

kemudian jadwal akan direkap dan disusun oleh manager perusahaan. Dalam proses

penyusunan, manager hanya menggunakan software Microsoft Excel dalam pengolahan

data dan tidak menggunakan kaidah komputasi, selain itu jumlah karyawan paruh waktu

juga relatif banyak. Proses penjadwalan dengan sistem manual tersebut dapat saja

dilakukan, namun ini akan menimbulkan masalah terutama dalam hal ketelitian yaitu

hasil yang kurang maksimal, dari segi waktu juga kurang efisien karena memerlukan

waktu yang lama.

Untuk mengatasi masalah yang ada akan dibuat sebuah perangkat lunak yaitu

sistem penjadwalan karyawan paruh waktu. Sistem akan menerima inputan dari semua

aspek yang berhubungan dengan penyusunan jadwal, kemudian mengidentifikasi dan

memecahkan masalah dengan menggunakan algoritma genetika.

Algoritma genetika adalah algoritma komputasi yang diinspirasi teori evolusi

yang kemudian diadopsi menjadi algoritma komputasi untuk mencari solusi suatu

permasalahan dengan cara yang lebih alamiah. Algoritma ini juga merupakan algoritma

pencarian secara heuristik. Salah satu fungsinya ialah untuk mencari solusi atas

permasalahan optimasi kombinasi, yaitu mendapatkan suatu nilai solusi optimal terhadap

suatu permasalahan yang mempunyai banyak kemungkinan solusi. Menurut teori Darwin

yang ditemukan oleh John Holland (1975), prinsip algoritma genetika yaitu setiap

makhluk hidup akan menurunkan satu atau beberapa karakter ke anak atau keturunannya.

Penyelesaian menggunakan algoritma genetika sangat berpengaruh dari kromosom yang

dibangun, dimana kromosom ialah sebuah molekul yang berisi DNA dimana terdapat

informasi genetik dalam setiap sel gen yang disimpan.

Berdasarkan hal diatas, peneliti tertarik untuk membuat sistem penjadwalan

karyawan paruh waktu dengan menerapkan algoritma genetika dan diharapkan kehadiran

sistem berbasis komputer ini akan menghasilkan solusi penjadwalan karyawan paruh

waktu dengan cepat dan hasil terbaik.


http://informatika.web.id/category/algoritma

3

1.2. Rumusan Masalah

Berdasarkan latar belakang yang dijelaskan sebelumnya, maka yang menjadi

permasalahan adalah :

1. apakah algoritma Genetika dapat digunakan untuk menyelesaikan permasalahan

penjadwalan karyawan paruh waktu ?

2. bagaimana sifat-sifat operator algoritma Genetika dan operator mana yang dapat

menghasilkan hasil selalu baik ?

1.3. Manfaat dan Tujuan

Berdasarkan rumusan masalah yang ada, maka tujuan dari penelitian ini adalah

membangun Sistem Penjadwalan Karyawan paruh waktu dengan menggunakan algoritma

Genetika dalam proses penjadwalan tersebut.

Manfaat dari penelitian ini adalah dapat menggunakan operator algoritma

Genetika untuk mendapatkan hasil akhir secara cepat dengan hasil terbaik.

1.4. Batasan Masalah

Keterbatasan waktu dan pengetahuan peneliti menimbulkan beberapa batasan

masalah dalam merancang perangkat lunak ini, antara lain :

a. sistem dirancang hanya untuk membantu manager dalam penyusunan jadwal

karyawan paruh waktu

b. studi kasus dilakukan pada usaha kuliner Kedai 24 jam

c. kriteria yang digunakan dalam proses penjadwalan karyawan paruh waktu adalah

jumlah hari, jumlah shift per hari, jumlah shift karyawan dalam satu bulan, kualitas

kerja karyawan, jadwal sebelumnya dan kriteria yang bersifat opsional yaitu

permintaan jadwal karyawan paruh waktu

d. sistem hanya akan berjalan dengan jumlah hari 31, jumlah shift 4 dan jumlah

karyawan untuk satu lokasi 8

e. proses penjadwalan tiap lokasi sama


4

f. jadwal dikatakan baik jika memenuhi atau hampir memenuhi semua kriteria

g. jadwal dibuat satu kali dalam sebulan

h. aplikasi dibangun menggunakan bahasa pemrograman Java dan MySQL

1.5. Metodologi Penelitian

Penelitian ini dilakukan dengan metodologi pengembangan waterfall (Winston,

1970) dengan tahap-tahap sebagai berikut :

1. Studi Literatur

Tahap ini dilaksanakan dengan melakukan studi kepustakaan dari buku-buku, e-book,

jurnal, makalah dan internet yang dapat mendukung penulisan tugas akhir.

2. Analisis

Tahap ini dilaksanakan dengan melakukan pengumpulan data dan fakta tentang

sistem penjadwalan karyawan paruh waktu serta melakukan analisis terhadap masalah

yang ada.

3. Perancangan

Tahap ini dilaksanakan dengan melakukan perancangan terhadap sistem yang akan

dibangun berdasarkan analisis yang telah dilakukan.

4. Implementasi

Tahap ini dilaksanakan dengan melakukan implementasi rancangan sistem ke dalam

bahasa pemrograman menggunakan NetBeans IDE.

5. Pengujian

Tahap ini dilaksanakan dengan mengeksekusi program untuk mengetahui apakah

sistem sudah berjalan dengan benar.

6. Analisis hasil

Tahap ini dilaksanakan dengan melakukan pengujian terhadap sistem untuk

mengetahui apakah sistem mampu membuat jadwal karyawan paruh waktu dengan

menerapkan algoritma genetika.


5

7. Penyusunan laporan

Tahap ini dilaksanakan dengan membuat laporan hasil analisis dan perancangan.

1.6. Sistematika Penulisan

Dalam penelitian ini, sistematika penulisan dibagi menjadi 5 bab yaitu :

1. Bab 1 : Pendahuluan

Bab ini menjelaskan latar belakang masalah, rumusan masalah, batasan

masalah, tujuan, metodologi penelitian, dan sistematika penulisan

2. Bab 2 : Landasan Teori

Bab ini berisi teori-teori yang menjadi dasar penelitian

3. Bab 3 : Analisa dan Perancangan

Bab ini berisi analisis masalah dan perancangan sistem yang nantinya akan

dibangun sebagai dasar dalam implementasi sistem

4. Bab 4 : Implementasi dan Analisa Hasil

Bab ini berisi implementasi sistem berdasarkan analisis dan perancangan

dan analisa hasil dari sistem yang telah diimplementasikan

5. Bab 5 : Penutup

Bab ini berisi kesimpulan dan saran untuk sistem yang dibuat demi

berkembangnya sistem tersebut


6

BAB II

LANDASAN TEORI

2.1. Algoritma Genetika

2.1.1. Pengertian Algoritma Genetika

Turban (2005: 882) menyatakan bahwa “algoritma Genetika adalah

kumpulan prosedur komputasional yang secara konseptual mengikuti langkah-

langkah yang diinspirasi oleh proses evolusi biologis. Solusi yang lebih baik dan

lebih baik lagi dikembangkan dari pembangkitan sebelumnya sampai solusi

optimal atau hampir optimal didapatkan”.

Salah satu aplikasi algoritma genetika adalah pada permasalahan optimasi,

yaitu mendapatkan suatu nilai solusi optimal terhadap suatu permasalahan yang

mempunyai banyak kemungkinan solusi. Daya tarik algoritma genetika terletak

pada kesederhanaan dan pada kemampuan untuk mencari solusi yang baik dan

cepat untuk masalah yang komplek.

2.1.2. Istilah-istilah dalam Algoritma Genetika

Algoritma genetika memiliki istilah-istilah yang digunakan untuk

menggambarkan keadaan/permasalahan sebenarnya ke dalam teori Genetika,

antara lain :

a. Gen

Gen merupakan nilai yang menyatakan satuan dasar yang membentuk suatu

arti tertentu dalam satu kesatuan gen yang dinamakan kromosom.

b. Allele

Allele merupakan nilai dari gen.


7

c. Kromosom / Individu

Kromosom merupakan gabungan dari gen-gen yang membentuk nilai tertentu

dan menyatakan solusi yang mungkin dari suatu permasalahan.

d. Populasi

Populasi merupakan sekumpulan individu yang akan diproses bersama dalam

satu satuan siklus evolusi.

e. Fitness

Fitness menyatakan seberapa baik nilai dari suatu individu yang didapatkan.

f. Seleksi

Seleksi merupakan proses untuk mendapatkan calon induk yang baik.

g. Crossover

Crossover merupakan proses pertukaran atau kawin silang gen-gen dari dua

induk tertentu.

h. Mutasi

Mutasi merupakan proses pergantian salah satu gen yang terpilih dengan nilai

tertentu.

i. Generasi

Generasi merupakan urutan iterasi dimana beberapa kromosom bergabung,

yaitu satu siklus proses evolusi atau satu iterasi di dalam algoritma genetika.

j. Offspring

Offspring merupakan kromosom baru yang dihasilkan.

2.1.3. Struktur Umum Algoritma Genetika

Bila P(t) adalah induk dan C(t) adalah keturunan pada generasi t,

struktur umum algoritma Genetika adalah sebagai berikut :


8

Procedure Algoritma Genetika

begin

t = 0

initialize P(t);

evaluate P(t);

while (not terminate condition)

do

recombine P(t) to yield C(t);

evaluate C(t);

select P(t+1) from P(t) and C(t);

t = t + 1;

end

end

2.1.4. Basis Algoritma Genetika

Ide dasar algoritma genetika adalah mengelola suatu populasi individu

yang merepresentasikan kandidat solusi sebuah permasalahan. Secara umum

algoritma genetika memiliki lima komponen dasar (Michalewicz, 1996) yaitu:

1. Representasi genetik dari solusi-solusi masalah.

2. Cara membentuk populasi awal dari solusi-solusi.

3. Fungsi evaluasi yang me-rate (rating) solusi-solusi berdasarkan fitness

mereka.

4. Operator-operator genetik yang merubah komposisi genetik dari offspring

selama reproduksi.

5. Nilai-nilai untuk parameter algoritma genetika.

Algoritma genetika berangkat dari himpunan solusi yang dihasilkan secara

acak yang disebut populasi. Sedangkan setiap individu dalam populasi disebut

kromosom yang merupakan representasi dari solusi dan masing-masing

dievaluasi tingkat ketanggguhannya (fitness) oleh fungsi yang telah ditentukan.


9

Melalui proses seleksi alam atas operator genetik, gen-gen dari dua kromosom

(disebut parent) diharapkan akan menghasilkan kromosom baru dengan tingkat

fitness yang lebih tinggi sebagai generasi baru atau keturunan (offspring)

berikutnya. Kromosom-kromosom tersebut akan mengalami iterasi yang disebut

generasi (generation). Menurut Gen dan Cheng (2000) pada setiap generasi,

kromosom dievaluasi berdasarkan nilai fungsi fitness. Setelah beberapa generasi

maka algoritma genetika akan konvergen dapat kromosom terbaik, yang

merupakan solusi optimal (Goldberg, 1989). Diagram alir algoritma Genetika

dapat dilihat pada gambar 2.1.

mulai

Deskripsikan persoalan

Ya

Hasilkan solusi awal

Tidak

Uji :

Apakah solusi terbaik

cukup baik ?

Pilih induk (pemain) untuk

bereproduksi

Berhenti

Terapkan proses penyilangan

dan hasilkan sekumpulan

keturunan

Terapkan mutasi acak

Langkah 1

Langkah 2

Langkah 3

Langkah 5

Langkah 4

Gambar 2.1 Diagram alir proses algoritma genetika

2.1.5. Operator Algoritma Genetika

Operator-operator yang digunakan dalam algoritma Genetika adalah :

a. Seleksi

Seleksi merukanan proses pemilihan kromosom untuk dijadikan

orang tua yang nantinya akan melakukan proses reproduksi. Berdasarkan


10

teori Darwin, kromosom yang terbaik harusnya dapat bertahan hidup dan

membentuk keturunan baru. Ada beberapa jenis metode seleksi, yaitu :

i. Seleksi Roda Roulete (Roulete Wheel selection)

Pada meotode seleksi ini orang tua yang dipilih berdasar kan

nilai fitness-nya, semakin baik nilai fitness-nya maka semakin besar

kemungkinan untuk dipilih. Diandakian semua kromosom diletakkan

pada sebuah roda roulette, besarnya kemungkinan bagi setiap

kromosom adalah tergantung dari fitness-nya seperti seperti contoh

pada Gambar 2.2.

Kromosom Fitness

A 15

B 5

C 10

D 5

E 5

Gambar 2.2 Contoh Seleksi Roda Roulette

Probabilitas untuk masing-masing individu merupakan hasil

pembagian antara fitness masing-masing individu dengan total fitness

dalam populasi. Dari contoh pada gambar 2.2 kromosom A memiliki

probabilitas 37,5% untuk terpilih sebagai orang tua pembentuk

keturunan baru pada setiap pemilihan kromosom. Secara algoritma,

seleksi roda roulette dapat dituliskan sebagai berikut :

begin

s = sumfitness(P) // jumlah fitness

semua kromosom dari populasi P


11

Skema seleksi roda roulette ini adalah berdasarkan skala

fitness karena terpilihnya suatu kromosom dalam populasi untuk

dapat berkembang biak adalah sebanding dengan fitness-nya, maka

akan terjadi semacam tradeoff antara eksplorasi dan eksploitasi jika

terdapat satu atau kelompok kecil kromosom yang mempunyai fitness

yang baik yaitu antara mengeksplorasi bagian-bagian baru dalam

ruang pencarian, atau terus mengeksploitasi informasi yang telah

diperoleh. Kecenderungan kromosom terbaik untuk terus terpelihara

terus dapat membawa ke hasil optimum lokal bukan global.

Sebaiknya jika semua kromosom dalam populasi mempunyai fitness

yang hampir sama, maka seleksi ini akan menjadi seleksi yang

bersifat acak.

ii. Seleksi Rangking (Linear-rank selection)

Seleksi rangking pertama yang dilakukan adalah merangking

atau mengurutkan kromosom didalam populasi berdasarkan nilai

fitness-nya kemudian memberi nilai fitness berdasarkan urutannya.

Kromosom dengan nilai fitness terburuk akan memiliki nilai fitness

baru bernlai 1, terburuk kedua bernilai 2 dan seterusnya. Sebagai

kromosom yang memiliki nilai fitness terbaik akan memiliki nilai

fitness n, dimana n adalah jumlah kromosom dalam populasi. Setelah

proses pengurutan dan pemberian nilai fitness baru, setiap kromosom

akan memiliki kesempatan yang lebih adil untuk terpilih. Tetapi

metode ini dapat menyebabkan konvergensi menjadi lambat, karena

kromosom terbaik tidak selalu berada dengan yang lainnya. Contoh

untuk seleksi rangking dapat dilihat pada gambar 2.3.


12

Gambar 2.3 Contoh Seleksi Rangking

iii. Seleksi Turnamen (Tournament selection)

Seleksi turnamen merupakan jenis seleksi yang divariasi

berdasarkan seleksi roda roulette dan seleksi rangking. Sejumlah k

kromosom tertentu dari populasi beranggota n kromosom (k<=n)

dipilih secara acak dengan prioritas yang sama. Dari k kromosom

yang terpilih kemudian akan dipilih satu kromosom dengan fitness

terbaik, yang diperoleh dari hasil pengurutan rangking nilai fitness

semua kromosom terpilih.

Perbedaanya dengan seleksi roda roulette adalah pemilihan

kromosom yang akan dipergunakan untuk berkembang biak tidak

berdasarkan skala fitness dari populasi. Untuk k=1, seleksi turnamen

akan sama dengan seleksi secara acak karena hanya melibatkan satu

kromosom. Untuk k=2, maka dua kromosom dari populasi secara

acak, kemudian akan dipilih satu kromosom dengan nilai fitness

terbaik. Biasanya yang sering digunakan adalah k=2, tergantung dari

jumlah kromosom yang terdapat didalam populasi.

b. Perkawinan Silang (crossover)

Perkawinan silang digunakan untuk membentuk keturunan baru

berdasarkan orang tua yang terpilih. Operator ini lebih dominan dalam

algoritma Genetika dibandingkan dengan operator mutasi. Jumlah kromosom

yang terlibat dalam perkawinan silang ini adalah 2 kromosom.


13

Perkawinan silang dilakukan dengan harapan kromosom-kromosom

baru akan mempunyai bagian baik dari kromosom-kromosom lama dan tidak

menutup kemungkinan menjadi kromosom-kromosom yang lebih baik. Ada

beberapa jenis perkawinan silang, antara lain :

i. Single Point Crossover

Dalam Single Point Crossover ada satu titik potongan pada

dua kromosom yang dipilih secara acak, maka terdapat dua bagian

kepala dan dua bagian ekor. Kemudian akan dilakukan pertukaran

bagian tersebut secara acak, misal kedua bagian ekor pada dua

kromosom tersebut ditukar untuk memproduksi dua individu baru

(offspring). Contoh dari Single Point Crossover dapat dilihat pada

gambar 2.4.

Gambar 2.4 Contoh Single Point Crossover

ii. Multiple Point Crossover

Dalam Multiple Point Crossover ada lebih dari satu titik

potongan dan ada banyak persilangan dan bagian dalam kedua

kromosom, yang akan dilakukan pertukaran antar bagian tersebut

secara acak. Contoh dari Multiple Point Crossover dapat dilihat pada

gambar 2.5.


14

Gambar 2.5 Contoh Multiple Point Crossover

iii. Uniform Crossover

Dalam Uniform Crossover, gen dari offspring didapat dengan

menyalin gen dari orang tua. Gen dari orang tua yang akan dijadikan

gen pada offspring dipilih secara acak yaitu indeks gen ke berapa dan

gen dari orang tua yang mana. Contoh dari Uniform Crossover dapat

dilihat pada gambar 2.6.

Gambar 2.6 Contoh Uniform Crossover

c. Mutasi

Mutasi merupakan proses mengubah nilai dari satu atau beberapa gen

dalam satu kromosom tertentu. Tujuanya adalah untuk membantu

mempercepat terjadinya perbedaan diantara semua kromosom dalam

populasi sehingga pencarian dapat menjelajah keseluruh ruang pencarian,

tetapi mutasi tidak boleh terlalu sering dilakukan karena akan membuat

algoritma Genetika berubah menjadi pencarian acak.

Proses mutasi dalam biologi adalah mengubah allele pada suatu

kromosom dengan allele yang lain. Proses mutasi dilakukan secara acak,

sehingga tidak selalu menjamin bahwa setelah proses mutasi akan diperoleh


15

kromosom dengan nilai fitness yang lebih baik dibandingkan dengan sebelum

proses mutasi dilakukan, oleh karena itu terjadi kontroversi dalam

penerapanya pada algoritma Genetika. Mutasi sering kali tetap dipergunakan

hanya saja probabilitas mutasinya kecil. Contoh untuk mutasi dapat dilihat

pada gambar 2.7.

Gambar 2.7 Contoh Mutasi

d. Update populasi

Update populasi adalah proses membaharui kromosom yang terdapat

dalam populasi. Pada algoritma Genetika, N kromosom pada suatu generasi

digantikan sekaligus oleh N kromosom baru hasil perkawinan silang silang

atau mutasi. Adapun prosedur update populasi pada algoritma Genetika

ialah:

1. Mengganti kromosom/individu yang memiliki nilai fitness terburuk.

2. Mengganti kromosom/individu yang paling tua.

3. Membandingkan anak dengan kedua orang tua, apabila anak memiliki

nilai fitness lebih baik akan menggantikan orang tua yang memiliki nilai

fitness buruk.

2.1.6. Hal-hal yang harus dilakukan dalam Algoritma Genetika

Beberapa hal yang harus dilakukan dalam algoritma genetika adalah :

1. Mendefinisikan individu, dimana individu menyatakan salah satu solusi

(penyelesaian) yang mungkin dari permasalahan yang diangkat.


16

2. Mendefinisikan nilai fitness, yang merupakan ukuran baik-tidaknya sebuah

individu atau baik-tidaknya solusi yang didapatkan.

3. Menentukan proses pembangkitan populasi awal. Hal ini biasanya dilakukan

dengan menggunakan pembangkitan acak seperti random-walk.

4. Menentukan proses seleksi yang akan digunakan.

5. Menentukan proses perkawinan silang (cross-over) dan mutasi gen yang

akan digunakan.


17

BAB III

ANALISA DAN PERANCANGAN

3.1. Definisi Masalah

3.1.1. Analisa Sistem

Proses penjadwalan karyawan paruh waktu di Kedai 24 jam merupakan

salah satu masalah optimasi yang masih dilakukan dengan cara manual. Adapun

dalam proses penjadwalan ini menyangkut beberapa komponen yang saling

berkaitan yaitu :

1. Hari

Hari merupakan jumlah hari yang digunakan untuk satu kali proses

penjadwalan

2. Shift

Shift merupakan jumlah shift per hari untuk satu lokasi

3. Karyawan

Karyawan merupakan jumlah karyawan dalam satu lokasi dan data karyawan

yaitu nama dan kualitas karyawan

4. Jadwal sebelumnya

Jadwal sebelumnya merupakan suatu shift yang dimiliki seorang karyawan,

sebagai contoh hari pertama suatu karyawan mempunyai shift ke-3, maka

untuk menentukan shift karyawan pada hari kedua karyawan tersebut

mempunyai komponen jadwal sebelumnya yaitu 3 (shift ke-3)

Selain komponen-komponen tersebut juga ada satu komponen

permintaan jadwal karyawan yaitu permohonan jadwal shift karyawan paruh

waktu sebelum jadwal disusun. Komponen ini bersifat opsional, jadi dalam

proses penjadwalan komponen ini bisa saja digunakan dan bisa tidak digunakan

tergantung pengaturan, karena dalam kenyataanya permintaan jadwal karyawan

ini digunakan namun tidak menjamin semua permintaan jadwal karyawan

terkabulkan/sama dengan jadwal karyawan.


18

Jadwal karyawan paruh waktu merupakan hasil kesepakatan pembuat

jadwal dan karyawan yang diperoleh dari tiap-tiap komponen yang ada, hasil

kesepakatan ini diharapkan saling menguntungkan antar pembuat jadwal dan

semua karyawan sehingga kesepakatan terbaik akan menjadi hasil akhir dengan

proses yang lebih cepat dari sistem penjadwalan yang telah ada.

Adanya komponen-komponen yang mempengaruhi penyusunan jadwal ini

diharapkan akan menghasilkan hasil terbaik, namun ada beberapa permasalahan

yang harus dihindari dalam proses penyusunan jadwal antara lain, satu karyawan

mempunyai shift lebih dari satu dalam satu hari yang sama, permasalahan lain

yang harus dihindari ada karyawan yang mempunyai shift terakhir dalam satu

hari kemudian mempunyai shift pertama di hari berikutnya. Oleh karena itu

dibuat aturan-aturan penjadwalan karyawan paruh waktu untuk menghindari

permasalahan-permasalahan yang ada, aturan-aturan tersebut adalah sebagai

berikut :

1. Satu karyawan tidak dapat mempunyai lebih dari satu shift dalam satu hari

yang sama

2. Dua karyawan yang sama-sama mempunyai kualitas „kurang‟ tidak boleh

mempunyai shift yg berurutan dalam satu hari

3. Karyawan yang mempunyai shift terakhir dalam satu hari tidak dapat

mempunyai shift pertama di hari berikutnya

4. Jumlah shift tiap karyawan dalam satu bulan = 14 – 16 shift

5. Shift karyawan dalam satu waktu sama dengan permintaan jadwal karyawan

tersebut, aturan ini bersifat opsional.

Semua proses penyusunan jadwal bisa saja dilakukan secara manual,

namun masih mengalami hambatan dalam penanganan masalah yang muncul dan

akan bepengaruh pada hasil akhir, terutama dalam hal ketelitian, dengan proses

ini juga membutuhkan waktu yang lama.


19

3.1.2. Gambaran Umum Sistem yang Dibuat

Untuk mengatasi permasalahan yang muncul dengan sistem penjadwalan

yang masih manual diperlukan suatu sistem baru yang dapat menangani hal

tersebut agar mendapat hasil terbaik dengan proses penjadwalan yang lebih

cepat. Permasalahan penjadwalan karyawan paruh waktu ini dapat diselesaikan

menggunakan algoritma genetika. Algoritma genetika merupakan salah satu

solusi untuk menyelesaikan masalah optimasi berdasarkan mekanisme seleksi

alami dan sifat genetika. Dari data yang ada yaitu jumlah hari, jumlah shift per

hari, jumlah karyawan dalam suatu lokasi dapat diarahkan untuk pembentukan

kromosom-kromosom sebagai populasi awal. Dari beberapa kemungkinan

kromosom yang terbentuk akan dipilih beberapa kromosom terbaik yang akan

menjadi kromosom-kromosom induk. Dari beberapa kromosom induk akan

dikembangkan dalam perkawinan silang dan mutasi untuk mendapatkan

keturunan yang baik yang akan menjadi hasil akhir, yaitu satu kromosom yang

akan mewakili terbentuknya jadwal karyawan. Flowchart sistem yang akan

dibuat tampak pada gambar 3.1 dengan pengaturan algoritma pada gambar 3.2

dan flowchart algoritma Genetika yang digunakan dalam sistem tampak pada

gambar 3.3.


20

mulai

Proses algoritma genetika

Input data lokasi

Input permintaan jadwal

Input data shift

Input data karyawan

Jadwal karyawan

selesai

Input pengaturan

algoritma genetika

Gambar 3.1 Flowchart sistem

mulai

Probabilitas mutasi =

(besar probabilitas mutasi/100) * jumlah iterasi

Input jumlah iterasi

Input keaktifan

permintaan jadwal

Input besar probabilitas

mutasi

Input jenis crossover

selesai

Gambar 3.2 Flowchart pengaturan algoritma Genetika


21

mulai

Pembentukan kromosom

Evaluasi nilai fitnes tiap

kromosom dengan aturan

permintaan jadwal

Iterasi < jumlah iterasi ?

Y

Pembangkitan populasi

awal

Iterasi = 0

Aturan permintaan

jadwal aktif ?


kromosom tanpa aturan

permintaan jadwal

Seleksi kromosom

Iterasi =

iterasi mutasi ?Proses mutasi

Proses crossover 2 titik

Jenis crossover =

2 titik ?

Proses crossover

4 titik

Iterasi++

Evaluasi nilai fitnes

offspring

Update kromosom

Fitness == 0 ?

kromosom terbaik

Y

Y

Y

T

T

T

T

selesai

Iterasi mutasi =

iterasi mutasi + iterasi

Iterasi mutasi =

Jumlah iterasi / probabilitas mutasi

Gambar 3.3 Flowchart algoritma Genetika


22

3.2. Perancangan Antarmuka

3.2.1. Perancangan Menu

DATA

JADWAL

KELUAR

Data Shift

Data Karyawan

Data Permintaan Jadwal

Data Lokasi

Jadwal Karyawan

Proses Penjadwalan

Gambar 3.4 Perancangan menu

3.2.2. Perancangan Input dan Output

3.2.2.1. Form Utama

SISTEM PENJADWALAN

KARYAWAN PARUH WAKTU

Data Penjadwalan Keluar

LOGO

Gambar 3.5 Perancangan form utama


23

Form utama pada gambar 3.5 terdiri dari 3 menu yaitu : Data,

Penjadwalan, dan Keluar. Menu Data terdiri dari 4 sub menu, yaitu : data

lokasi, data shift, data lokasi dan data permintaan jadwal. Menu

Penjadwalan mempunyai 2 sub menu, yaitu : Proses penjadwalan dan

Lihat jadwal

3.2.2.2. Form Data Lokasi

SISTEM PENJADWALAN


DATA LOKASI

Edit

Hapus

BatalSimpan

Kode Lokasi

namalokasikodelokasi alamat

Nama Lokasi

Alamat

Keluar

Gambar 3.6 Perancangan form data lokasi

Form data lokasi pada gambar 3.6 digunakan untuk mengolah

data lokasi yang meliputi kode lokasi, nama lokasi dan alamat. Dalam

form lokasi ini terdapat tabel lokasi yang digunakan untuk menampilkan

data lokasi. Terdapat 3 text field : kode lokasi, nama lokasi dan alamat

untuk memasukkan/mengedit data masing-masing. Terdapat 5 button

beserta fungsinya, yaitu : button Simpan untuk menyimpan data lokasi,

button Edit untuk mengedit data lokasi(terlebih dahulu memilih data yang

akan diedit), button Hapus untuk menghapus data lokasi(terlebih dahulu

memilih data yang akan dihapus), button Batal untuk membatalkan

proses pengolahan data lokasi yang sedang berlangsung, dan button

Keluar untuk keluar dari form data lokasi.


24

3.2.2.3. Form Data Shift

SISTEM PENJADWALAN


DATA SHIFT

Edit

Hapus

Batal Simpan

Kode Shift

Kode Shift Mulai Selesai Lokasi

Nama Shift

Waktu Mulai

Waktu Selesai

Lokasi V

Keluar

Gambar 3.7 Perancangan form data shift

Form data shift pada gambar 3.7 digunakan untuk mengolah data

shift yang meliputi kode shift, nama shift, waktu mulai, waktu selesai dan

lokasi. Dalam form shift ini terdapat tabel shift yang digunakan untuk

menampilkan data shift. Terdapat 4 text field : kode shift, nama shift,

waktu mulai dan waktu selesai untuk memasukkan/mengedit data

masing-masing. Terdapat 1 combo box lokasi yang berisi data lokasi yang

telah tersimpan sebelumnya untuk memasukkan/mengedit data lokasi

pada data shift. Terdapat 5 button beserta fungsinya, yaitu : button

Simpan untuk menyimpan data shift, button Edit untuk mengedit data

shift(terlebih dahulu memilih data yang akan diedit), button Hapus untuk

menghapus data shift(terlebih dahulu memilih data yang akan dihapus),

button Batal untuk membatalkan proses pengolahan data shift yang

sedang berlangsung, dan button Keluar untuk keluar dari form data shift.


25

3.2.2.4. Form Data Karyawan

SISTEM PENJADWALAN


DATA KARYAWAN

Hapus

Edit

SimpanBatal

Kode Karyawan

Kode Nama Telp Kualitas Lokasi

Nama Karyawan

No. Telp

Kualitas

Lokasi V

Keluar

Kurang Cukup Baik

Gambar 3.8 Perancangan form data karyawan

Form data karyawan pada gambar 3.8 digunakan untuk mengolah

data karyawan yang meliputi kode karyawan, nama karyawan, nomor

telepon, kualitas dan lokasi. Dalam form karyawan ini terdapat tabel

karyawan yang digunakan untuk menampilkan data karyawan. Terdapat 3

text field : kode karyawan, nama karyawan dan notelp untuk

memasukkan/mengedit data masing-masing. Terdapat 3 radio button

kualitas : kurang, cukup, baik untuk memasukkan/mengedit data kualitas

karyawan, dimana kualitas ini ditentukan oleh user dari penilaian kinerja

karyawan tersebut sebelumnya. Terdapat 1 combo box lokasi yang berisi

data lokasi yang telah tersimpan sebelumnya untuk

memasukkan/mengedit data lokasi pada data karyawan. Terdapat 5

button beserta fungsinya, yaitu : button Simpan untuk menyimpan data

karyawan, button Edit untuk mengedit data karyawan(terlebih dahulu

memilih data yang akan diedit), button Hapus untuk menghapus data


26

karyawan(terlebih dahulu memilih data yang akan dihapus), button Batal

untuk membatalkan proses pengolahan data karyawan yang sedang

berlangsung, dan button Keluar untuk keluar dari form data karyawan.

3.2.2.5. Form Data Permintaan Jadwal

SISTEM PENJADWALAN


DATA PERMINTAAN JADWAL

Hapus SimpanBatal

Kode Permintaan

Kode Karyawan

Karyawan

Permintaan Jadwal

V

hari1

Browse

Keluarhari2 hari3 hari4 hari5 hari6 hari7 hari8 ha

Gambar 3.9 Perancangan form permintaan jadwal

Form permintaan jadwal pada gambar 3.9 digunakan untuk

mengolah data permintaan jadwa yang meliputi kode permintaan jadwal,

karyawan, permintaan jadwal dari hari1 sampai dengan hari31. Dalam

form permintaan jadwal ini terdapat tabel permintaan jadwal yang

digunakan untuk menampilkan data permintaan jadwal. Terdapat 2 text

field : kode permintaan jadwal dan permintaan jadwal untuk

memasukkan/mengedit data masing-masing. Terdapat 1 combo box

karyawan yang berisi data karyawan yang telah tersimpan sebelumnya

untuk memasukkan/mengedit data karyawan pada data permintaan

jadwal. Terdapat 5 button beserta fungsinya, yaitu : button Browse untuk

mengambil path, yaitu alamat yang merujuk ke file permintaan jadwal

tiap karyawan (file harus mempunyai format .csv), button Simpan untuk

menyimpan data permintaan jadwal, button Hapus untuk menghapus data

permintaan jadwal(terlebih dahulu memilih data yang akan dihapus),


27

button Batal untuk membatalkan proses pengolahan data permintaan

jadwal yang sedang berlangsung, dan button Keluar untuk keluar dari

form data permintaan jadwal.

3.2.2.6. Proses Penjadwalan

SISTEM PENJADWALAN


PROSES PENJADWALAN

Buat Jadwal

Lokasi V

Bulan V

Hari 5 Hari 6 Hari 7 Hari 8 Hari 9

Keluar

Hari 4Hari 3Hari 2Hari 1x

Gambar 3.10 Perancangan proses penjadwalan

Form proses penjadwalan pada gambar 3.10 digunakan untuk

membuat jadwal karyawan dari data-data karyawan yang telah tersimpan

sebelumnya. Dalam form proses penjadwalan ini terdapat tabel proses

penjadwalan yang digunakan untuk menampilkan jadwal yang telah

terbuat. Terdapat 2 combo box : lokasi dan bulan yang berisi data lokasi

yang telah tersimpan sebelumnya dan data nama bulan untuk batasan

sebelum jadwal dibuat. Terdapat 2 button beserta fungsinya, yaitu :

button Buat Jadwal untuk memulai proses penjadwalan dan button Keluar

untuk keluar dari form proses penjadwalan.


28

3.2.2.7. Jadwal Karyawan

SISTEM PENJADWALAN


JADWAL KARYAWAN

KeluarSimpan

Bulan : Lokasi:

Hari 5 Hari 6 Hari 7 Hari 8 Hari 9Hari 4Hari 3Hari 2Hari 1x

Gambar 3.11 Perancangan jadwal karyawan

Form jadwal karyawan pada gambar 3.11 digunakan untuk melihat

dan mencetak data jadwal karyawan yang telah terbuat. Dalam form

proses penjadwalan ini terdapat tabel jadwal karyawan yang digunakan

untuk menampilkan jadwal karyawan yang telah terbuat sebelumnya.

Terdapat 2 button beserta fungsinya, yaitu : button Simpan untuk

menyimpan data jadwal karyawan dalam format excel (.xls) dan button

Keluar untuk keluar dari form jadwal karyawan.

3.3. Perancangan Basisdata

3.3.1. Entitas dan Atribut

1. Entitas Shift

Entitas Shift berisi data shift, memiliki atribut sebagai berikut : kodeshift

(sebagai Primary-Key), namashift, mulai, selesai, lokasi

2. Entitas Lokasi

Entitas lokasi berisi data lokasi, memiliki atribut sebagai berikut : kodelokasi

(sebagai Primary-Key), namalokasi, alamat


29

3. Entitas Karyawan

Entitas Karyawan berisi data karyawan, memiliki atribut sebagai berikut :

kodekaryawan(sebagai Primary-Key), namakaryawan, notelp, kualitas,

lokasi

4. Entitas Permintaanjadwal

Entitas Permintaanjadwal berisi data permintaan jadwal karyawan, memiliki

atribut sebagai berikut : kodepermintaanjadwal, karyawan, hari1, hari2,

hari3, hari4, hari5, hari6, hari7, hari8, hari9, hari10, hari11, hari12, hari13,

hari14, hari15, hari16, hari17, hari18, hari19, hari20, hari21, hari22, hari23,

hari24, hari25, hari26, hari27, hari28, hari29, hari30, hari31

3.3.2. Relasi dan Entitas

1. Relasi Shift dengan Lokasi

Shift dengan Lokasi memiliki relasi “punya” dengan derajad relasi one-to-

many. Satu lokasi punya banyak shift, sedangkan satu shift hanya punya satu

lokasi.

2. Relasi Lokasi dengan Karyawan

Lokasi dengan karyawan memiliki relasi “punya” dengan derajad relasi one-

to-many. Satu lokasi punya banyak karyawan, sedangkan satu karyawan

hanya punya satu lokasi.

3. Karyawan dengan Permintaanjadwal

Karyawan dengan Permintaanjadwal memiliki relasi “buat” dengan derajad

relasi one-to-one. Satu permintaanjadwal dibuat oleh satu karyawan, dan satu

karyawan membuat satu permintaanjadwal.


30

3.3.3. ER Diagram

Gambar 3.12 Diagram ER

3.3.4. Diagram Fisikal

Shift PermintaanjadwalLokasi Karyawan

kodeshift

namashift

mulai

selesai

kodelokasi

kodelokasi

namalokasi

alamat

kodekaryawan

namakaryawan

notelp

kualitas

kodelokasi

kodepermintaan

kodekaryawan hari1

hari2

hari3

hari4

hari5

hari6

hari7

hari8

hari9

hari10

hari11

hari12

hari13

hari14

hari15

hari16

hari17

hari18

hari19

hari20

hari21

hari22

hari23

hari24

hari25

hari26

hari27

hari28

hari29

hari30

hari31

*

**

**

****

*

Gambar 3.13 Diagram Fisikal


31

3.3.5. Perancangan Tabel

TABEL LOKASI

FIELD NAMA TYPE SIZE KEY

kodelokasi varchar 5 *

namalokasi varchar 10

alamat varchar 50

Tabel 3.1 Perancangan tabel lokasi

TABEL SHIFT


kodeshift varchar 5 *

namashift varchar 10

mulai varchar 5

selesai varchar 5

kodelokasi varchar 5 **

Tabel 3.2 Perancangan tabel shift

TABEL KARYAWAN


kodekaryawan varchar 5 *

namakaryawan varchar 10

noelp varchar 15

Kualitas varchar 10

kodelokasi varchar 5 **

Tabel 3.3 Perancangan tabel karyawan


32

TABEL PERMINTAAN JADWAL


kodepermintaanjadwal varchar 5 *

kodekaryawan varchar 5 **

hari1 varchar 5

hari2 varchar 5

hari3 varchar 5

hari4 varchar 5

hari5 varchar 5

hari6 varchar 5

hari7 varchar 5

Hari varchar 5

hari8 varchar 5

hari9 varchar 5

hari10 varchar 5

hari11 varchar 5

hari12 varchar 5

hari13 varchar 5

hari14 varchar 5

hari15 varchar 5

hari16 varchar 5

hari17 varchar 5

hari18 varchar 5

hari19 varchar 5

hari20 varchar 5

hari21 varchar 5

hari22 varchar 5

hari23 varchar 5

hari23 varchar 5

hari25 varchar 5


33

hari26 varchar 5

hari27 varchar 5

hari28 varchar 5

hari29 varchar 5

hari30 varchar 5

hari31 varchar 5

Tabel 3.4 Perancangan tabel permintaan jadwal

3.4. Perancangan Algoritma Genentika dalam Penjadwalan Karyawan

Paruh Waktu

3.4.1. Representasi Masalah

Penjadwalan karyawan paruh waktu ini memiliki beberapa komponen

yaitu jumlah shift per hari, jumlah karyawan dalam suatu shift, kualitas kerja

karyawan, jadwal sebelumnya dan satu komponen yang bersifat opsional yaitu

permohonan jadwal karyawan paruh waktu. Beberapa komponen akan digunakan

sebagai pembentuk model kromosom. Komponen-komponen yang digunakan

akan dibangun dengan menempatkan setiap komponen menjadi sebuah kode

untuk mempresentasikan masalah ke dalam bentuk kromosom.

Jumlah gen diperoleh dari jumlah shift dalam satu hari dan jumlah hari

akan membentuk sebuah kromosom. Panjang kromosom yaitu jumlah gen dalam

satu kromosom merupakan jumlah hasil kali dari jumlah shift dalam satu hari

dan jumlah hari. Panjang kromosom/jumlah gen yang terbentuk dapat

dirumuskan sebagai berikut :

K = S * H ………………………………………………………...…..(3.1)

Keterangan :

K = panjang kromosom/jumlah gen

S = jumlah shift dalam satu hari

H = jumlah hari


34

3.4.2. Pembentukan dan Pemodelan Kromosom

Kromosom dibangkitkan secara acak untuk menempatkan karyawan pada

setiap shift dan hari tertentu.

Pengkodean yang digunakan dalam pembentukan kromosom ini adalah

pengkodean nilai, dimana nilai yang di enkodekan langsung merupakan

representasi dari masalah. Dalam masalah penjadwalan karyawan paruh waktu

ini karyawan menjadi populasi dalam kromosom, maka data karyawan akan di

enkodekan menggunakan data real.

HARI 1 HARI 2 . . .

HARI 31

KRM JAP PAE STY NLC JAP STY HNK STY JAP PAE AFR

S1 S2 S3 S4 S1 S2 S3 S4

S1 S2 S3 S4

Gambar 3.14 Ilustrasi model kromosom

Permodelan kromosom diilustrasikan seperti gambar 3.14. Setiap gen

kromosom ditempati satu shift dimana 1-4 merupakan kode shift, yang dapat

diartikan :

Kotak ke-n = [hari; shift; karyawan]

Kotak ke-1 = [1; 1; KRM]

= [hari ke-1; shift 1; karyawan KRM]

Kotak ke-2 = [1; 2; JAP]

= [hari ke-1; shift 2; karyawan JAP]

Kotak ke-3 = [1; 3; PAE]

= [hari ke-1; shift 3; karyawan PAE]

Kotak ke-4 = [1; 4; STY]

= [hari ke-1; shift 4; karyawan STY]

Kotak ke-5 = [2; 1; NLC]

= [hari ke-2; shift 1; karyawan NLC]


35

Kotak ke-6 = [2; 2; JAP]


Kotak ke-7 = [2; 3; STY]


Kotak ke-8 = [2; 4; HNK]

= [hari ke-2; shift 4; karyawan HNK]

…

Kotak ke-121 = [31; 1; STY]


Kotak ke-122 = [31; 2; JAP]


Kotak ke-123 = [31; 3; PAE]

= [hari ke-31; shift 3; karyawan PAE]

Kotak ke-124 = [31; 4; AFR]

= [hari ke-31; shift 4; karyawan AFR]

3.4.3. Pembangkitan Kromosom

Kromosom akan dibangkitkan secara acak, untuk populasi awal

dibangkitkan 10 kromosom dan masing-masing kromosom mempunyai

124 gen. Kromosom yang dibangkitkan akan ditempati oleh hari, shift dan

karyawan.

3.4.4. Pencarian Nilai Fitness

Nilai fitness menentukan kualitas/baik dan buruknya kromosom yang

diperoleh dari pelanggaran terhadap aturan-aturan yang ditentukan. Semakin

kecil nilai fitness suatu kromosom maka kromosom tersebut semakin baik. Nilai

fitness dikatakan optimal jika tidak terjadi pelanggaran terhadap aturan-aturan

pada tabel 3.5.

Dalam masalah penjadwalan karyawan paruh waktu ini diasumsikan

semakin besar nilai fitness suatu kromosom maka kromosom tersebut semakin


36

baik, oleh karena itu nilai fitness terkecil di konversi menjadi nilai fitness terbesar

dalam kromosom, nilai fitness tiap kromosom diperoleh dari total fitness semua

kromosom dibagi dengan nilai tiap kromosom, maka nilai fitness telah

terkonversi. Nilai fitness dapat dirumuskan sebagai berikut :

Nilai Fitness’ = Total Nilai Fitness / Nilai Fitness .…………(3.4)

Keterangan :

Nilai Fitness’ = nilai fitness setelah dikonversi

Nilai Fitness = nilai fitness tiap kromosom

Total Nilai fitness = total nilai fitness semua kromosom

3.4.4.1. Aturan-aturan penjadwalan karyawan

NO ATURAN PELANGGARAN

1

Satu karyawan tidak dapat

mempunyai lebih dari satu shift

dalam satu hari yang sama

Fitness = + 1, jika ada satu

karyawan mempunyai dua shift

atau lebih dalam satu hari yang

sama

2

Dua karyawan yang sama-sama

mempunyai kualitas=1 tidak boleh

mempunyai shift yg berurutan

dalam satu hari

Fitness = + 1, jika ada dua

karyawan yang sama-sama

mempunyai kualitas=1 berada

dalam shift yg berurutan dalam

satu hari

3

Karyawan yang mempunyai shift

terakhir dalam satu hari tidak dapat

mempunyai shift pertama di hari

berikutnya

Fitness = + 1, jika ada karyawan

berada pada shift 4 di satu hari dan

menempati shift 1 pada hari

berikutnya

4 Jumlah shift tiap karyawan dalam

satu bulan = 14 – 16 shift

Fitness = + 1, jika shift karyawan

dalam satu bulan <14 dan >16


37

5

Shift karyawan dalam satu waktu

sama dengan permintaan jadwal

karyawan tersebut (opsional)

Fitness = + 1, jika aturan

permintaan jadwal digunakan dan

shift karyawan tidak sesuai dengan

permintaan jadwal karyawan

Tabel 3.5 Aturan-aturan penjadwalan karyawan

3.4.5. Seleksi Kromosom

Seleksi kromosom adalah mencari kromosom dalam populasi untuk

dipilih menjadi orang tua. Dalam masalah penjadwalan karyawan paruh waktu

ini seleksi dilakukan dengan metode Roda Roulette (Roulette Wheel), proses ini

dilakukan berdasarkan nilai fitness, semakin baik nilai fitness suatu kromosom

maka semakin besar kemungkinan kromosom akan menjadi orang tua.

Kromosom yang terpilih sebagai orang tua adalah kromosom yang akan

melakukan proses reproduksi yaitu operasi persilangan dan operasi mutasi

dengan harapan akan mendapatkan kromosom yang lebih baik dari kromosom

sebelumnya.

Dari total nilai fitness dalam populasi yang diperoleh sebelumnya, dicari

probabilitas masing-masing individu. Probabilitas dari setiap kromosom dapat

dirumuskan sebagai berikut :

P = (t / s) * 100 ……………………………………………..(3.2)

Keterangan :

P = Probabilitas tiap kromosom

t = total nilai fitness tiap kromosom

s = total nilai fitness semua kromosom


38

Dari probabilitas tiap individu yang diperoleh akan digambarkan ke dalam

Roda Roulette (Roulette Wheel), semakin besar probabilitas individu semakin

besar pula bagian individu tersebut di dalam Roda Roulette (Roulette Wheel).

Proses seleksi dilakukan dengan menentukan satu titik untuk menentukan

kromosom yang dipilih setelah Roda Roulette (Roulette Wheel) diputar dan

berhenti dengan sendirinya.

3.4.6. Proses Reproduksi

Proses reproduksi bertujuan untuk mendapatkan kromosom baru yang

lebih baik dari kromosom induknya, proses ini menggunakan operasi

persilangan/crossover dan operasi mutasi. Crossover dilakukan setiap kali iterasi

kecuali pada suatu iterasi akan dilakukan proses mutasi, maka proses crossover

tidak dilakukan pada iterasi tersebut. Mutasi dilakukan sesuai dengan masukan

besar probabilitas mutasi, dengan probabilitas mutasi akan dicari kapan dan

berapa kali proses mutasi dilakukan. Untuk mencari berapa kali proses mutasi

dilakukan dapat dirumuskan sebagai berikut :

Jumlah mutasi = (probabilitas mutasi / 100) * jumlah iterasi …....(3.3)

Untuk mencari kapan mutasi dilakukan/pada kelipatan iterasi berapa proses

mutasi dilakukan dapat dirumuskan sebagai berikut :

Iterasi mutasi = jumlah iterasi / jumlah mutasi ……………..…….(3.4)

Operasi persilangan merupakan proses menggabungkan dua kromosom

yang telah terpilih sebagai orang tua untuk menghasilkan dua individu baru.

Dalam masalah penjadwalan karyawan paruh waktu ini ada dua jenis crossover

yang akan digunakan yaitu crossover 2 titik dan crossover 4 titik, ilustrasi kedua

jenis proses reproduksi tersebut dapat dilihat pada gambar 3.15 dan gambar 3.16.


39

Gambar 3.15 Ilustrasi proses crossover 2 titik

Gambar 3.16 Ilustrasi proses crossover 4 titik

Operasi mutasi merupakan proses mengubah satu bagian kromosom (gen)

dari sebuah kromosom yang terpilih untuk menghasilkan satu individu baru.

Dalam masalah penjadwalan karyawan paruh waktu ini mutasi yang yang

digunakan adalah mutasi satu titik dengan proses yang diilustrasikan pada gambar

3.17.

Gambar 3.17 Ilustrasi proses mutasi


40

3.4.7. Update Generasi

Update kromosom adalah memperbaharui kromosom yang dilakukan

setelah proses reproduksi, proses ini dilakukan dengan membuang kromosom

terburuk kemudian mengganti kromosom tersebut dengan offspring/kromosom

hasil perkawinan silang maupun mutasi, dengan catatan kromosom baru hasil

reproduksi tersebut lebih baik dari kromosom terburuk dari populasi sebelumnya,

offspring dikatakan lebih baik jika nilai fitness-nya lebih kecil dari nilai fitness

kromosom terburuk. Hasil update generasi adalah populasi baru yang akan

digunakan untuk proses selanjutnya.

3.4.8. Kondisi Berhenti

Proses reproduksi ini akan dilakukan berulang-ulang, namun proses bisa

berhenti jika ditemukan beberapa kondisi sebagai berikut :

a. Offspring/kromosom baru hasil reproduksi mempunyai nilai optimal yaitu

nilai fitness = 0

b. Proses reproduksi sudah dilakukan sebanyak jumlah iterasi yang ditentukan

Selebihnya proses reproduksi akan terus dilakukan, offspring-offspring

akan diseleksi kembali, begitu seterusnya sampai terpenuhi kriteria berhenti.

Proses reproduksi ini nantinya akan menghasilkan kromosom terbaik sebagai

hasil akhir.

3.5. Penerapan Algoritma Genetika dalam Penjadwalan Karyawan Paruh

Waktu

Dalam permasalahan penjadwalan karyawan paruh waktu, akan dirancang jadwal

karyawan di salah satu lokasi untuk menjadwalkan 4 shift dengan 8 karyawan dalam 31

hari dengan contoh data seperti tabel dibawah ini :


41

1. Data Lokasi

Tabel 3.6 Contoh Data Lokasi

2. Data Karyawan

Tabel 3.7 Contoh Data Karyawan

3. Data Shift

Tabel 3.8 Contoh Data Shift

4. Data Permintaan Jadwal


42

Tabel 3.9 Contoh Data Permintaan Jadwal

3.5.1. Pembangkitan Kromosom

Kromosom / kumpulan dari beberapa gen mempunyai panjang 124 yang

diperoleh dari :

Kromosom = Shift * Hari

= 4 * 31

= 124

Jadi, jumlah gen untuk sebuah kromosom = 124

Kromosom dibangkitkan secara acak, untuk populasi awal dibangkitkan

10 kromosom yang masing-masing kromosom terdiri dari 124 gen. Tiap gen

menyatakan hari, shift dan karyawan tertentu. Sebagai contoh kromosom-

kromosom tersebut adalah sebagai berikut :

Tabel 3.10 Kromosom 1-10, Gen 1-18


43





44





45

3.5.2. Pencarian Nilai Fitness

Total nilai fitness dilakukan pada setiap kromosom dengan cara mengecek

tiap gen pada kromosom berdasarkan aturan-aturan yang ditetapkan. Untuk nilai

awal, setiap kromosom diberi nilai fitness 0, yaitu nilai fitness minimal.

Kemudian total nilai fitness dikonversi dari terkecil ke terbesar dan sebaliknya

dari terbesar ke terkecil, konversi ini dilakukan dengan tujuan agar kromosom

yang mempunyai total nilai fitness terkecil memperoleh bagian terbesar dan

sebaliknya total nilai fitness terbesar memperoleh bagian terkecil pada Roda

Roulette, yaitu metode yang digunakan untuk proses selanjutnya yaitu proses

seleksi.

Sebagai contoh dari hasil pencarian nilai fitness 10 kromosom, didapat

total nilai fitness dan hasil konversi nilai fitness tiap kromosom yang dapat dilihat

pada tabel 3.17.

Kromosom Nilai fitness Nilai fitness‟

Kromosom 1 120 8,33

Kromosom 2 124 8,06

Kromosom 3 110 9,09

Kromosom 4 69 14,49

Kromosom 5 98 10,20

Kromosom 6 75 13,33

Kromosom 7 100 10

Kromosom 8 104 9,62

Kromosom 9 85 11,76

Kromosom 10 115 8,70

103,59

Tabel 3.17 Nilai fitness dan hasil konversi nilai fitness tiap kromosom


46

3.5.3. Seleksi Kromosom

Dari total nilai fitness tiap kromosom, dicari probabilitas masing-masing

individu :

Probabilitas kromosom i = nilai fitness‟ i – total nilai fitness‟ i

Probabilitas kromosom 1 = (8,33 / 103,59) * 100 = 8,04




Probabilitas kromosom 5 = (10,20/ 103,59) * 100 = 9,85


Probabilitas kromosom 7 = (10 / 103,59) * 100 = 9,65




Didapat probabilitas tiap kromosom yang dapat dilihat pada tabel 3.18

Kromosom Probabilitas (%)

Kromosom 1 8,04

Kromosom 2 7,79

Kromosom 3 8,78

Kromosom 4 13,99

Kromosom 5 9,85

Kromosom 6 12,87

Kromosom 7 9,65

Kromosom 8 9,28

Kromosom 9 11,36

Kromosom 10 8,39

Tabel 3.18 Probabilitas total nilai fitness tiap kromosom


47

Dalam masalah penjadwalan karyawan paruh waktu ini representasi Roda

Roulette (Roulette Wheel) digambarkan dalam bentuk diagram garis. Gambar 3.18

adalah diagram garis yang dibentuk berdasarkan probabilitas fitness dalam

kromosom, panjang garis dibentuk dalam range 1-100 yang kemudian dibagi

menjadi 10 bagian yang menggambarkan jumlah kromosom, dimana panjang

setiap bagian ditentukan berdasarkan probabilitas total fitness tersebut.

Kromosom 1 memiliki probabilitas 12% untuk terpilih menjadi orang tua dalam

pemilihan kromosom, maka range 1-12 dalam garis mewakili kromosom 1, dan

seterusnya.

Gambar 3.18 Diagram probabilitas total nilai fitness

Berdasarkan gambar 3.17 proses seleksi dilakukan dengan

membangkitkan bilangan acak dari 0-100, kemudian dari bilangan tersebut dapat

ditentukan kromosom mana yang terpilih, sebagai contoh bilangan yang didapat

adalah 65, maka kromosom 7 adalah kromosom yang terpilih menjadi orang tua

karena 65 masuk dalam range 61,32 – 70,97 yang merupakan range yang

mewakili kromosom 7.

3.5.4. Reproduksi Kromosom

Reproduksi kromosom dilakukan setiap kali iterasi hingga kondisi

berhenti terpenuhi. Setiap iterasi akan dilakukan proses crossover atau proses

mutasi. Proses crossover dilakukan setiap iterasi kecuali akan dilakukan proses

mutasi. Sesuai rumus 3.3 dan 3.4 proses mutasi dilakukan sesuai masukan besar

probabilitas mutasi, misal masukan probabilitas mutasi dengan jumlah iterasi 100

adalah 5%, maka jumlah mutasi akan dilakukan sebanyak 5 kali, diperoleh dari

(5/100)*100. Proses mutasi akan dilakukan setiap kelipatan iterasi 20, diperoleh

dari 100/5.


48

Pada suatu iterasi proses seleksi kromosom yang terpilih adalah

kromosom 7, sebagai contoh pada seleksi kromosom berikutnya kromosom

yang terpilih adalah kromosom 3, maka akan dilakukan proses persilangan antar

kedua kromosom tersebut dengan 2 jenis persilangan yaitu crossover 2 titik dan

crossover 4 titik. Kedua proses persilangan tersebut dilakukan secara opsional

yaitu memilih salah satu jenis persilangan yang nantinya akan menghasilkan 2

kromosom yang diharapkan akan lebih baik dari kromosom induknya. Ilustrasi

proses crossover 2 titik dan proses crossover 4 titik adalah sebagai berikut :

Induk 1 untuk crossover 2 titik : kromosom 7

Gambar 3.19 Representasi kromosom 7 sebagai induk 1 crossover 2 titik


49



Offspring 1 : kromosom baru yang dihasilkan dari proses crossover 2 titik

Gambar 3.21 Representasi offspring 1 dari crossover 2 titik


50






51






52



Operasi mutasi hanya melibatkan satu kromosom yang terpilih, yaitu

kromosom 7 yang mempunyai nilai fitness terbaik. Kromosom 7 akan menjadi

induk yang juga diharapkan akan menghasilkan kromosom baru yang lebih baik

dari kromosom induknya. Ilustrasi proses mutasi adalah sebagai berikut :


53

Induk untuk mutasi : Kromosom 7

Gambar 3.27 Representasi kromosom 7 sebagai induk mutasi

Offspring : kromosom baru yang dihasilkan dari proses mutasi

Gambar 3.28 Representasi offspring mutasi


54

BAB IV

IMPLEMENTASI DAN ANALISA HASIL

4.1. FLOWCHART

Flowchart sistem untuk menjadwalkan karyawan paruh waktu dengan

algoritma genetika adalah sebagai berikut :

mulai

Input data lokasi

Input permintaan

jadwal

Input data shift

Input data karyawan

Probabilitas mutasi =

(besar probabilitas mutasi/100) *

jumlah iterasi

Input jumlah iterasi

Input keaktifan

permintaan jadwal

Input besar

probabilitas mutasi

Input jenis crossover

Pembentukan kromosom

Evaluasi nilai fitnes tiap kromosom

dengan aturan permintaan jadwal

Iterasi < jumlah iterasi ?

Y

Pembangkitan populasi awal

Iterasi = 0

Aturan permintaan

jadwal aktif ?


kromosom tanpa aturan

permintaan jadwal

Seleksi kromosom

Iterasi =

iterasi mutasi ?Proses mutasi

Proses crossover 2 titik

Jenis crossover =

2 titik ?

Proses crossover

4 titik

Iterasi++

Evaluasi nilai fitnes offspring

Update kromosom

Fitness == 0 ?

kromosom terbaik

Y

Y

Y

T

T

T

selesai

T

T

Y

Iterasi mutasi =

iterasi mutasi + iterasi

Iterasi mutasi =

Jumlah iterasi / probabilitas mutasi

Gambar 4.1 Flowchart Sistem Penjadwalan Karyawan Paruh Waktu


55

4.2. IMPLEMENTASI PROGRAM

4.2.1. Form Utama

Gambar 4.2 Form Utama

4.2.2. Form Data Lokasi

Gambar 4.3 Form Data Lokasi

Form data lokasi akan muncul setelah memilih menu Data dan sub

menu Data Lokasi. Data lokasi langsung ditampilkan pada form data lokasi

pada tabel lokasi. Untuk menambah data lokasi langsung mengisi kode

lokasi, nama lokasi, dan alamat pada form isian kemudian pilih tombol

Simpan. Untuk mengedit data lokasi, pilih data dari tabel lokasi yang akan

diedit maka data akan muncul pada form isian, ganti data yang akan diedit

kemudian pilih tombol Edit. Untuk menghapus data lokasi, pilih data dari

tabel lokasi yang akan dihapus kemudian pilih tombol Hapus. Untuk

membatalkan proses tambah, edit dan hapus data lokasi pilih tombol Batal


56

sebelum data selesai diproses. Untuk keluar dari form data lokasi pilih

tombol Keluar dan pengguna akan kembali masuk pada form utama.

4.2.3. Form Data Shift

Gambar 4.4 Form Data Shift

Form data shift akan muncul setelah memilih menu Data dan sub

menu Data Shift. Data shift langsung ditampilkan pada form data shift pada

tabel shift. Untuk menambah data shift langsung mengisi kode shift, nama

shift, waktu mulai, waktu selesai dan memilih lokasi shift pada form isian

kemudian pilih tombol Simpan. Untuk mengedit data shift, pilih data dari

tabel shift yang akan diedit maka data akan muncul pada form isian, ganti

data yang akan diedit kemudian pilih tombol Edit. Untuk menghapus data

shift, pilih data dari tabel shift yang akan dihapus kemudian pilih tombol

Hapus. Untuk membatalkan proses tambah, edit dan hapus data shift pilih

tombol Batal sebelum data selesai diproses. Untuk keluar dari form data shift

pilih tombol Keluar dan pengguna akan kembali masuk pada form utama.


57

4.2.4. Form Data Karyawan

Gambar 4.5 Form Data Karyawan

Form data karyawan akan muncul setelah memilih menu Data dan

sub menu Data Karyawan. Data karyawan langsung ditampilkan pada form

data karyawan pada tabel karyawan. Untuk menambah data karyawan

langsung mengisi kode karyawan, nama karyawan, nomor telepon dan

memilih kualitas karyawan dan lokasi karyawan pada form isian kemudian

pilih tombol Simpan. Untuk mengedit data karyawan, pilih data dari tabel

karyawan yang akan diedit maka data akan muncul pada form isian, ganti

data yang akan diedit kemudian pilih tombol Edit. Untuk menghapus data

karyawan, pilih data dari tabel karyawan yang akan dihapus kemudian pilih

tombol Hapus. Untuk membatalkan proses tambah, edit dan hapus data

karyawan pilih tombol Batal sebelum data selesai diproses. Untuk keluar dari

form data karyawan pilih tombol Keluar dan pengguna akan kembali masuk

pada form utama.


58

4.2.5. Form Data Permintaan Jadwal

Gambar 4.6 Form Data Permintaan Jadwal Karyawan

Gambar 4.7 Form Lokasi File

Form data permintaan jadwal akan muncul setelah memilih menu

Data dan sub menu Data Permintaan Jadwal. Data permintaan jadwal

karyawan langsung ditampilkan pada form data permintaan jadwal pada tabel

permintaan jadwal. Untuk menambah data permintaan jadwal langsung

mengisi kode permintaan jadwal dan memilih karyawan dan permintaan

jadwal pada form isian, untuk memilih permintaan jadwal telebih dahulu

pilih tombol Browse, maka akan tampil form lokasi file seperti tampak pada

gambar 4.7, pilih lokasi file kemudian pilih tombol Ok pada form lokasi file

dan path data permintaan jadwal telah masuk pada form isian, kemudian pilih


59

tombol Simpan pada form permintaan jadwal. Untuk menghapus data

permintaan jadwal, pilih data dari tabel permintaan jadwal yang akan dihapus

kemudian pilih tombol Hapus. Untuk membatalkan proses tambah dan hapus

data permintaan jadwal pilih tombol Batal sebelum data selesai diproses.

Untuk keluar dari form data permintaan jadwal pilih tombol Keluar dan

pengguna akan kembali masuk pada form utama.

4.2.6. Proses Penjadwalan

Gambar 4.8 Form Proses Penjadwalan

Gambar 4.9 Form Pengaturan Algoritma Genetika

Form proses penjadwalan akan muncul setelah memilih menu

Penjadwalan dan sub menu Proses Penjadwalan. Jadwal akan ditampilkan

setelah proses penjadwalan dilakukan. Untuk melakukan proses penjadwalan


60

terlebih dahulu memilih lokasi dan bulan sesuai jadwal yang akan dibuat,

kemudian pilih tombol Buat Jadwal, maka akan tampil form pengaturan

algoritma genetika seperti tampak pada gambar 4.9, isi terlebih dahulu

jumlah iterasi, kemudian pilih jenis crossover yang akan digunakan yaitu

crossover 2 titik atau crossover 4 titik, kemudian probabilitas mutasi antara

0% - 5%, terakhir pilih aktif tidaknya aturan permintaan jadwal, kemudian

pilih tombol OK pada form pengaturan algoritma genetika. Selanjutnya

proses penjadwalan akan berjalan dan hasil berupa jadwal karyawan akan

ditampilkan dalam tabel proses penjadwalan. Untuk membatalkan pengaturan

algoritma genetika pilih tombol batal pada form tersebut. Untuk keluar dari

form proses penjadwalan pilih tombol Keluar dan pengguna akan kembali

masuk pada form utama.

4.2.7. Jadwal Karyawan

Gambar 4.10 Form Jadwal Karyawan

Form Jadwal Karyawan akan muncul setelah memilih menu

Penjadwalan dan sub menu Lihat Jadwal. Form Jadwal Karyawan akan

menampilkan kembali hasil dari proses penjadwalan, yaitu data lokasi, bulan,

dan jadwal karyawan dari proses penjadwalan terakhir. Untuk keluar dari

form jadwal karyawan pilih tombol Keluar dan pengguna akan kembali

masuk pada form utama.


61

4.3. ANALISIS HASIL PROGRAM

4.3.1. Pengujian Program Sistem Penjadwalan Karyawan Paruh Waktu

Pengujian program dilakukan dengan melakukan percobaan pada

sistem penjadwalan karyawan paruh waktu, percobaan dilakukan untuk

mencari beberapa hal yaitu sebagai berikut :

1. Jumlah iterasi dan rata-rata fitness terbaik yang dihasilkan

Program dijalankan sebanyak 10 kali percobaan (p) dengan

crossover 4 titik, probabilitas mutasi 5 dan aturan permintaan jadwal

tidak aktif. Menghasilkan hubungan jumlah iterasi dengan nilai fitness

yang dihasilkan yang dapat dilihat pada tabel 4.1.

Tabel 4.1 Hubungan jumlah iterasi dengan rata-rata fitness terbaik dengan

permintaan jadwal tidak aktif

Gambar 4.11 Grafik hubungan jumlah iterasi dengan rata-rata fitness

terbaik

Berdasarkan tabel 4.1 dan grafik hubungan jumlah iterasi dengan

rata-rata fitness terbaik pada gambar 4.25 dapat disimpulkan bahwa nilai

fitness yang dihasilkan untuk setiap jumlah iterasi bersifat random,

6

6.5

7

7.5

8

20 40 60 80 100

Rata-rata Fitness

Rata-rataFitness


62

semakin banyak jumlah iterasi yang dilakukan pada suatu percobaan

tidak menjamin nilai fitness pada percobaan tersebut semakin baik, tetapi

dilihat dari rata-rata nilai fitness yang dihasilkan untuk setiap jumlah

iterasi, semakin banyak jumlah iterasi kemungkinan nilai fitness baik

semakin besar.

2. Jenis crossover dan rata-rata fitness terbaik yang dihasilkan


jumlah iterasi 100, probabilitas mutasi 1% dan aturan permintaan jadwal

tidak aktif. Menghasilkan hubungan jenis crossover dengan nilai fitness


Tabel 4.2. Hubungan jenis crossover dengan rata-rata fitness terbaik

Gambar 4.12 Grafik hubungan jenis crossover dengan rata-rata fitness

terbaik

Berdasarkan tabel 4.2 dan grafik hubungan jenis crossover dengan

rata-rata fitness terbaik pada gambar 4.26 dapat disimpulkan bahwa nilai

fitness yang dihasilkan untuk setiap jenis crossover bersifat random, jenis

0

2

4

6

8

10

i-1

i-2

i-3

i-4

i-5

i-6

i-7

i-8

i-9

i-1

0

Nilai Fitness

Crossover 2titik

Crossover 4titik


63

crossover yang digunakan pada suatu percobaan tidak menjamin nilai

fitness pada percobaan tersebut selalu lebih baik, tetapi dilihat dari rata-

rata nilai fitness yang dihasilkan dari kedua jenis crossover, crossover 2

titik mempunyai kemungkinan nilai fitness baik lebih besar daripada

crossover 4 titik.

3. Probabilitas mutasi dan rata-rata fitness terbaik yang dihasilkan


jumlah iterasi 100, jenis crossover 4 titik dan aturan permintaan jadwal

tidak aktif. Menghasilkan hubungan probabilitas mutasi dengan nilai

fitness yang dihasilkan yang dapat dilihat pada tabel 4.3.

Tabel 4.3 Hubungan probabilitas mutasi dengan rata-rata fitness terbaik

Gambar 4.13 Grafik hubungan probabilitas mutasi dengan rata-rata

fitness terbaik

6.5

7

7.5

8

0 1 2 3 4 5

Rata-rata Fitness

Rata-rataFitness


64

Berdasarkan tabel 4.3 dan grafik hubungan probabilitas mutasi

dengan rata-rata fitness terbaik pada gambar 4.27 dapat disimpulkan

bahwa nilai fitness yang dihasilkan untuk probabilitas mutasi 0% - 5%

bersifat random, besar probabilitas mutasi yang digunakan untuk setiap

percobaan tidak ada yang menjamin nilai fitness pada percobaan tersebut

baik.

4. Jenis crossover dan probabilitas mutasi dengan rata-rata fitness

terbaik yang dihasilkan


jumlah iterasi 100 dan aturan permintaan jadwal aktif. Menghasilkan

hubungan jenis crossover dan probabilitas mutasi dengan nilai fitness


Tabel 4.4 Hubungan jenis crossover dan probabilitas mutasi dengan rata-

rata fitness terbaik


65

Gambar 4.14 Grafik hubungan jenis crossover dan probabilitas mutasi

dengan rata-rata fitness terbaik

Berdasarkan tabel 4.4 dan grafik hubungan jenis crossover dan

probabilitas mutasi dengan rata-rata fitness terbaik pada gambar 4.28

dapat disimpulkan bahwa nilai fitness yang dihasilkan untuk setiap

hubungan jenis crossover dan besar probabilitas mutasi bersifat random,

tidak ada hubungan khusus untuk jenis crossover dan besar probabilitas

mutasi yang menjamin nilai fitness hubungan tersebut selalu baik.

5. Aturan permintaan jadwal dan rata-rata fitness terbaik yang

dihasilkan


jumlah iterasi 100, jenis crossover 4 titik dan probabilitas mutasi 2.

Menghasilkan hubungan aktif tidaknya aturan permintaan jadwal dengan

nilai fitness yang dihasilkan yang dapat dilihat pada tabel 4.5.

0

1

2

3

4

5

6

7

8

9

0 1 2 3 4 5

crossover 2titik

crossover 4titik


66

Tabel 4.5 Hubungan aturan permintaan jadwal dengan rata-rata fitness

terbaik

Gambar 4.15 Grafik hubungan aturan permintaan jadwal dengan rata-rata

fitness terbaik

Berdasarkan tabel 4.5 dan grafik hubungan aturan permintaan

jadwal dengan rata-rata fitness terbaik pada gambar 4.29 dapat

disimpulkan bahwa` nilai fitness yang dihasilkan untuk aktif tidaknya

aturan permintaan jadwal, percobaan dengan aturan permintaan jadwal

tidak aktif menghasilkan nilai fitness lebih baik daripada percobaan

dengan aturan permintaan jadwal aktif.

4.3.2. Kelebihan dan Kekurangan Program

Kelebihan dari program Sistem Penjadwalan Karyawan Paruh Waktu

adalah sebagai berikut :

1. Program mudah digunakan dengan fasilitas tombol pengolah data serta

urutan jalan program yang jelas dan mudah dimengerti pengguna

0

20

40

60

80

100

120

i-1

i-2

i-3

i-4

i-5

i-6

i-7

i-8

i-9

i-1

0

Nilai Fitness

aktif

tidak aktif


67

2. Penggunaan algoritma Genetika dalam proses penjadwalan dapat diatur

sesuai keinginan pengguna

3. Nilai fitness tiap iterasi secara otomatis tersimpan dalam file dengan

alamat path „E:\ data fitness iterasi.xls‟

4. Hasil program berupa jadwal karyawan paruh waktu dapat disimpan

dalam file dengan format .xls

Kekurangan dari program Sistem Penjadwalan Karyawan Paruh

Waktu adalah sebagai berikut :

1. Desain interface program minimalis dan kurang menarik

2. Setiap komponen yang digunakan dalam proses penjadwalan sudah

ditentukan jumlahnya sehingga tidak fleksibel


68

BAB V

PENUTUP

5.1. KESIMPULAN

Berdasarkan pembahasan pada bab-bab sebelumnya, maka dapat disimpulkan

bahwa :

1. Algoritma Genetika dapat digunakan untuk menyelesaikan permasalahan

penjadwalan karyawan paruh waktu dengan sifat-sifat operator sebagai berikut :

a. Semakin banyak aturan yang digunakan untuk mencari nilai fitness maka

semakin sedikit juga kemungkinan mendapatkan nilai fitness baik

b. Untuk mendapatkan nilai fitness yang lebih baik biasanya dibutuhkan iterasi

yang lebih banyak

c. Jenis crossover dan besar probabilitas mutasi yang digunakan tidak memberi

jaminan untuk mendapat hasil yang lebih baik.

2. Semua operator algoritma Genetika bersifat random sehingga tidak ada operator

tertentu yang menjamin hasil selalu baik.

5.2. SARAN

Sebagai perimbangan untuk pengembangan program ini, ada beberapa saran

yang dapat penulis sampaikan :

1. Program dapat dikembangkan dengan desain interface yang lebih menarik

2. Program dapat dikembangkan dengan membuat jumlah setiap komponen

penjadwalan fleksibel

3. Program dapat dikembangkan dengan menyelesaikan permasalahan penjadwalan

karyawan paruh waktu dengan algoritma lainnya selain algoritma Genetika.


69

DAFTAR PUSTAKA

Affenzeller, Michael, dkk. 2000. Genetic Algorithms and Genetic Programming. London : CRC

Press.

Ferianingrum, Wahyu. 2009. Sistem Pendukung Pengambilan Keputusan Penjadwalan Kuliah

dengan Algoritma Genetika. Skripsi. Fakultas Sains dan Teknologi Universitas Sanata Dharma.

Yogyakarta.

Mitsuo, Gen, dan Runwei Cheng. 2000. Genetic Algorithms and Engineering Design. New York

: Wiley-Interscience.

Nikodemus. 2006. Penjadwalan Mata Kuliah dengan Algoritma Genetika. Skripsi. Fakultas Sains

dan Teknologi Universitas Sanata Dharma. Yogyakarta.

Turban, Efraim, Jay E. Aronson dan Ting-Peng Liang. 2005. Sistem Pendukung Keputusan dan

Sistem Cerdas. Yogyakarta : Andi.


plagiat merupakan tindakan tidak terpuji - core.ac.uk fileperusahaan salah satunya adalah manager...

Documents