kuliah 10 - penjadwalan produksi

1/12/2011

1

Penjadwalan

Kuliah 10

LSiPro – FT Untirta

Muhammad Adha Ilhami


Tujuan Pembelajaran

• Mahasiswa mampu memahami konsep &

logika penjadwalan.

• Mahasiswa mampu membuat jadwal produksi


1/12/2011

2

Permasalahan Penjadwalan


• Masalah penjadwalan muncul di rumah sakit,

pabrik, universitas, airport, klinik, dll.

• Kadang pesanan (job/order) berbeda tapi

harus dikerjakan pada mesin/alat/orang yang

sama. Sehingga perlu diatur job mana yang

dikerjakan duluan dan mana yang belakangan.

Tipe Permasalahan Penjadwalan


1/12/2011

3

Model Penjadwalan


• Job Scheduling : hanya memecahkan masalah sequencing (urutan job) saja, karena ukuran job diketahui.

• Batch Scheduling : memecahkan masalah sequencing danpenentuan ukuran batch sekaligus.

Pendekatan Penjadwalan

• Forward Scheduling: penjadwalan maju yang dimulaisegera saat job siap (ready time);mulai dari time zero danbergerak searah dengan pergerakan waktu. Jadwaldipastikan feasible namun mungkin melewati due date.

• Backward Scheduling : penjadwalanmundur yang dimulaidari due date dan bergerak berlawanan arah waktu. Jadwalpasti memenuhi due date namun belum pasti feasible.

Ilustrasi


t = 0 t = 0

Due date Due date

Forward Scheduling Backward Scheduling

M

1

M

1

Single

Machine

Job 1

Job 2

t

Mana duluan?

Machine

NC

Machine

NC

Job 3

Job 1

Job 2

Job 3

Mana duluan dan di mesin mana?

Single Machine

Paralel/Heterogeneous Machine

1/12/2011

4

Terminologi dalam Penjadwalan

• Processing Time (waktu proses): estimasi waktupenyelesaian (job/task), ti.

• Setup time (waktu setup): waktu yang dibutuhkanuntuk kegiatan persiapan sebelum job diproses, si.

• Flow time (waktu tinggal): waktu antara saat datang(arrival time) dan saat kirim (delivery date), Fi.

• Arrival time (saat datang): saat job mulai berada dishop floor (production line), ai.

• Delivery date (saat kirim): saat pengiriman job darishop floor ke proses berikutnya atau ke konsumen, deli.

• Ready time (saat siap): saat sebuah job siap diproses, ri.• Due date (deadline): saat jika saat job selesai

melampaui waktu tersebut job dikatakan terlambat, di.



• Makespan: interval waktu total untuk penyelesaianseluruh job, completion time terbesar dari seluruh job.

• Completion time (saat selesai): saat suatu job selesaidiproses, ci.

• Lateness: deviasi antara saat selesai dan due date, Li = ci – di.

• Tardiness (Ti) = positive lateness, Earliness (Ei) = negative lateness.

• Slack: sisa waktu sampai due date, SLi =di – ti – saatsekarang.

• Loading: menggambarkan beban mesin• Schedule: menggambarkan urutan (sequence) dari job

yang akan dikerjakan (ada saat mulai dan saat selesai)


1/12/2011

5


• Waiting time: adalah waktu job menunggukarena mesin sedang mengerjakan job lain.

• Idle time: adalah waktu mesin tidak bekerjakarena tidak ada job yang harus dikerjakan.

• Priority rule: aturan penjadwalan berdasarkanprioritas tertentu. Seperti: FCFS (first come first serve), SPT (shortest processing time), LPT (longest processing time), EDD (earliest due date), CR (critical ratio)


Kriteria Penjadwalan

• Ada beberapa kriteria yang dapat digunakan dalammenentukan apakah suatu jadwal itu baik atau buruk, yaitu:

1. Minimasi shop time (waktu shop digunakan): minimize flow time, atau minimize makespan.

2. Maksimasi utilisasi shop floor (yaitu meminimasi idle time)

3. Minimasi WIP (work in process): minimize flow time atauminimize earliness.

4. Minimasi konsumen menunggu (maksimasi kepuasankonsumen): number of tardy jobs, mean lateness, maximum lateness, mean queue time.


1/12/2011

6

A. Permasalahan Single Machine : SPT


