Shift Scheduler - Kecerdasan Buatan

⚙️ Parameter Hill Climbing

Jumlah Langkah 5000

Berapa kali algoritma mencoba perbaikan

🏔️

Belum ada hasil Hill Climbing

Pilih varian, atur parameter, lalu klik Jalankan

📖 Tentang Algoritma Optimasi

Penjelasan konsep, cara kerja, dan implementasi tiga algoritma pencarian lokal yang digunakan pada studi kasus penjadwalan shift karyawan.

🏭 Studi Kasus: Penjadwalan Shift Karyawan

Deskripsi Problem

Penjadwalan shift karyawan adalah masalah optimasi nonlinear NP-hard. Dengan 10 karyawan, 4 jenis shift (Pagi, Siang, Malam, Libur), dan 7 hari, terdapat 4⁷⁰ ≈ 10⁴² kemungkinan jadwal yang mustahil diperiksa satu per satu.

Algoritma pencarian lokal bekerja dengan cara mencoba jadwal tetangga, yaitu jadwal baru yang hanya berbeda satu perubahan kecil dari jadwal saat ini (misalnya: mengubah shift Andi di hari Senin dari Pagi menjadi Siang). Dengan cara ini, algoritma menjelajahi ruang solusi secara efisien tanpa harus memeriksa semua kemungkinan.

Kualitas setiap jadwal diukur menggunakan fungsi fitness. Semakin sedikit aturan yang dilanggar, semakin tinggi nilai fitness-nya. Jadwal yang memenuhi semua aturan akan mendapat nilai fitness 1.0.

Constraint yang Harus Dipenuhi

Shift Pagi minimal 2 karyawan per hari
Shift Siang minimal 2 karyawan per hari
Shift Malam minimal 1 karyawan per hari
Setiap karyawan maksimal 5 hari kerja per minggu
Setiap karyawan minimal 2 hari libur per minggu
Dilarang jadwal Malam kemudian Pagi keesokan hari (anti-fatigue)

Fungsi Fitness

fitness = 1 / (1 + total_pelanggaran)

Nilai 1.0 berarti tidak ada pelanggaran sama sekali (jadwal sempurna)

🏔️ Hill Climbing Algorithm

Mulai dari jadwal acak, terus bergerak ke jadwal yang lebih baik (tetangga) hingga tidak ada lagi yang bisa diperbaiki.

Simple HC

Evaluasi 1 tetangga acak per langkah. Langsung pindah jika lebih baik atau sama baik.

Steepest-Ascent HC

Evaluasi 80 tetangga sekaligus, pilih yang terbaik. Lebih cermat per langkah.

Stochastic HC

Pilih tetangga secara acak. Hasil bisa berbeda tiap run, wajar untuk algoritma stochastic.

⚠️ Kelemahan: Mudah terjebak di local optimum, yaitu solusi yang lebih baik dari sekitarnya tapi bukan yang terbaik secara global.

🌡️ Simulated Annealing

Terinspirasi dari pendinginan logam. Keunggulan utama: SA bisa menerima solusi yang lebih buruk dengan probabilitas tertentu untuk keluar dari jebakan local optimum yang sering dialami Hill Climbing. Inilah yang membuat SA lebih andal dalam menemukan solusi mendekati optimal global.

Eksplorasi Awal (T₀)

Semakin besar → lebih bebas menerima solusi buruk di awal.

Kecepatan Fokus (α)

Seberapa cepat probabilitas penerimaan solusi buruk menurun.

Probabilitas Boltzmann

P = exp(−Δ/T). Saat T tinggi → sering terima solusi buruk.

🧬 Genetic Algorithm

Terinspirasi evolusi biologis. Memelihara populasi jadwal dan menggunakan seleksi, crossover, serta mutasi untuk menghasilkan generasi yang semakin baik.

🧬

Kromosom

Satu jadwal mingguan lengkap (10 karyawan × 7 hari)

🏆

Seleksi Tournament

Ambil k kromosom acak, pilih yang fitness-nya tertinggi

✂️

Crossover

Single-point: gabungkan segmen dari dua jadwal induk

🎲

Mutasi

Ubah shift satu slot secara acak dengan probabilitas kecil

✅ Keunggulan: Jarang terjebak local optimum karena banyak solusi dicoba bersamaan setiap generasi. Elitisme memastikan solusi terbaik tidak hilang.

⚖️ Perbandingan Ketiga Algoritma

