13/05/2014
Scheduling Problems Job Shop Scheduling Problems Mata Kuliah: Penjadwalan Produksi Teknik Industri – Universitas Brawijaya
Job Shop Scheduling (2)
Job Shop Scheduling (1) • Flow shop: aliran kerja unidirectional • Job shop: aliran kerja tidak unidirectional
•
Flow shop: Indeks (i, j)
tij: Waktu proses job i di mesin j
New jobs
Job J1 J2 …
In process jobs
Mk
In process jobs
Jn
… … … …
… … … …
… … … … … …
Job shop: Indeks (i, j, k)
job operasi Completed jobs 3
Waktu proses … Mm
M1 M 2
mesin
tijk Waktu operasi ke j untuk pemrosesan job i di mesin k 4
1
13/05/2014
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
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
5
Geser-Kiri (left-shift) • Geser-kiri lokal (local left-shift) penyesuaian (menjadi lebih cepat) saat mulai (start time) suatu operasi dengan tanpa mengubah urutan • Geser-kiri global (global left-shift) penyesuaian sehingga suatu operasi dimulai lebih cepat tanpa menyebabkan delay operasi lain
6
Jenis Jadwal Pada Job Shop (1)
Jenis Jadwal Pada Job Shop (2)
1. Jadwal semiaktif
– adalah satu set jadwal yang tidak memungkinkan lagi untuk melakukan geser-kiri lokal – adalah satu set jadwal yang tidak memiliki superfluous idle time Superfluous idle time terjadi pada jadwal yang apabila suatu operasi dimulai lebih awal tidak menyebabkan perubahan urutan pada mesin manapun
Job J1 Job J2 Job J3 Job J4
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
Misal urutan job adalah 4-3-2-1: M1 M2 M3
7
Waktu Proses Operasi 1 Operasi 2 Operasi 3 4 3 2 1 4 4 3 2 3 3 3 1
4
3
4
2
1
3 2 4
3
1 2
1
8
2
13/05/2014
Jenis Jadwal Pada Job Shop (4)
Jenis Jadwal Pada Job Shop (3) Geser-kiri lokal tidak bisa dilakukan (menggeser saat mulai tanpa mengubah urutan) Saat mulai operasi (1,1,1) bisa dilakukan tanpa menyebabkan delay pada operasi lain (tapi harus mengubah urutan)
M1 M2
4
1
4
M3
3 3 2
4
3
2.
Jadwal Aktif adalah satu set jadwal yang tidak memungkinkan lagi untuk melakukan geser-kiri global
3.
Jadwal non-delay adalah jadwal aktif yang tidak membiarkan mesin menjadi idle bila suatu operasi dapat dimulai
1 1
2
1 1
1 1
2
1 1
9
10
Jenis Jadwal Pada Job Shop (5)
Algoritma Pembangkitan Jadwal Aktif (1) PSt = Jadwal parsial yang terdiri t buah operasi terjadwal
All schedule * SA
11
A
* ND
SA = semiactive A = active ND = non-delay * = optimal
St = Set 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
12
3
13/05/2014
Algoritma Pembangkitan Jadwal Aktif (2) Step 1. Tentukan t=0, dan kemudian mulai dengan PS0 sebagai jadwal parsial nol. Tentukan seluruh operasi tanpa predecessor sebagai S0.
Algoritma Pembangkitan Jadwal Aktif (3) Step 4. Untuk setiap jadwal parsial baru PSt+1, yang dihasilkan pada Step 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 2. Tentukan min jSt 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
13
Step 5. Untuk setiap PSt+1 yang dihasilkan pada Step 3, kembali ke Step 2. Lanjutkan langkah-langkah ini sampai suatu jadwal aktif dihasilkan.
14
Contoh
15
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
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
Jadwal Aktif(1)
Stage
0
1
1
0
0
Mesin 2 3
0
1
j
tij
j
0 111 212 313 412
0 0 0 0
4 1 3 3
4 1 3 3
0
0 1 0 1
4 4 3 3
4 5 3 4
st
111 221 313 412
*
m*
1
2
PSt
212
313 3
3
16
4
13/05/2014
Jadwal Aktif(2) Stage
2
3
1
Mesin 2
0
1
4
1
Jadwal Aktif(3)
j
tij
j
*
m*
PSt
3 111 221 322 412
0 1 3 1
4 4 2 3
4 5 5 4
4
1
111
3
4 4 3 1
3 4 2 3
7 8 5 4
3
st
122 221 322 412
Stage
4
5
412
4
1
4
4
Mesin 2 3
4
6
j
tij
j
3 122 221 322 423
4 4 4 4
3 4 2 3
7 8 6 7
3
6 4 4 4
3 4 3 3
9 8 7 7
7
3
*
m*
8
1
11
3
2
17
122 221 331 423
*
m*
PSt
322 6
2 423
18
Jadwal Aktif(4) Stage
6
7
19
st
1
4
8
Mesin 2
6
6
j
tij
j
7 122 221 331 431
6 4 6 7
3 4 3 1
9 8 9 8
7
6 8 8 8
3 4 3 1
9 12 11 9
3
st
122 233 331 431
Jadwal Aktif(5) *
m*
PSt
Stage
221 8
8
1
9
431
9
1
9
9
Mesin 2
6
9
3
st
7 122 233 331 7 133 233 331
j
tij
j
6 8 9 9 8 9
3 4 3 2 4 3
9 12 12 11 12 12
PSt
122
133
1
20
5
13/05/2014
Jadwal Aktif(6)
Stage
1
Mesin 2
10
9
9
11
12 12
9 9
Jadwal Aktif(7)
j
tij
j
*
m*
11 233 331
11 9
4 3
15 12
12
1
11 233
11
4
15
15
3
3
st
M3
PSt
313
331
412
M2
423 322
133
233
122
212
233 M1
15
111
221
331 431
21
22
Algoritma Pembangkitan Jadwal Non-delay (2)
Algoritma Pembangkitan Jadwal Non-delay(1) Step 1. Tentukan t=0, dan kemudian mulai dengan PS0 sebagai jadwal parsial nol. Tentukan seluruh operasi tanpa predecessor sebagai S0.
Step 4. Untuk setiap jadwal parsial baru PSt+1, yang dihasilkan pada Step 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
dan mesin m* yaitu mesin
Step 2. Tentukan min jSt j 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 5. Untuk setiap PSt+1 yang dihasilkan pada Step 3, kembali ke Step 2. Lanjutkan langkah-langkah ini sampai seluruh jadwal aktif dihasilkan.
23
24
6
13/05/2014
Priority Control • Priority rules: for establishing the priority of orders • Common priority rules
First Come First Served (FCFS) Shortest Processing Time (SPT) Earliest Due Date (EDD) Slack per Remaining Operation (S/OPN) Critical Ratio (CR) Queue Ratio (QR) Operation Due Date (OPNDD)
Referensi • Introduction to Sequencing and Scheduling. Kenneth R. Baker. Duke University. John Wiley & Sons. 1974.
25
7
