Ahli Kumpulan

QUEK SOOK YEETIANG SIAO FOONG

Suatu cara penyelesaian masalah yang menggunakan cara penjelajahan serta cuba jaya.

Tidak memberi penyelesaian yang optimum.

Bin-packing - Objek-objek yang berlainan saiz dan isipadu disusun ke dalam kotak yang bersaiz lebih besar dengan muatan tertentu. - Proses ini cuba mendapat bilangan kotak besar yang minimum.

Algoritma ini pantas tetapi tidak memberikanpenyelesaian optimum.

Letakkan kotak pertama ke dalam ruang pertama tanpa sebarang susunan.Letakkan kotak kedua dalam ruang pertama, jika tidak muat, masukkan ke dalam ruang kedua.Ulangi langkah 2 sehingga semua kotak dimuatkan ke dalam ruang yang disediakan.

Susun semula kotak-kotak mengikut urutan menurun.Aplikasikan algoritma first-fit untuk susunan baru ini.

Lihat gabungan kotak-kotak untuk mengisi ruang tempat. (fill bins)Bungkuskan kotak-kotak ini (ikat bersama)Bagi yang tinggal, tempatkan kotak seterusnya dalam slot pertama yang sesuai mengisi kotak itu.

Contoh soalanJadual menunjukkan tempoh beberapa aktivitidalam satu projek.

Dengan menggunakan algoritma packingyang sesuai, tentukan bilangan pekerja yangdiperlukan untuk menyempurnakan tugas dalam12 hari.

AktivitiABCDEFGHIJTempoh(Hari)3736569498

Penyelesaian First-fit decreasing

Langkah 1: Susun semula tempoh(hari) secara turutan menurun.

9, 9, 8, 7, 6, 6, 5, 4, 3, 3

Langkah 2: Susun tempoh(hari) secaramenambah asalkan tempoh(hari) tidakmelebihi 12 hari.

P 19P 2987665433P 3P 4P 5P 6P 7Maka, dengan menggunakan kaedah first-fit decreasing jumlah pekerja yang diperlukan untuk menyempurnakan tugas ialah 7 orang.

Penyelesaian Full-binLangkah 1: Senaraikan tempoh(hari)mengikut urutan menaik.

Langkah 2: Cari dan tambahkan bilangantempoh(hari) yang tidak melebihi 12 hari.

P 1P 2P 3P 4P 59393847566Hanya memerlukan 5 orang pekerja 3, 3, 4, 5, 6, 6, 7, 8, 9, 9

Dapat dilihat jika dibandingkan penyelesaian dua algoritma di atas, penyelesaian algoritma Full-bin adalah lebih sesuai kerana ia dapat meminimumkan kos untuk menyempurnakan projek itu.