Job PiFlow time

1 10 10

2 8 18

3 14 32

4 5 37

5 3 40

Total Flow time 137

Mean Flow time 27,4

Job PiFlow time

5 3 3

4 5 8

2 8 16

1 10 26

3 14 40

Total Flow time 93

Mean Flow time 18,6

SPT

5 4 2 1 35421 3

t

B. Penjadwalan Single Machine: WSPT


Job PiBobot

(Wi)

P/W

1 10 1 10

2 8 3 2,67

3 14 2 7

4 5 2 2,5

5 3 1 3

JobBobot (Wi)

PiFlow time Weighted

flow time

4 2 5 5 10

2 3 8 13 39

5 1 3 16 16

3 2 14 30 60

1 1 10 40 40

Total 9 Total 104 165

Rata-rata 20,8 33

WSPT

1/12/2011

7

C. Penjadwalan Single Machine: EDD


Job Waktu Due

Date

Saat

Selesai

Lateness

1 10 12 10 -2

2 8 20 18 -2

3 14 18 32 16

4 5 17 37 20

5 3 3 40 37

Total 69

Rata-rata 13,8

Maximum 37

JobWaktu

Due

date

Saat Selesai Lateness

5 3 3 3 0

1 10 12 13 1

4 5 17 18 1

3 14 18 32 14

2 8 20 40 20

Total 36

Rata-rata 7,2

Maximum 20

EDD

Terbukti, EDD mampu meminimumkan maximum lateness.

D. Penjadwalan Single Machine:

Algoritma Hodgson


Algoritma Hodgson meminimumkan jumlah job yang tardy padasebuah mesin.

Langkah-langkah Algoritma Hodgson:

Step 1: Urutkan job dengan EDD, jika tidak ada atau hanya satu job yang tardy (positive lateness) maka stop. Jika lebih dari satu makalanjutkan ke langkah 2.

Step 2: Mulai dari awal sampai akhir dari urutan EDD, lakukanidentifikasi tardy job yang paling awal. Bila tidak tardy lanjutkan kestep 4. Jika ada, lanjutkan ke step 3.

Step 3: Jika job tardy berada di urutan ke-i, pilih job dengan waktuproses terpanjang di antara i buah job tersebut. Keluarkan job terpilih tersebut. Hitung saat selesai yang baru, dan kembali kestep 2.

Step 4: Tempatkan job yang dikeluarkan dalam urutan sembarang dibagian akhir urutan job.

1/12/2011

8

Contoh Algoritma Hodgson


i 2 1 3 5 4 6 7 8

ti 8 5 6 10 3 14 7 3

Ci 8 13 19 29 32 46 53 56

Di 10 15 15 20 25 40 45 50

Li -2 -2 4 9 7 6 8 6

Number of Tardy Jobs = 6 Jobs



i 1 3 5 4 6 7 8

Ti 5 6 10 3 14 7 3

Ci 5 11 21 24 38 45 48

Di 15 15 20 25 40 45 50

Li -10 -4 1 -1 -2 0 -2

1/12/2011

9



i 1 3 4 6 7 8

Ti 5 6 3 14 7 3

Ci 5 11 14 28 35 38

Di 15 15 25 40 45 50

Li -10 -4 -12 -12 -10 -12 No Positive Lateness

i 1 3 4 6 7 8 2 5

Ti 5 6 3 14 7 3 8 10

Ci 5 11 14 28 35 38 46 56

Di 15 15 25 40 45 50 10 20

Li -10 -4 -12 -12 -10 -12 36 36

Number of Tardy Jobs = 2 Jobs

Perbandingan Penjadwalan Single

Machine & Peruntukannya

Berdasarkan Kriteria Performansi


1/12/2011

10

I. Penjadwalan n Job Mesin Paralel:

SPT


Tujuannya : Meminimumkan flow time pada mesinparalel.

Step 1 Urut semua job dengan aturan SPT

Step 2 Jadwalkan job satu per satu pada mesin yang memiliki beban minimum. Bila beban sama pilihsembarang.

Job Pi

1 10

2 8

3 14

4 5

5 3

Contoh: ada 2 mesin paralel (sejenis) dan ada 5 job.

Urutan SPT

i 5 4 2 1 3

Pi 3 5 8 10 14

I. Penjadwalan n Job Mesin Paralel:

