departemen teknik industri fti-itb hasil pembelajaranmahasiswa mampu menerapkan model matematik,...

1

Departemen Teknik Industri FTI-ITB

TI-3122 Perencanaan dan Pengendalian Produksi

Penjadwalan Produksi

Laboratorium Sistem Produksiwww.lspitb.org

©2003

TI3122-Perencanaan dan Pengendalian Produksi - Minggu 6 2


Hasil Pembelajaran

• UmumMahasiswa mampu menerapkan model matematik, heuristik dan teknik statistik untuk menganalisis danmerancang suatu sistem perencanaan dan pengendalianproduksi

• KhususMemahami konsep penjadwalan produksi serta mampumenyusun jadwal produksi

2



Pendahuluan

• Masalah penjadwalan muncul di berbagai macamkegiatan: rumah sakit, universitas, airline, factory

• Output MRP adalah planned order releases

• Terdapat order-order yang berbeda tetapi harusdiproses pada mesin yang sama



Model Penjadwalan (1)

Penjadwalan

Single stage

Multiple stages

Single machine

Parallel/heterogeneous machines

Flow shop

Job shop

Job

Batch

3



Model Penjadwalan(2)

• Job scheduling (memecahkan masalahsequencing saja, karena ukuran job telahdiketahui)

n jobs on 1 processorn jobs on m-parallel processorsFlow shop schedulingJob shop scheduling

• Batch scheduling (memecahkan masalahpenentuan ukuran batch dan masalah sequencing secara simultan)

Single stage

Multiple stages



Pendekatan

• Forward scheduling(penjadwalan maju): penjadwalan yang dimulai segera setelah saat job siap; mulai dari time zero dan bergerak searahdengan pergerakan waktu. Jadwal pasti feasible tapi mungkin melebihi due date.

• Backward scheduling (penjadwalan mundur): penjadwalan mulai dari date date dan bergerakberlawanan arah dengan arah pergerakan waktu. Jadwal pasti memenuhi due date tapi mungkintidak feasible

4



Terminologi(1)

• Processing time (waktu proses): estimasi waktupenyelesaian pekerjaan (job, task), ti

• Setup time (waktu setup): waktu yang dibutuhkan untuk kegiatan persiapan sebelumpemrosesan job dilaksanakan. Sequence dependent and independent setup times. si

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

• Saat datang adalah saat job mulai berada di shop floor (production line), ai



Terminologi(2)

• Delivery date (saat kirim): saat pengiriman job dari shop floor ke proses berikut atau ke konsumen, di

• Ready time (saat siap): saat sebuah job siap diproses.• Due date: saat batas (deadline) untuk job, yang setelah

batas tersebut job dinyatakan terlambat, di• Makespan: interval waktu total untuk penyelesaian seluruh

job• Completion time (saat selesai): saat suatu job selesai

diproses, ci• Lateness: deviasi antara saat selesai dan due date, Li = ci -

di• Tardiness (Ti): positive lateness. Earliness (Ei): negative

lateness

5



Terminologi(3)

• Slack: sisa waktu sampai due date, SLi = di - ti –saat sekarang Gantt chart: adalah peta visual yang menggambarkan loading dan scheduling

• Loading menggambarkan beban mesin

• Schedule menggambarkan urutan (sequence) pemrosesan job, dan menggambarkan saatdimulai dan saat selesai suatu pekerjaan

• Dalam bidang penelitian scheduling, schedule dansequence biasanya mempunyai pengertian yang dapat dipertukarkan (schedule = sequence)



Terminologi(4)

• Waiting time adalah waktu job menunggu karenamesin yang seharus memproses job tersebutsedang memproses job lain

• Idle time adalah waktu mesin tidak bekerja(menganggur) karena tidak ada job yang harusdiprosesPriority rule: aturan penentuan prioritaspemrosesan

• Priority rules: FCFS (first come first serve); SPT (shortest processing time), LPT (longest processing time), EDD (earliest due date); rasiokritis (critical ratio, CR). CR = (due date –today’s date)/(lead time remaining) atau CR = (due date – today’s date)/(workdays remaining)

6



Terminologi(5)

• Kriteria penjadwalan:

Minimasi shop time: flow time, makespan

