Tugas algoritma 2

-
Penjadwalan Brute Force

4) Kasus: Menyusun Jadwal Kerja (Scheduling)

Cerita:
Ada 5 pekerjaan yang harus dikerjakan 1 mesin secara berurutan (tidak bisa paralel).
Setiap pekerjaan memiliki waktu pengerjaan (durasi) dan bobot kepentingan.
Kita ingin menentukan urutan pekerjaan agar total “waktu selesai × bobot” sekecil mungkin.

Data pekerjaan (durasi, bobot):

  • A: (3 jam, bobot 4)
  • B: (2 jam, bobot 2)
  • C: (5 jam, bobot 10)
  • D: (1 jam, bobot 1)
  • E: (4 jam, bobot 3)

Tujuan:
Cari urutan pekerjaan yang meminimalkan total “waktu selesai × bobot”.

Metode Brute Force

Brute force mengevaluasi seluruh urutan yang mungkin (5! = 120 urutan).
Untuk setiap urutan (j₁,…,j₅):

  1. Hitung waktu kumulatif Cjₖ = Σ pjₜ
  2. Hitung nilai objektif: Z = Σ wjₖ × Cjₖ
  3. Pilih urutan dengan Z terkecil

Perhitungan Hasil Terbaik

Dari evaluasi seluruh 120 permutasi, nilai minimum Σ wjCj adalah 158. Terdapat dua urutan optimal dengan hasil sama:

Urutan 1: C → A → B → D → E

  • C: CC=5 → 10×5=50
  • A: CA=8 → 4×8=32
  • B: CB=10 → 2×10=20
  • D: CD=11 → 1×11=11
  • E: CE=15 → 3×15=45
  • Total = 158

Urutan 2: C → A → D → B → E

  • C: CC=5 → 50
  • A: CA=8 → 32
  • D: CD=9 → 9
  • B: CB=11 → 22
  • E: CE=15 → 45
  • Total = 158

B dan D dapat dipertukarkan karena rasio p/w sama (=1), sehingga kedua urutan sama-sama optimal.

Kesimpulan

Urutan pekerjaan optimal: C – A – B – D – E atau C – A – D – B – E.
Nilai minimum: Σ wjCj = 158.

Komentar

Posting Komentar

Postingan populer dari blog ini

TUGAS IMK 01

-
Gambar
Bagian 1: Tulis masalah dari lampu merah yang ada sekarang. lalu berikan solusi anda. Masalah yang Ditemui pada Lampu Merah Konvensional: Count down error – penghitung mundur waktu pada lampu lalu lintas sering mengalami error atau bahkan mati. Sistem sering tidak berfungsi – lampu bisa padam atau stuck pada satu warna sehingga membahayakan pengguna jalan. Akurasi waktu tidak seimbang – durasi lampu hijau, kuning, dan merah sering tidak sesuai dengan kepadatan lalu lintas aktual. Salah posisi / terhalang objek – letak lampu kadang tertutup oleh pepohonan, papan reklame, atau bangunan. Kurang informatif – hanya menampilkan warna dasar tanpa informasi tambahan yang dapat membantu pengendara. Tidak ramah bagi pejalan kaki – minim fitur khusus bagi penyebrang jalan, misalnya tombol khusus atau suara pemandu. Solusi yang Dapat Diberikan: Perbaikan sistem penghitung mundur dengan integrasi sensor digital yang lebih stabil. Backup daya (UPS/solar panel)...
Baca selengkapnya

Tugas 3 algoritma

-
Gambar
Pemecahan Kasus Di kasus ini, kita punya 5 pekerjaan yang harus diselesaikan secara berurutan di satu mesin. Setiap pekerjaan punya durasi (jam) dan bobot penting . Tujuannya adalah mencari urutan kerja supaya total  ∑ ( w a k t u   s e l e s a i × b o b o t ) \sum (waktu\ selesai \times bobot) ∑ ( w ak t u   se l es ai × b o b o t ) jadi sekecil mungkin. Kalau dikerjakan sembarangan, hasilnya bisa lebih besar. Jadi kita pakai strategi algoritma greedy . Algoritma ini menyarankan supaya kita mengurutkan pekerjaan berdasarkan rasio bobot per durasi (w/p) . Alasannya sederhana: semakin besar bobot dibandingkan waktu, semakin penting pekerjaan itu untuk dikerjakan lebih cepat. Langkah-langkah Bayangin kita lagi dapat tugas: ada 5 pekerjaan yang harus diselesaikan di satu mesin, dan semuanya harus dikerjakan satu per satu . Setiap pekerjaan punya dua informasi penting: Durasi (p) : berapa lama pekerjaan itu butuh waktu, Bobot (w) : seberapa penting pekerjaan itu....
Baca selengkapnya