SPT


i 5 4 2 1 3

Pi 3 5 8 10 14

Machine

NC #1

Machine

NC #2

5

4

2

1

3

i Mesin #1 Mesin #2

i 5 2 3 4 1

Pi 3 8 14 5 10

FT 3 11 25 5 15

Mean Flow Time = (3 + 11 + 25 + 5 + 15)/5 = 11,8

1/12/2011

11

II. Penjadwalan n Job Mesin Serial


• Penjadwalan Flow Shop 2 mesin: Algoritma

Johnson (1956), solusi optimal.

• Penjadwalan Flow Shop m mesin: Algoritma

Campbell, Dudek, & Smith (CDS).

• Penjadwalan Job Shop

II.A. Penjadwalan Flow Shop 2 Mesin

Serial: Kriteria Minimasi Makespan


• Flow Shop, jumlah mesin > 1, urutan prosesseluruh job adalah sama.

• Asumsi:

� Setiap mesin hanya mampu memproses 1 job pada satu saat.

� Setiap job hanya bisa diproses di satu mesindi saat yang sama.

1/12/2011

12

II.A. Penjadwalan Flow Shop 2 Mesin

Serial : Algoritma Johnson


Step 1 Tentukan waktu proses terpendek dari daftar job.

Step 2 Ada tiga kondisi:

2.a Jika waktu terpendek ada di mesin 1, maka jadwalkan job tersebut

pada posisi paling kiri pada urutan yang dimungkinkan. Step 3

2.b Jika waktu terpendek ada di mesin 2, maka jadwalkan job tersebut

pada posisi paling kanan pada urutan yang dimungkinkan. Step 3

2.c Jika terdapat beberapa nilai waktu terpendek yang sama, maka

pilih sembarang, dan jadwalkan job tersebut di posisi paling kiri

atau kanan sesuai di mesin mana job tersebut memiliki waktu

proses terpendek. Step 3

Step 3 Keluarkan job yang sudah dijadwalkan dari daftar job. Bila

masih ada job yang belum dijadwalkan, maka kembali ke Step 1.

Jika seluruh job sudah dijadwalkan maka STOP.

Contoh Algoritma Johnson


Job 1 2 3 4 5

Mesin 1 10 8 14 5 3

Mesin 2 5 7 9 2 12

Machine

1

Machine

2

4

4

5

5

1

1

2

2

3

3

4

4

5

5

1

1

2

2

3

3

Makespan = 42

1/12/2011

13

II.B. Penjadwalan Flow Shop m Mesin

Serial : Algoritma CDS


Step 1 Set K = 1. Hitung ti,1* dan ti,2* (m = jumlah mesin)

Step 2 Gunakan Algoritma Johnson untuk penentuan urutan pekerjaan

dengan menyatakan ti,1 = ti,1* dan ti,2 = ti,2*.

Step 3 Hitung makespan untuk urutan tersebut. Catat Jadwal dan

makespan yang dihasilkan.

Step 4 Jika K = m – 1, maka pilih jadwal dengan makespan terpendek

sebagai jadwal yang digunakan, lalu STOP. Jika K = K + 1, maka

kembali ke Step 1.




Job 1 2 3 4 5

Mesin 1 10 8 14 5 3

Mesin 2 5 7 9 2 12

Mesin 3 8 6 12 7 5

Job K = 1

tm1 tm3

1 10 8

2 8 6

3 14 12

4 5 7

5 3 5K = m – 1 =3 – 1 = 2

Maka akan ada 2 iterasi dan menghasilkan 2 jadwal.

Iterasi 1

Step 1 - K = 1, waktu yang digunakan adalah waktu pada mesin 1

dan mesin 3 saja.

Step 2 – Lakukan penjadwalan dengan algoritma Johnson

Step 3 – Hitung makespan, dan catat nilai makespan tersebut.

1/12/2011

14




Urutan

Job

K = 1

tm1 tm3

5 3 5

4 5 7

3 14 12

1 10 8

2 8 6

Job 1 2 3 4 5

Mesin 1 10 8 14 5 3

Mesin 2 5 7 9 2 12

Mesin 3 8 6 12 7 5

No. JobStart Time

M1 M1Start Time

M2 M2Idle Time

M2Start Time