Maksimasi utilization (minimasi idle time)

Minimasi WIP (work in process): Minimasi flow time, minimasi earliness

Minimasi customer waiting time: number of tardy jobs, mean lateness, maximum lateness, mean queue time



Terminologi(6)

• Suatu variant dalam batch scheduling problems adalah lot streaming.

• Lot streaming adalah suatu teknik untukmempercepat aliran pengerjaan (the flow of work) dengan menentukan transfer lots, yaitulot untuk membawa sebagian part (dari suatubatch yang terdiri part yang identik) yang sudahselesai diproses di suatu mesin (upstream machine) ke mesin berikut (downstream machine). Tujuan lot streaming adalah untukmemperpendek makespan dan sekaligus flow time (yang berarti meminimumkan inventory).

7



Penjadwalan n jobs pada single machine(1)

• Aturan SPT (shortest processing time) untukmeminimumkan waktu tinggal (flow time) rata-rata:

• Flow time rata-rata akan minimum bila n jobs yang akan diproses pada sebuah mesin diurutmenurut waktu pemrosesan terpendek (shortest processing time, SPT), yaitu:

[ ] [ ] [ ] [ ]nn tttt ≤≤≤≤ −121 ...




Waktuproses

1 52 83 64 35 106 147 78 3

Job Waktuproses

4 38 31 53 67 72 85 106 14

Job

Urutan yang dihasilkan: 4-8-1-3-7-2-5-6

Flow time rata-rata: 23,875

3

6

11

17

24

32

42

56

19123.875

Flow tim e

FF

8




Gantt chart

4 8 1 3 7 2 5 6

Makespan = 56

Waktuproses

4 3 3

8 3 6

1 5 11

3 6 17

7 7 24

2 8 32

5 10 42

6 14 56

Total 191Rata-rata 23.875

Job Flow tim e




• Aturan WSPT (Weighted shortest processing time):

• Bila terdapat n jobs yang akan diproses di sebuahmesin dan setiap job mempunyai bobot Wi, makarata-rata flow time akan minimum bila job tersebut diurut menurut:

[ ]

[ ]

[ ]

[ ]

[ ]

[ ]

[ ]

[ ]n

n

n

n

Wt

Wt

Wt

Wt

≤≤≤≤−

−

1

1

2

2

1

1 ...

9




Waktuproses

1 5 1 52 8 2 43 6 3 24 3 1 35 10 2 56 14 3 4.77 7 2 3.58 3 1 3

Job Boboti

i

Wt

Urutan yang dihasilkan: 3-4-8-7-2-6-1-5Flow time rata-rata: 27,0Flow time tertimbang rata-rata: 27,46667

W eightedFlow tim e

3 3 6 6 18

4 1 3 9 9

8 1 3 12 12

7 2 7 19 38

2 2 8 27 54

6 3 14 41 123

1 1 5 46 46

5 2 10 56 112

Total 15 Total 216 412Rata-rata 27 27.46667

Job B ob W aktu Flow tim e




• Aturan SPT meminimumkan mean lateness

• Bila terdapat n jobs yang akan diproses di sebuahmesin, maka mean lateness akan minimum bilajobs tersebut diurut menurut aturan SPT

1 5 152 8 103 6 154 3 255 10 206 14 407 7 458 3 50

Job Waktu Due date

10




Saat LatenesssSelesai c-d

4 3 25 3 -228 3 50 6 -441 5 15 11 -43 6 15 17 27 7 45 24 -212 8 10 32 225 10 20 42 226 14 40 56 16

Total -29Rata-rata -3.625

Job Waktu Due date

Maximum lateness: 22




• Aturan EDD (earliest due date)

• Aturan EDD meminimumkan maximum lateness pada sebuah mesin

Saat LatenesssSelesai c-d

2 8 10 8 -21 5 15 13 -23 6 15 19 45 10 20 29 94 3 25 32 76 14 40 46 67 7 45 53 88 3 50 56 6

Total 36Rata-rata 4.5

Job Waktu Due date

Maximum lateness:9

11




• Algoritma Hodgson meminimumkan jumlah job yang tardy pada sebuah mesin

