TUGAS 3

Soal:

1. 4 orang karyawan diberi tugas untuk 4 pekerjaan. Diketahui bahwa waktu yang
diperlukan setiap pekerjaan adalah sebagai berikut:

Karyawan Pekerjaan/ Tugas (Hari)

A B C D
a 15 18 21 24
b 19 23 22 18
c 26 17 16 19
d 19 21 23 17

Tentukan alokasi penugasan yang akan meminimumkan jumlah waktu yang diperlukan
(anggap semua karyawan dibayar dengan tingkat yang sama, bila tidak, biaya
seharusnya juga dipertimbangkan)

2. Carilah jalur kritis rangkaian kegiatan-kegiatan dibawah ini dan buatlah jaringannya
terlebih dahulu:
Kegiatan Lama waktu Kegiatan Lama waktu
(dalam hari) (dalam hari)
1–2 6 5–8 7
1–3 4 5 – 10 8
1–4 5 6–7 7
2–5 7 6–9 3
2–7 6 7 – 10 9
3–5 8 7–8 3
3–7 10 8 – 11 8
4–6 4 9 – 10 6
10 – 11 5

3. Diketahui, sebuah proyek pembangunan jembatan diberikan tenggat waktu

penyelesaian selama 16 minggu dan ditargetkan akan selesai selama 15 minggu. Jalur
kritis proyek ini terdiri dari aktifitas A, C, E, G, dan H. Dengan mengacu pada data
berikut ini, tentukan probabilitas waktu penyelesaian proyek.
Dalam memecahkan masalah penugasan (assignment problem) di atas, kitamenggunakan
metode alokasi yang dikenal dengan namaHungarian [Link]-langkah penyelesaian
masalah alokasi sebagai berikut :

a. Pertama, memodifikasi matriks waktu (biaya) dan mengurangi dengan

waktuterkecil (bukan nol) dalam setiap kolom dari sleuruh sel dalam kolom itu
untukmendapatkan paling sedikit satu angka nol dalam setiap kolom.(Dalam
mempermudah pengerjaan, maka dipergunakan simbol) :

Karyawan Pekerjaan/ Tugas (Hari)

A B C D
a 0 1 5 7
(15-15) (18-17) (21-16) (24-17)
b 4 6 6 1
(19-15) (23-17) (22-16) (18-17)
c 11 0 0 2
(26-15) (17-17) (16-16) (19-17)
d 4 4 7 0
(19-15) (21-17) (23-16) (17-17)

b. Dalam setiap baris, waktu terkecil (bukan nol) dipakai untuk mengurangiseluruh
sel dalam baris itu. Ini hanya dilakukan pada baris kedua karenasemua baris
lainnya telah mempunyai angka nol. Bila langkah pertama telahmenghasilkan
paling sedikit satu angka nol adalah setiap baris, langkah keduadapat dihilangkan.
c. Sekarang tarik sejumlah minimum garis yang akan meliput semua angka
nol(perhatikan garis biru yang ditarik berdasarkan pada sel yang ada angkanol).
Dalam matriks di atas, tiga garis telah mencukupi. Bila ada jumlah garisyang
sama dengan jumlah baris atau kolom, alokasi optimal mungkin [Link] tidak,
matriks harus diubah. Di sini ada tiga garis dibanding empat barisatau kolom,
sehingga langkah berikutnya diperlukan.
Karyawan Pekerjaan/ Tugas (Hari)
A B C D
a 0 1 5 7

b 3 5 5 0
(4-1) (6-1) (6-1) (1-1)
c 11 0 0 2

d 4 4 7 0

d. Seluruh sel yang belum terliput garis-garis dikurangi dengan sel terkecil
yangbelum terlalui (yaitu 3). Kemudian tambahkan dengan jumlah yang sama
keelemen-elemen yang ada pada garis-grais silang (7 dalam garis a, dan 2
Problem halaman 3dalam garis c), sehingga nilaninya menjadi 10 dan 5. Masukkan
hasil-hasil ini pada matriks dan menyelesaikan matriks dengan seluruh elemen-
elemen yangtelah terliput tanpa perubahan.
 e. Ulangi langkah ketiga; sekali lagi, hanya ada tiga garis yang meliput angkanol
(0). Oleh ebab itu, ulangi langkah keempat, dan mendapatkan empat garisyang
meliput seluruh angka nol (0). Jadi, dapat dihasilkan matriks optimal

Karyawan Pekerjaan/ Tugas (Hari)

A B C D
a 0 1 5 10
(7+3)
b 0 2 2 0
(3-3) (5-3) (5-3) (1-1)
c 11 0 0 5
(2+3)
d 1 1 4 0
(4-2) (4-3) (7-3)

Karyawan Pekerjaan/ Tugas (Hari)

A B C D
a 0 0 4 10
(1-1) (5-1) (7+3)

b 0 1 1 0
(3-3) (2-1) (2-1) (1-1)
c 12 0 0 6
(11+2) (5+1)

d 1 0 3 0
(4-2) (1-1) (4-1)

f. Buat alokasi tugas yang nyata, mulai dengan angka nol yang khas dalam barisatau
kolom. (Bila tidak ada angka nol tersebut, mulai dengan sembarangangka nol).
Dari hasil tersebut adalah cC. Penyelesaian alokasi ini muncul 2(dua)
kemungkinan yang dapat ditunjukkan dengan lingkaran garis merah danbiru.

Kemungkinan 1 : cC, aA, bD, dB ; waktu yang diperlukan adalah

= 16 + 15 + 18 + 21 = 70 hari

Kemungkinan 2 : cC, aB, bA, dD ; waktu yang diperlukan adalah=

16 + 18 + 19 + 17 = 70 hari