M3 M3 Idle Time M3 Finish Time1 5 0 3 3 12 3 15 5 15 202 4 3 5 8 2 0 17 7 0 273 3 8 14 22 9 5 31 12 4 434 1 22 10 32 5 1 37 8 0 515 2 32 8 40 7 3 47 6 0 57

Makespan 57

Step 4 – Karena K = 1 < 2, maka lanjutkan/kembali ke Step 1.




Job K = 2

Tm1+2 Tm2+3

1 15 13

2 15 13

3 23 21

4 7 9

5 15 17

Iterasi 2

Step 1 - K = 2, waktu yang digunakan adalah waktu

pada (mesin 1 + mesin 2) dan (mesin 2 + mesin 3).

Step 2 – Lakukan penjadwalan dengan algoritma

Johnson

Step 3 – Hitung makespan, dan catat nilai makespan

tersebut.

Urutan

Job

K = 2

Tm1+2 Tm2+3

4 7 9

5 15 17

3 23 21

2 15 13

1 15 13

1/12/2011

15




Job 1 2 3 4 5

Mesin 1 10 8 14 5 3

Mesin 2 5 7 9 2 12

Mesin 3 8 6 12 7 5

Step 4 – Karena K = 1+1 = 2, maka Stop.

Urutan

Job

K = 2

Tm1+2 Tm2+3

4 7 9

5 15 17

3 23 21

2 15 13

1 15 13

No. JobStart Time

M1 M1Start Time

M2 M2Idle Time

M2Start Time

M3 M3Idle Time

M3Finish Time

1 4 0 5 5 2 5 7 7 7 142 5 5 3 8 12 1 20 5 6 253 3 8 14 22 9 2 31 12 6 434 2 22 8 30 7 0 38 6 0 495 1 30 10 40 5 2 45 8 0 57

Makespan 57

III. Job Shop Scheduling


Job Shop : urutan pekerjaan tidak unidirectional.

Indeks yang umum digunakan dalam penjadwalan Job Shop adalah

indeks (i, j, k)

Dimana:

i : indeks job

j : indeks operasi

k : indeks mesin

M1 Mk

Finish Job

Finish Job

WIPWIP

New Job

New Job

WIP

1/12/2011

16

III. Jenis Job Shop Scheduling


Jenis Penjadwalan Job Shop:

1. Jadwal Semi Aktif

2. Jadwal Aktif*

3. Jadwal Non Delay.

* Optimal

SA A ND

III. Jenis Job Shop Scheduling:

Jadwal Aktif (Notasi)


PSt = Jadwal parsial yang terdiri dari t buah operasi terjadwal

St = Set/kumpulan operasi yang dapat dijadwalkan pada stage t,

setelah diperoleh PSt.

σt = Waktu tercepat operasi J Є St dapat dimulai

Фt = Waktu tercepat operasi J Є St dapat diselesaikan

1/12/2011

17


Algoritma Jadwal Aktif


Step 1 Tentukan t = 0, dan kemudian mulai dengan PS0 sebagai jadwal parsial nol.

Tentukan seluruh operasi tanpa predecessor sebagai S0.

Step 2 Tentukan ф* = minjЄSt {фj} dan mesin m* yaitu mesin tempat ф* dapat

direalisasikan.

Step 3 Untuk setiap operasi j Є St yang membutuhkan mesin m* dan berlaku σj <

ф*, buat jadwal parsial baru dengan menambahkan operasi j pada PSt

dengan saat mulai operasi pada σj .

Step 4 Untuk setiap jadwal parsial baru PSt+1, yang dihasilkan pada step 3,

perbaharui set data berikut:

� Keluarkan operasi j dari St.

� Tambahkan suksesor langsung operasi j ke dalam St+1.

� Naikkan nilai t dengan 1.

Step 5 Untuk setiap PSt+1 yang dihasilkan pada Step 3, kembali ke step 2.

Lanjutkan langkah ini sampai seluruh job terjadwalkan.


Contoh Permasalahan Jadwal Aktif


Misalkan secara sembarang diusulkan jadwal dengan urutan 4 – 3 – 2 – 1, maka

dihasilkan Gantt Chart sbb:

1/12/2011

18


Penyelesaian Jadwal Aktif (1)





1/12/2011

19




6 9




1/12/2011

20




9 2




1/12/2011

21




kuliah 10 - penjadwalan produksi

Documents