Step 1. Urut semua job sesuai EDD; bila tidak ada atau hanyasatu job yang tardy (positive lateness) maka stop. Bila lebihdari sebuah maka lanjutkan ke Step 2Step 2. Mulai dari awal sampai akhir job pada urutan EDD, identifikasi tardy job yang paling awal. Bila tidak tardy job maka lanjutkan ke Step 4. Bila ada, maka lanjutkan ke Step 3Step 3. Misal tardy job tersebut berada di urutan ke i. Pilih job yang mempunyai waktu proses terpanjang di antara i buah job tersebut. Keluarkan job terpilih tersebut. Hitung saat selesaiyang baru, dan kembali ke Step 2.Step 4. Tempatkan job yang dikeluarkan dalam urutansembarang di ujung belakang urutan




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

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

12




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 -11 -12 -10 -12

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 -11 -12 -10 -12 36 36

Jumlah tardy job: 2Rata-rata lateness adalah 1,625, dan maximum lateness adalah 36




Mean Flow Weighted Mean Maximum No. of MeanRule Time Mean Flow Lateness Lateness Tardy Tardiness

Time JobsSPT 23,875 29 -3,625 22 4 7,75

WSPT 27 27,467 -0.5 36 4 10,625EDD 32 31733 4,5 9 6 5Slack 32,125 31,133 4,625 9 6 5

Hodgson 29,125 29,867 1,625 36 2 9Wilkerson 28,875 30,667 1,375 16 3 4

Perbandingan perfomansi scheduling rule

13



Penjadwalan n jobs, parallel machines(1)

• Algoritma meminimkan mean flow timr padamesin paralel

Step 1. Urut semua jobs dengan urutan SPTStep 2. Jadwalkan job tersebut satu per satu padamesin yang memiliki beban minimum. Bila beban mesinsama, pilih sembarang mesin

i 1 2 3 4 5 6 7 8 9 10ti 5 6 3 8 7 2 3 5 4 2

i 6 10 3 7 9 1 8 2 5 4

ti 2 2 3 3 4 5 5 6 7 8

Urutan SPT




i 6 10 3 7 9 1 8 2 5 4

ti 2 2 3 3 4 5 5 6 7 8

M1

M2

M3 3 1 5

2910

6 7 8 4

14




Job W aktu Flow tim e Job W aktu Flow tim e Job W aktu Flow tim e

6 2 2 10 2 2 3 3 3

7 3 5 9 4 6 1 5 8

8 5 10 2 6 12 5 7 15

4 8 18

Total 35 20 26

Rata-rata 8.75 6.666667 8.666667

Rata-rata flow time: 8,01

Makespan: 18

M1 M2 M3




2. Algoritma meminimumkan sekaligus mean flow time danmakespan pada mesin paralel

15



Penjadwalan n jobs, serial machines

• Penjadwalan job shop• Kriteria: minimasi makespan• Flow shop 2 mesin: Algoritma Johnson (1956),

optimal• Flow shop m mesin: Algoritma Campbell, Dudek

dan Smith (CDS)• Urutan pemrosesan n job di seluruh mesin adalah

sama• Panjang makespan ditentukan dengan membuat

Gantt chart untuk jadwal terpilih: Setiap job hanya diproses di satu mesin pada saat yang sama, dan setiap mesin hanya memprosessebuah job pada saat yang sama



Algoritma Johnson(1)

• Step 1. Tentukan waktu proses yang terpendek diantara seluruh job dalam daftar job yang akandiproses

• Step 2a. Bila waktu proses terpendek berada dimesin M1, maka jadwalkan job dengan waktuterpendek itu pada posisi paling kiri pada urutanyang dimungkinkan, dan lanjutkan ke Step 3.

• Step 2b. Bila waktu proses terpendek berada dimesin M2, maka jadwalkan job dengan waktuterpendek itu pada posisi paling kanan padaurutan yang dimungkinkan, dan lanjutkan keStep 3.

16




• Step 2c. Bila terdapat beberapa nilai waktuproses terpendek, maka pilih sembarang; danjadwalkan job dengan waktu proses terpilih diposisi paling kiri atau kanan sesuai dengankeberadaan waktu proses terpilih tersebut.

• Step 3. Keluarkan job yang sudah dijadwalkandari daftar job. Bila masih ada job yang belumdijadwalkan, maka kembali ke Step 1. Bilaseluruh job sudah dijadwalkan maka stop.




