Tugas algoritma 4
Kasus: Ada 5 pekerjaan yang harus dikerjakan oleh satu mesin secara berurutan. Karena mesin hanya bisa mengerjakan satu pekerjaan dalam satu waktu, kita perlu menentukan urutan pengerjaan yang menghasilkan total biaya paling kecil. Biaya dihitung dari bobot pekerjaan dikali waktu selesai pekerjaan tersebut. Data pekerjaan: A = (durasi 3 jam, bobot 4) B = (durasi 2 jam, bobot 2) C = (durasi 5 jam, bobot 10) D = (durasi 1 jam, bobot 1) E = (durasi 4 jam, bobot 3) Jawab: Seorang operator ingin menjadwalkan kelima pekerjaan ini. Ia mencoba menggunakan pendekatan DFS. Dengan cara ini, ia menelusuri semua kemungkinan urutan pengerjaan, dari awal sampai akhir, lalu menghitung biaya setiap urutan. Setelah semua dicoba, ia bisa tahu urutan mana yang paling efisien. Langkah-langkah DFS: Mulai dari daftar kosong. Pilih salah satu pekerjaan yang belum dipilih, tambahkan ke daftar. Hitung waktu selesai sementara dan biaya yang ditambahkan. Ulangi proses sampai semua pekerjaan ...