Aspek	🏔️ Hill Climbing	🌡️ Simulated Annealing	🧬 Genetic Algorithm
Jumlah solusi	1 solusi tunggal	1 solusi tunggal	Populasi banyak solusi
Local optimum	Mudah terjebak	Bisa lolos (probabilistik)	Jarang terjebak, banyak solusi dicoba bersamaan
Kecepatan	Paling cepat	Sedang	Paling lambat
Kualitas solusi	Tergantung titik awal	Lebih baik dari HC	Umumnya terbaik
Parameter	Sedikit (iterasi saja)	3 parameter	Banyak parameter

📝 Panduan Pengisian Parameter

Penjelasan setiap parameter beserta rekomendasi nilai yang bisa digunakan agar simulasi berjalan dengan baik.

🏔️ Parameter Hill Climbing

Varian

Pilih salah satu dari tiga varian:

Simple: paling cepat, cocok untuk eksplorasi awal. Gunakan ini jika ingin hasil cepat.
Steepest: lebih cermat karena membandingkan banyak pilihan. Hasilnya lebih konsisten tapi sedikit lebih lambat.
Stochastic: hasilnya acak tiap run, cocok untuk melihat variasi hasil. Butuh iterasi lebih banyak agar konsisten.

Jumlah Langkah

Nilai	Efek	Rekomendasi
500	Sangat cepat, cukup untuk Simple dan Steepest	Untuk tes awal
2000	Cukup untuk sebagian besar kasus	Penggunaan umum
5000	Konsisten optimal untuk semua varian termasuk Stochastic	Direkomendasikan

🌡️ Parameter Simulated Annealing

Eksplorasi Awal (T₀)

Mengontrol seberapa bebas algoritma mencoba jadwal yang lebih buruk di awal.

Nilai	Efek
1 - 5	Eksplorasi terbatas, cepat konvergen
10	Seimbang (direkomendasikan)
20 - 50	Eksplorasi sangat luas, butuh lebih banyak langkah

Kecepatan Fokus (alpha)

Seberapa cepat eksplorasi dikurangi tiap langkah. Nilai mendekati 1.0 artinya pendinginan lambat.

Nilai	Efek
0.90 - 0.95	Cepat fokus, butuh sedikit langkah
0.995	Lambat fokus, hasil lebih baik (direkomendasikan)
0.999	Sangat lambat, butuh banyak langkah

Batas Fokus (T_min)

Algoritma berhenti eksplorasi saat nilai ini tercapai. Nilai kecil artinya eksplorasi berlangsung lebih lama. Rekomendasi: 0.001 (default sudah optimal).

Jumlah Langkah

Batas maksimum percobaan sebagai pengaman. Rekomendasi: 3000. Nilai lebih kecil bisa membuat hasil tidak optimal.

🧬 Parameter Genetic Algorithm

Jumlah Solusi (Populasi)

Berapa banyak jadwal yang dicoba bersamaan setiap generasi.

Nilai	Efek
10 - 20	Cepat tapi kurang beragam
50	Seimbang (direkomendasikan)
100 - 200	Lebih beragam tapi lebih lambat

Jumlah Generasi

Berapa kali populasi berevolusi. Lebih banyak generasi artinya pencarian lebih panjang. Rekomendasi: 100. Biasanya sudah cukup untuk mencapai solusi optimal.

Peluang Kawin Silang

Seberapa sering dua jadwal digabung menjadi jadwal baru. Rekomendasi: 80%. Nilai terlalu rendah membuat evolusi lambat, terlalu tinggi mengurangi variasi.

Peluang Mutasi

Seberapa sering satu slot jadwal berubah secara acak. Rekomendasi: 2%. Nilai terlalu besar membuat pencarian terlalu acak dan sulit konvergen.

Solusi Terbaik Dijaga (Elitisme)

Berapa jadwal terbaik yang langsung dipertahankan ke generasi berikutnya tanpa diubah. Rekomendasi: 2. Memastikan solusi terbaik tidak hilang akibat mutasi.

Ukuran Seleksi (Tournament K)

Dari berapa kandidat acak dipilih satu induk terbaik. Rekomendasi: 3. Nilai lebih besar membuat seleksi lebih ketat tapi mengurangi keberagaman.

📊 Parameter Komparatif B.5

Maks. Iterasi

Batas langkah yang diberikan ke semua algoritma sekaligus untuk perbandingan yang adil.

Nilai	Efek	Keterangan
1000	Cepat, SA mungkin belum optimal	Untuk demo cepat
3000	Cukup untuk semua algoritma	Penggunaan umum
5000	Semua algoritma konsisten optimal	Direkomendasikan

Implementasi Genetic Algorithm pada Sistem Penjadwalan Shift Kerja

📖 Tentang Algoritma Optimasi

Deskripsi Problem

Constraint yang Harus Dipenuhi

📝 Panduan Pengisian Parameter

👥 Kelola Karyawan