perencanaan & pengendalian produksiaeunike.lecture.ub.ac.id/files/2012/12/pertemuan-13-14...7...

PERENCANAAN & PENGENDALIAN PRODUKSI

TIN 4113

Pertemuan 13 & 14

• Outline:

– Scheduling

• Referensi:

– Tersine, Richard J., Principles of Inventory and Materials Management, Prentice-Hall, 1994.

– Wiratno, S. E., Lecture PPT: Production Activity Control, IE-ITS, 2009.

3

Scheduling and Squencing

• Scheduling is the assigning of starting and completion times to orders (jobs) and frequently includes the time when orders are to arrive and leave each department

• Sequencing is the assigning of the sequence in which orders are to be processed

4

Pendahuluan

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

• Output MRP adalah planned order releases

• Terdapat order-order yang berbeda tetapi harus diproses pada mesin yang sama

5

Model Penjadwalan (1)

Penjadwalan

Single stage

Multiple stages

Single machine

Parallel/heterogeneous machines

Flow shop

Job shop

Job

Batch

6

Model Penjadwalan(2)

• Job scheduling (memecahkan masalah sequencing saja, karena ukuran job telah diketahui)

• n jobs on 1 processor

• n jobs on m-parallel processors

• Flow shop scheduling

• Job shop scheduling

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

Single stage

Multiple stages

7

Pendekatan

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

• Backward scheduling (penjadwalan mundur): penjadwalan mulai dari due date dan bergerak berlawanan arah dengan arah pergerakan waktu. Jadwal pasti memenuhi due date tapi mungkin tidak feasible

8

Terminologi (1)

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

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

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

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

9

Terminologi (2) • Delivery date (saat kirim): saat pengiriman job dari shop floor

ke proses berikut atau ke konsumen, deli • 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

10

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 saat dimulai dan saat selesai suatu pekerjaan

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

11

Terminologi (4) • Waiting time adalah waktu job menunggu karena mesin yang

seharusnya memproses job tersebut sedang memproses job lain

• Idle time adalah waktu mesin tidak bekerja (menganggur) karena tidak ada job yang harus diproses

• Priority rule: aturan penentuan prioritas pemrosesan

• FCFS (first come first serve); SPT (shortest processing time), LPT (longest processing time), EDD (earliest due date); rasio kritis (critical ratio, CR).

– CR = (due date – today’s date)/(lead time remaining) atau CR = (due date – today’s date)/(workdays remaining)

12

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

13

Terminologi (6) – Suatu variant dalam batch scheduling problems

adalah lot streaming.

– Lot streaming adalah suatu teknik untuk mempercepat aliran pengerjaan (the flow of work) dengan menentukan transfer lots, yaitu lot untuk membawa sebagian part (dari suatu batch yang terdiri part yang identik) yang sudah selesai diproses di suatu mesin (upstream machine) ke mesin berikut (downstream machine). Tujuan lot streaming adalah untuk memperpendek makespan dan sekaligus flow time (yang berarti meminimumkan inventory).

14

Penjadwalan n jobs pada single machine(1)

– Aturan SPT (shortest processing time) untuk meminimumkan waktu tinggal (flow time) rata-rata:

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

nn tttt 121 ...

15

Penjadwalan n jobs pada single machine(2)

1 5

2 8

3 6

4 3

5 10

6 14

7 7

8 3

JobWaktu

prosesJob

Waktu

Proses

Flow

time

4 3 3

8 3 6

1 5 11

3 6 17

7 7 24

2 8 32

5 10 42

6 14 56

F 191

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

Flow time rata-rata: 23,875

16

Penjadwalan n jobs pada single machine(3)

Gantt chart

4 8 1 3 7 2 5 6

Makespan = 56

JobWaktu

Proses

Flow

time

4 3 3

8 3 6

1 5 11

3 6 17

7 7 24

2 8 32

5 10 42

6 14 56

F 191

F 23.875

17

Penjadwalan n jobs pada single machine(4)

• Aturan WSPT (Weighted Shortest Processing Time):

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

n

n

n

n

W

t

W

t

W

t

W

t

1

1

2

2

1

1...

18

Penjadwalan n jobs pada single machine(5)

JobWaktu

prosesBobot

1 5 1 5

2 8 2 4

3 6 3 2

4 3 1 3

5 10 2 5

6 14 3 4.7

7 7 2 3.5

8 3 1 3

i

i

w

t

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

Flow time rata-rata: 27,0

Flow time tertimbang rata-rata: 27,46667

Job BobotWaktu

proses

Flow

time

Weighted

Flow time

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 412

Rata-rata 27 27.4667

19

Penjadwalan n jobs pada single machine(6)

• Aturan SPT meminimumkan mean lateness

• Bila terdapat n jobs yang akan diproses di sebuah mesin, maka mean lateness akan minimum bila jobs tersebut diurut menurut aturan SPT

1 5 15

2 8 10

3 6 15

4 3 25

5 10 20

6 14 40

7 7 45

8 3 50

Job Waktu Due date

20

Penjadwalan n jobs pada single machine(7)

Latenesss

c-d

4 3 25 3 -22

8 3 50 6 -44

1 5 15 11 -4

3 6 15 17 2

7 7 45 24 -21

2 8 10 32 22

5 10 20 42 22

6 14 40 56 16

Total -29

Rata-rata -3.625

Job Waktu Due dateSaat

Selesai

Maximum lateness : 22

21

Penjadwalan n jobs pada single machine(8)

• Aturan EDD (earliest due date)

• Aturan EDD meminimumkan maximum lateness pada sebuah mesin

Saat Latenesss

