1

Pertemuan 16Flow Shop Scheduling

Matakuliah : T0034/Analisis & Perancangan Algoritma

Tahun : 2005

Versi : 1/0

2

Learning Outcomes

Pada akhir pertemuan ini, diharapkan mahasiswa

akan mampu :

• << TIK-99 >>

• << TIK-99>>

3

Outline Materi

• Materi 1

• Materi 2

• Materi 3

• Materi 4

• Materi 5

4

Flow Shop Scheduling

Suatu job i diproses dalam waktu Tij, j>1 tidak dapat diproses sebelum job yang waktu prosesnya Tj-1,i selesai.

The finish time fi(s) suatu job i adalah waktu yang diperlukan oleh job i pada schedule s.

The mean flow time didefinisikan sebagai

dimana n banyaknya job yang akan diselesaikan

n

1i

(s) fin

1(s) MFT

5

Contoh 1

Misalkan n=4, ( a1, a2, a3, a4 ) = ( 3, 4, 8, 10 ) dan ( b1, b2, b3, b4 ) = ( 6, 2, 9, 15)

Deretan terurut dari a dan b adalah = ( b2, a1, a2, b1, a3, b3, a4, b4 ) = ( 2, 3, 4, 6, 8, 9, 10, 15 ).

Misalkan 1, 2, 3, 4 adalah schedule optimal dan karena bilangan terkecil adalah b2, tetapkan 4 = 2. Maka bilangan berikut adalah a1 dan set 2 = a1 dan seterusnya, maka 3 = 4.

Schedule diatas dapat di implementasikan, dengan waktu proses

6

Contoh 2

misalkan 2 job diproses pada 3 prosessor. Waktu proses dinyatakan dengan matriks

Yang dapat di jadwalkan dengan dua cara, seperti pada gambar 5.15 (a) dan (b) pada buku : Fundamental of Computer Algorithms oleh Ellis Horrowitz dan Sakni Sartaj hal 234.

2 5

3 3

0 2

j

7

Flow Shop Scheduling contd’

Fi (s) = waktu penyelesaian total job i

F(s) = waktu penjadwalan pada schedule s

Waktu proses rata-rata

OFT = Optimal Finish Time Schedule dari set job dalam non preemptive schedule s

POFT = Preemptive Optimal Finish Time Schedule

OMFT = Optimal Mean Finish Time Schedule

POMFT = Preemptive Optimal Finish Time

(s)}{fF(s) ini1Max

ni1 i(s)f

n1MFT(s)

8

Flow Shop Scheduling contd’

Pada problema dengan banyak job (m > 2), maka untuk OFT, POFT dan OMFT sangat sukar dan ini termasuk NP-hard dan NP- Complete problem.

Disini ditinjau untuk m=2

Lihat contoh 5.25 pada buku tersebut diatas halaman 238.

)nlogn( 2

9

Reabilitas Rancangan (Reability Design)

Problemnya adalah merancang suatu sistem yang merupakan gabungan dari beberapa alat yang dihubungkan secara serie, seperti pada gambar 5.12 dan 5.13 pada buku Fundamental of Computer Algorithms oleh Ellis Horrowitz dan Sakni Sartaj, halaman 228.

Fungsi objektive-nya :

dengan kendala

dan mi 1 bilangan bulat serta 1in

mi = duplikat dari alat Dici = Cost dari tiap unit alat IC = Cost maksimum yang diijinkan

(mi)φn Maksimumka ini1

Π

n i 1

ii cmc

10

Contoh seperti pada contoh 5.23 pada buku tersebut diatas halaman 230.

End of Pertemuan 16