Job

tj1

tj2

Job1 Job2 Job3 Job4 Job5

3 5 1 6 7

6 2 2 6 5

Job3 Job1 Job4 Job5 Job2

31 4 5 2

2541324

M=24

17



Algoritma Campbel, Dudek and Smith(1)

Step 1. Set K=1. Hitung (m=jumlah mesin):

Step 2. Gunakan Algoritma Johnson untuk penentuan urutanpekerjaan dengan menyatakan

∑=

=K

kkii tt

1,

*1,

∑=

+−=K

kkmii tt

11,

*2,

*1,1, ii tt =*

2,2, ii tt =




• Step 3. Hitung makespan untuk urutan tersebut. Catat jadwal dan makespan yang dihasilkan

• Step 4. Jika K=m-1 maka pilih jadwal denganmakespan terpendek sebagai jadwal yang digunakan, lalu stop. Jika K<m-1 maka K=K+1 dan kembali ke Step 1.

18




Job iM esin 1 M esin 2 M esin 1 M esin 2

1

2

3

4

5

6

K=1 K=2Job i M esin 1 M esin 2 M esin 3

1 4 3 5

2 3 3 4

3 2 1 6

4 5 3 2

5 6 4 7

6 1 8 3



Job shop scheduling(1)

• Flow shop: aliran kerja unidirectional• Job shop: aliran kerja tidak unidirectional

MkIn process jobs In process jobs

New jobs

Completed jobs

19




• Flow shop: Indeks (i, j)

Job M1 M2 Mm…

J1J2

Jn

…

…………

… … …………

… ………

Waktu proses

• Job shop: Indeks (i, j, k)

Waktu operasi ke j untuk pemrosesan job i di mesin k

job operasi mesin

tijk

tij: Waktu proses job i di mesin j




Operasi 1 Operasi 2 Operasi 3Job J1 4 3 2Job J2 1 4 4Job J3 3 2 3Job J4 3 3 1

W aktu Proses


Routing

t233 = 4 t31… = 33 1= t431

20



Geser-kiri (left-shift)

• Geser-kiri lokal (local left-shift)penyesuaian (menjadi lebih cepat) saat mulai (start time) suatuoperasi dengan tanpa mengubah urutan

• Gese-kiri global (global left-shift)penyesuaian sehingga suatu operasi dimulai lebih cepat tanpamenyebabkan delay operasi lain



Jenis jadwal pada job shop(1)

1. Jadwal semiaktifadalah satu set jadwal yang tidak memungkinkan lagi untukmelakukan geser-kiri lokaladalah satu set jadwal yang tidak memiliki superfluous idle time

Superfluous idle time terjadi pada jadwal yang apabila suatu operasidimulai lebih awal tidak menyebabkan perubahan urutan padamesin manapun

21





W aktu Proses


Routing

4

3

3

3

4

4

2

2

2

1

1

1

M1

M2

M3

Misal urutan job adalah 4-3-2-1:




4

3

3

3

4

4

2

2

2

1

1

1

M1

M2

M3

Geser-kiri lokal tidak bisa dilakukan (menggeser saat mulaitanpa mengubah urutan)

Saat mulai operasi (1,1,1) bisa dilakukan tanpa menyebabkandelay pada operasi lain (tapi harus mengubah urutan)

1

1

1

1

1

1

22




2. Jadwal Aktifadalah satu set jadwal yang tidak memungkinkan lagi untukmelakukan geser-kiri global

3. Jadwal non-delayadalah jadwal aktif yang tidak membiarkan mesin menjadi idlebila suatu operasi dapat dimulai




All schedule

SA A ND*

* SA = semiactive

A = active

ND = non-delay

* = optimal

23



Algoritma Pembangkitan Jadwal Aktif(1)

PSt = Jadwal parsial yang terdiri t buah operasi terjadwalSt = Set operasi yang dapat dijadwalkan pada stage t, setelah

diperoleh PSt

σt = Waktu tercepat operasi dapat dimulaiφt = Waktu tercepat operasi dapat diselesaikan

Berikut adalah algoritma untuk mendapatkan/membangkitkan salahsatu jadwal aktif

tSj∈tSj∈




