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.
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
3
Pendahuluan •
• •
4
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
Model Penjadwalan (1) Single machine Single stage
Job
Parallel/heterogeneous machines Flow shop
Penjadwalan
Multiple stages Job shop Batch
5
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
Single stage
Multiple stages
• Batch scheduling (memecahkan masalah penentuan ukuran batch dan masalah sequencing secara simultan) 6
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 7
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
8
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
9
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)
10
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)
11
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
12
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).
13
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:
t1 t2 ... tn1 tn
14
Penjadwalan n jobs pada single machine(2) Job 1 2 3 4 5 6 7 8
Waktu proses 5 8 6 3 10 14 7 3
Urutan yang dihasilkan:
Waktu Flow Proses 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 4-8-1-3-7-2-5-6
Flow time rata-rata: 23,875 15
Job
Penjadwalan n jobs pada single machine(3) Job 4 8 1 3 7 2 5 6
16
Waktu Flow Proses time 3 3 3 6 5 11 6 17 7 24 8 32 10 42 14 56 F 191 F 23.875
Makespan = 56
4
8
1
3
7
2
Gantt chart
5
6
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:
t1 W1
17
t 2 W2
...
tn1 Wn 1
t n Wn
Penjadwalan n jobs pada single machine(5) Job
Waktu proses
Bobot
ti wi
1 2 3 4 5 6 7 8
5 8 6 3 10 14 7 3
1 2 3 1 2 3 2 1
5 4 2 3 5 4.7 3.5 3
Job 3 4 8 7 2 6 1 5 Total
Bobot 3 1 1 2 2 3 1 2 15
Waktu proses 6 3 3 7 8 14 5 10 Total Rata-rata
Urutan yang dihasilkan: 3-4-8-7-2-6-1-5 Flow time rata-rata: 27,0 Flow time tertimbang rata-rata: 27,46667 18
Flow time 6 9 12 19 27 41 46 56 216 27
Weighted Flow time 18 9 12 38 54 123 46 112 412 27.4667
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
19
Job
Waktu
Due date
1 2 3 4 5 6 7 8
5 8 6 3 10 14 7 3
15 10 15 25 20 40 45 50
Penjadwalan n jobs pada single machine(7) Job
Waktu
Due date
4 8 1 3 7 2 5 6
3 3 5 6 7 8 10 14
25 50 15 15 45 10 20 40
Maximum lateness : 22 20
Saat Selesai
3 6 11 17 24 32 42 56 Total Rata-rata
Latenesss
c-d -22 -44 -4 2 -21 22 22 16 -29 -3.625
Penjadwalan n jobs pada single machine(8) • Aturan EDD (earliest due date) • Aturan EDD meminimumkan maximum lateness pada sebuah mesin
21
Job
Waktu
Due date
2 1 3 5 4 6 7 8
8 5 6 10 3 14 7 3
10 15 15 20 25 40 45 50
Saat Latenesss Selesai c-d 8 -2 13 -2 19 4 29 9 32 7 46 6 53 8 56 6 Total 36 Rata-rata 4.5
Maximum lateness : 9
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 22
Penjadwalan n jobs pada single machine(10) i ti ci di Li
i ti ci di Li
23
2 8 8 10 -2
1 5 5 15 -10
1 5 13 15 -2
3 6 11 15 -4
3 6 19 15 4
5 10 29 20 9
5 10 21 20 1
4 3 32 25 7
4 3 24 25 -1
6 14 46 40 6
6 14 38 40 -2
7 7 53 45 8
8 3 56 50 6
7 7 45 45 0
8 3 48 50 -2
Penjadwalan n jobs pada single machine(11) 1 5 5 15 -10
i ti ci di Li
i ti ci di Li
1 5 5 15 -10
3 6 11 15 -4
3 6 11 15 -4
4 3 14 25 -11
4 3 14 25 -11
6 14 28 40 -12
6 14 28 40 -12
7 7 35 45 -10
7 7 35 45 -10
8 3 38 50 -12
8 3 38 50 -12
2 8 46 10 36
5 10 56 20 36
Jumlah tardy job = 2 Rata-rata lateness = 1,625, dan maximum lateness = 36 24
Penjadwalan n jobs pada single machine(12) Perbandingan perfomansi scheduling rule Rule
Mean Flow Time
SPT
23,875
29
-3,625
22
4
7,75
WSPT
27
27,467
-0.5
36
4
10,625
EDD Slack Hodgson Wilkerson
32 32,125 29,125 28,875
31733 31,133 29,867 30,667
4,5 4,625 1,625 1,375
9 9 36 16
6 6 2 3
5 5 9 4
25
Weighted Mean Maximum Mean Flow Lateness Lateness Time
No. of Tardy Jobs
Mean Tardiness
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
Urutan SPT
26
i
6
10
3
7
9
1
8
2
5
4
ti
2
2
3
3
4
5
5
6
7
8
Penjadwalan n jobs, parallel machines (2) 6 2
i ti
27
M3
3
M2
10
M1
6
10 2
3 3
7 3
1
1 5
5
9
7
9 4
2
8
4
8 5
2 6
5 7
4 8
Penjadwalan n jobs, parallel machines (3)
Job 6 7 8 4
M1 Waktu Flow time 2 2 3 5 5 10 8 18 Total 35 Rata-rata 8.75
Job 10 9 2
Rata-rata flow time: 8,1 Makespan: 18 28
M2 Waktu Flow time 2 2 4 6 6 12 20 6.67
Job 3 1 5
M3 Waktu Flow time 3 3 5 8 7 15 26 8.67
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
29
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.
30
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.
31
Algoritma Johnson (3) Job
Job1
Job2
Job3
Job4
Job5
tj1
3
5
1
6
7
tj2
6
2
2
6
5
Job3
Job1
Job4
Job5
Job2
M=24
3 1 3
4
5 1
4
2 5
2 24
32
Job Shop Scheduling (1) • Flow shop: aliran kerja unidirectional • Job shop: aliran kerja tidak unidirectional New jobs
In process jobs
Mk
In process jobs
Completed jobs 33
Job Shop Scheduling (2) • Flow shop: Indeks (i, j)
tij: Waktu proses job i di mesin j
Job J1 J2 … Jn
Waktu proses M1 M2 … Mm … … … … … … … …
… … … … … …
Job shop: Indeks (i, j, k) job operasi
mesin
tijk Waktu operasi ke j untuk pemrosesan job i di mesin k 34
Job Shop Scheduling (3)
Job J1 Job J2 Job J3 Job J4
Waktu Proses Operasi 1 Operasi 2 Operasi 3 4 3 2 1 4 4 3 2 3 3 3 1
t233 = 4
35
t31… 3 = 3
Job J1 Job J2 Job J3 Job J4
Routing Operasi 1 Operasi 2 Operasi 3 1 2 3 2 1 3 3 2 1 2 3 1
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 Job 𝑖
J1
J2
J3
J4
Waktu proses (𝑡𝑖 )
7
6
8
5
Due date (𝑑𝑖 )
20
22
10
15
• 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
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