Selesai c-d

2 8 10 8 -2

1 5 15 13 -2

3 6 15 19 4

5 10 20 29 9

4 3 25 32 7

6 14 40 46 6

7 7 45 53 8

8 3 50 56 6

Total 36

Rata-rata 4.5

Job Waktu Due date

Maximum lateness : 9

22

Penjadwalan n jobs pada single machine(9)

• Algoritma Hodgson meminimumkan jumlah job yang tardy pada sebuah mesin Step 1. Urut semua job sesuai EDD; bila tidak ada atau hanya satu job yang

tardy (positive lateness) maka stop. Bila lebih dari sebuah maka lanjutkan ke Step 2

Step 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 3

Step 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 selesai yang baru, dan kembali ke Step 2.

Step 4. Tempatkan job yang dikeluarkan dalam urutan sembarang di ujung belakang urutan

23

Penjadwalan n jobs pada single machine(10)

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

24

Penjadwalan n jobs pada single machine(11)

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 = 2

Rata-rata lateness = 1,625, dan maximum lateness = 36

25

Penjadwalan n jobs pada single machine(12)

Mean Flow Weighted Mean Maximum No. of Mean

Rule Time Mean Flow Lateness Lateness Tardy Tardiness

Time Jobs

SPT 23,875 29 -3,625 22 4 7,75

WSPT 27 27,467 -0.5 36 4 10,625

EDD 32 31733 4,5 9 6 5

Slack 32,125 31,133 4,625 9 6 5

Hodgson 29,125 29,867 1,625 36 2 9

Wilkerson 28,875 30,667 1,375 16 3 4

Perbandingan perfomansi scheduling rule

26

Penjadwalan n jobs, parallel machines(1)

• Algoritma meminimkan mean flow time pada mesin paralel

Step 1. Urut semua jobs dengan urutan SPT

Step 2. Jadwalkan job tersebut satu per satu pada mesin yang memiliki beban minimum. Bila beban mesin sama, pilih sembarang mesin

i 1 2 3 4 5 6 7 8 9 10

ti 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

27

Penjadwalan n jobs, parallel machines (2)

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

2 9 10

6 7 8 4

28

Penjadwalan n jobs, parallel machines (3)

Job Waktu Flow time Job Waktu Flow time Job Waktu Flow time

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.67 8.67

M1 M2 M3

Rata-rata flow time: 8,1

Makespan: 18

29

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 memproses sebuah job pada saat yang sama

30

Algoritma Johnson (1)

Step 1. Tentukan waktu proses yang terpendek di antara seluruh job dalam daftar job yang akan diproses

Step 2a. Bila waktu proses terpendek berada di mesin M1, maka jadwalkan job dengan waktu terpendek itu pada posisi paling kiri pada urutan yang dimungkinkan, dan lanjutkan ke Step 3.

Step 2b. Bila waktu proses terpendek berada di mesin M2, maka jadwalkan job dengan waktu terpendek itu pada posisi paling kanan pada urutan yang dimungkinkan, dan lanjutkan ke Step 3.

31

Algoritma Johnson (2)

Step 2c. Bila terdapat beberapa nilai waktu proses terpendek, maka pilih sembarang; dan jadwalkan job dengan waktu proses terpilih di posisi paling kiri atau kanan sesuai dengan keberadaan waktu proses terpilih tersebut.

Step 3. Keluarkan job yang sudah dijadwalkan dari daftar job. Bila masih ada job yang belum dijadwalkan, maka kembali ke Step 1. Bila seluruh job sudah dijadwalkan maka stop.

32

Algoritma Johnson (3)

Job

tj1

tj2

Job1 Job2 Job3 Job4 Job5

3 5 1 6 7

6 2 2 6 5

Job3 Job1 Job4 Job5 Job2

3

1 4 5 2

2 5 4 1 3 24

M=24

33

Job Shop Scheduling (1)

• Flow shop: aliran kerja unidirectional

• Job shop: aliran kerja tidak unidirectional

Mk

In process jobs In process jobs

New jobs

Completed jobs

34

Job Shop Scheduling (2)

• Flow shop: Indeks (i, j)

Job M1 M2 Mm …

J1

J2

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

35

Job Shop Scheduling (3)

Operasi 1 Operasi 2 Operasi 3

Job J1 4 3 2

Job J2 1 4 4

Job J3 3 2 3

Job J4 3 3 1

Waktu Proses

Operasi 1 Operasi 2 Operasi 3

Job J1 1 2 3

Job J2 2 1 3

Job J3 3 2 1

Job J4 2 3 1

Routing

t233 = 4 t31… = 3 3 1= t431

Latihan Soal • Tabel di bawah menunjukkan waktu proses 4 jobs pada satu mesin.

Tentukan urutan (sequence) jobs yang meminimalkan:

– Rata-rata flow time

– Mean lateness

– Maksimum lateness

– Jumlah tardy job

• The drilling and riveting times for six jobs are given next. For every job, a hole is drilled first, followed by riveting. Find the optimum sequence that minimizes the makespan for all jobs.

Job 𝑖 J1 J2 J3 J4

Waktu proses (𝑡𝑖) 7 6 8 5

Due date (𝑑𝑖) 20 22 10 15

Job 𝑖 J1 J2 J3 J4 J5 J6

Drilling 4 7 3 12 11 9

Riveting 11 7 10 8 10 13

Pertemuan 15 – Persiapan

• Materi

– Presentasi Tugas Besar (by appointment before due date)

Pertemuan 16 – QUIZ 2

• Materi

– Master Production Schedule

– Material Requirement Planning

– Line Balancing

– Scheduling