Step 1. Tentukan t=0, dan kemudian mulai dengan PS0 sebagaijadwal parsial nol. Tentukan seluruh operasi tanpa predecessorsebagai S0.

Step 2. Tentukan dan mesin m* yaitu mesintempat φ* dapat direalisasikan

Step 3. Untuk setiap operasi yang membutuhkan mesin m*

dan berlaku , buat jadwal parsial baru denganmenambahkan operasi j pada PSt dengan saat mulai operasi padaσj

{ }jSj tφφ ∈= min*

tSj∈*φσ <j

24




Step 4. Untuk setiap jadwal parsial baru PSt+1, yang dihasilkan padaStep 3, perbaharui (up date) 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 keStep 2. Lanjutkan langkah-langkah ini sampai suatu jadwal aktifdihasilkan.



Jadwal Aktif(1)

MesinStage 1 2 3 st σj tij φj φ* m* PSt

0 0 00 111212313412

0 40 10 30 3

4133

1 2212

1 0 1 0221313412

0101

4433

4534

3 3

313111

25



Jadwal Aktif(2)


0 1 32 111221322412

0 41 43 21 3

4554

4 1 111

3 4 1 3221322412

4431

3423

7854 4 2

412122



Jadwal Aktif(3)


4 4 34 122221322423

4 34 44 24 3

7867

6 2

322

5 4 6 3221331423

6444

3433

9877 7 3

423122

26



Jadwal Aktif(4)


4 6 76 122221331431

6 34 46 37 1

9898

8 1221

7 8 6 7233331431

6888

3431

912119 9 1

431122



Jadwal Aktif(5)


9 6 78 122233331

6 38 49 3

91212

8 1122

9 9 9 7233331

989

243

111212

11 3 133133

27



Jadwal Aktif(6)


9 9 1110 233331

11 49 3

1512 12 1

331

11 12 9 11 11 4 15 15 3 233233

12 9 15



Jadwal Aktif(7)

M1

M2

M3 313 423 133 233

412 322 122

111 221 331

212

431

28



Algoritma Pembangkitan Jadwal Non-delay(1)

Step 1. Tentukan t=0, dan kemudian mulai dengan PS0 sebagaijadwal parsial nol. Tentukan seluruh operasi tanpa predecessorsebagai S0.

Step 2. Tentukan dan mesin m* yaitu mesintempat σ * dapat direalisasikan

Step 3. Untuk setiap operasi yang membutuhkan mesin m*

dan berlaku , buat jadwal parsial baru denganmenambahkan operasi j pada PSt dengan saat mulai operasi padaσj

{ }jSj tσσ ∈= min*

tSj∈*σσ =j



Algoritma Pembangkitan Jadwal Non-delay (2)

Step 4. Untuk setiap jadwal parsial baru PSt+1, yang dihasilkan padaStep 3, perbaharui (up date) 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 keStep 2. Lanjutkan langkah-langkah ini sampai seluruh jadwal aktifdihasilkan.

29


JADWAL NON DELAY ATURAN PRIORITAS SPTMesinStage1 2 3 St Cj tij rj C* m* PSt

111 0 4 4212 0 1 1313 0 3 3

0 0 0 0

412 0 3 3

0 123

111212313

122 4 3 7221 4 4 8322 3 2 5

1 4 1 3

412 1 2 4 1 2

412

122 4 3 7221 4 4 8322 4 2 6

2 4 4 3

423 4 3 7

4 123

221322423


MesinStage1 2 3 St Cj tij rj C* m* PSt

122 6 3 9233 8 4 12331 8 3 11

3 8 6 7

431 8 1 9

6 2 122

133 9 2 11233 8 4 12331 8 3 11

4 8 9 7

431 8 1 9

8 3233431

133 12 2 145 9 9 12331 9 3 12 9 1

331

6 12 9 12 133 12 2 14 12 3 133

30


HASIL PENJADWALAN NON DELAY

Mesin 1

Mesin 2

Mesin 3

212

423 133

412

313

111

233

322

3 4 7 8 12

122

1 4 6 9

221 431 331

4 8 9 12

14

departemen teknik industri fti-itb hasil pembelajaranmahasiswa mampu menerapkan model matematik,...

Documents