BAB II TINJAUAN PUSTAKA
2.1
Penjadwalan
Baker (1974) mendefinisikan penjadwalan sebagai proses pengalokasian sumber-sumber dalam jangka waktu tertentu untuk melakukan sejumlah pekerjaan. Menurut Morton dan Pentico (1993) penjadwalan didefinisikan sebagai pengambilan keputusan tentang penyesuaian aktifitas dan sumber daya dalam rangka menyelesaikan sekumpulan pekerjaan agar tepat waktu dan mempunyai kualitas seperti yang diinginkan. Keputusan tersebut adalah: -
Pengurutan pekerjaan (sequencing).
-
Waktu mulai dan selesai pekerjaan (timing/release).
-
Urutan operasi suatu pekerjaan (routing).
Masalah penjadwalan muncul karena terbatasnya sumber daya yang dimiliki untuk mengerjakan sejumlah tugas pada saat bersamaan dan akibat dari keterbatasan tersebut perlu diambil keputusan mengenai urutan pengerjaan tugas dan alokasi dari sumber daya yang akan digunakan.
Baker (1974) menyatakan bahwa model penjadwalan dapat dibedakan menjadi 4 jenis, yaitu: -
Mesin yang digunakan dapat berupa proses dengan mesin tunggal atau proses dengan mesin majemuk.
-
Pola aliran proses dapat berupa aliran identik atau sembarang.
-
Pola kedatangan pekerjaan dapat bersifat statis atau dinamis.
-
Sifat informasi yang diterima dapat bersifat deterministik atau stokastik.
Pada jenis pertama, jumlah mesin dapat dibedakan atas mesin tunggal dan mesin majemuk. Model mesin tunggal merupakan model dasar bagi pengembangan mesin majemuk. Sedangkan pada jenis kedua, pola aliran dapat dibedakan atas flow shop dan
6
job shop. Pada flow shop, pola aliran pemrosesan seluruh pekerjaan dari suatu mesin ke mesin lain dalam urutan (routing) yang sama. Pada job shop setiap pekerjaan memiliki routing yang berbeda. Aliran proses yang berbeda mengakibatkan suatu pekerjaan yang akan diproses pada suatu mesin dapat merupakan pekerjaan baru atau pekerjaan yang sudah dikerjakan (work in proces).
Pola kedatangan pekerjaan dapat dibedakan atas pola kedatangan statis atau dinamis. Pola statis, pekerjaan datang bersamaan pada saat nol (time zero) atau kedatangan pekerjaan yang tidak bersamaan tetapi saat kedatangan pekerjaan sudah diketahui sejak saat nol. Pada pola dinamis kedatangan pekerjaan tidak menentu karena ada pengaruh dari variabel waktu. Model deterministik dilihat dari adanya informasi pasti tentang beberapa aspek. Sedangkan model stokastik mengandung unsur ketidakpastian.
2.2
Penjadwalan Job Shop
2.2.1
Definisi
Permasalahan penjadwalan job shop adalah permasalahan penjadwalan produksi yang mempunyai karakteristik sebagai berikut (Baker, 1974): -
Terdapat beberapa tipe resource produksi (mesin), masing- masing tipe terdiri dari satu unit.
-
Terdapat beberapa pekerjaan yang akan dijadwalkan, masing- masing terdiri dari beberapa operasi yang berurutan secara serial.
-
Urutan operasi pada suatu pekerjaan tidak harus sama dengan ur utan operasi pada pekerjaan yang lain.
-
Satu operasi dikerjakan oleh satu mesin dengan waktu pemrosesan tertentu.
-
Tidak ada interdependensi antar pekerjaan.
Sebuah jadwal dikatakan layak jika memenuhi kriteria sebagai berikut (Fogarty et al., 1991): -
Urutan pekerjaan operasi dalam suatu job tidak dilanggar.
-
Tidak terjadi overlap pengerjaan operasi.
7
Dalam penjadwalan job shop, jika terdapat n job yang akan diproses dalam m mesin maka akan terdapat sebanyak (n!)m set jadwal, meskipun tidak semua jadwal tersebut merupakan jadwal layak. Ketidakpraktisan pendekatan optimal pada permasalahan ini mengarahkan banyak penelitian pada penggunaan pendekatan-pendekatan heuristik. Pendekatan yang banyak digunakan pada pemecahan permasalahan penjadwalan job shop secara heuristik adalah pendekatan aturan prioritas (dispatching rule, scheduling rule). Beberapa contoh aturan prioritas yang banyak diimplementasikan pada penjadwalan job shop: -
First Come First Served (FCFS) è prioritas diberikan pada proses yang terlebih dulu mengantre pada mesin
-
Random è prioritas proses-proses dilakukan secara acak.
-
Shortest Processing Time (SPT) è prioritas diberikan pada proses dengan waktu pemrosesan terpendek.
-
Longest Processing Time (LPT) è prioritas diberikan pada proses dengan waktu pemrosesan terpanjang.
-
Earliest Due Date (EDD) è prioritas diberikan pada proses yang mempunyai due date terawal.
2.2.2
Model Analitik untuk penjadwalan Job Shop
Morton dan Pentico (1993) memformulasikan model penjadwalan job shop dengan asumsi masing- masing stasiun kerja terdiri atas satu mesin. Formulasi model penjadwalan job shop tersebut dalam bnetuk integer programming dengan fungsi tujuan untuk meminimumkan weighted flow. Formulasi matematik dari model tersebut adalah sebagai berikut: Min Z =
∑w C
j =1 , n
j
(2.1)
jK ( j )
Pembatas-pembatas: C jk ≥ C jh + p jk
∀j, k
(2.2)
C jk − Cik + H (1 − y ijk ) ≥ p jk Cik − C jk + Hy ijk ≥ pik
∀i , j , k
∀i , j , k
(2.3) (2.4)
8
C jk ≥ 0 ; yijk ∈ {0,1}
(2.5)
dimana: C jk
: completion time job j di mesin k.
C jh
: completion time job j di mesin h (completion time job j untuk operasi sebelumnya).
Cik
: completion time job i di mesin k.
p jk
: waktu proses job j di mesin k.
p ik
: waktu proses job i di mesin k.
wj
: bobot job j.
K ( j)
: mesin yang dipakai untuk operasi terakhir dari job j.
H
: bilangan yang sangat besar.
y ijk
: variabel biner.
y ijk = 1
, jika job i diproses sebelum job j dimesin k.
y ijk = 0
, jika sebaliknya.
Pembatas (2.2) menyatakan bahwa operasi hanya dapat dimulai setelah operasi sebelumnya diselesaikan (C jh ). Pembatas (2.3) dan (2.4) merupakan dua pembatas yang saling berkaitan. Kedua pembatas tersebut menunjukkan salah satu dari setiap dua job yang akan diproses pada mesin k harus dikerjakan terlebih dahulu. Pembatas (2.5) merupakan pembatas non negatif dan variable biner yang bernilai 1 atau 0.
2.2.3
Jadwal semi-aktif, aktif, non delay dan optimal
Menurut Baker (1974) jadwal-jadwal dalam job shop dapat diklasifikasikan menjadi: -
Set Jadwal Semi- Aktif (SA) Kumpulan jadwal yang tidak terdapat satu operasi pun bias dikerjakan lebih awal tanpa merubah urutan beberapa operasi pada mesin.
9
-
Set Jadwal Aktif Kumpulan jadwal semi aktif yang tidak terdapat satu operasi pun bias digeser lebih awal tanpa menunda operasi lain.
-
Set Jadwal Non Delay Kumpulan jadwal aktif yang tidak terdapat satu mesin pun dibiarkan menganggur jika pada saat yang sama terdapat operasi yang membutuhkan mesin tersebut.
-
Set Jadwal Optimal Kumpulan jadwal yang memiliki tingkat preferensi paling tinggi. Jadwal optimal ini bisa merupakan jadwal aktif atau jadwal non delay.
Algoritma Giffler-Thompson adalah algoritma yang banyak digunakan dalam pembentukan set jadwal aktif. Algoritma ini menjadi basis bagi banyak pengembangan algoritma lain pada permasalahan penjadwalan job shop. Notasi- notasi yang digunakan dalam algoritma ini antara lain: PSt
= set jadwal parsial yang berisi t proses-proses terjadwal.
St
= set yang berisi proses-proses yang bisa dijadwalkan pada stage t.
sj
= saat terawal proses j bisa dimulai.
øj
= saat terawal proses j bisa selesai.
Langkah- langkah pada algoritma tersebut adalah sebagai berikut (Baker, 1974): Langkah 1. t = 0, PSt = Ø, St berisi semua proses yang tidak mempunyai predecessor. Langkah 2. Tentukan ø* = min j ∈ St {øj} dan mesin m* dimana ø* harus dikerjakan. Langkah 3. Untuk masing- masing proses j ∈ St yang membutuhkan mesin m* dan s j < ø*, bentuk jadwal parsial baru dimana proses j ditambahkan pada PSt dan dimulai pada waktu s j. Langkah 4. Untuk setiap jadwal parsial yang terbentuk pada langkah 3, lakukan: a) Buang proses j dari St b) Bentuk St+1 dengan menambahkan successor langsung proses j pada St. c) Naikkan nilai t:t+1
10
Langkah 5. Kembali ke langkah 2 untuk setiap PSt+1 yang dibuat pada langkah 3, dan lanjutkan hingga semua jadwal aktif terbentuk.
Algoritma Jadwal Aktif ini menghitung nilai complation time. Oleh karena itu kriteria performansi yang digunakan adalah makespan, karena nilai completion time yang terbesar merupakan nilai makespan.
2.3
Penjadwalan dengan Pendekatan Mundur
Pendekatan dasar yang digunakan dalam menyusun suatu penjadwalan dapat dibedakan menjadi dua pendekatan, yaitu pendekatan maju (forward approach) dan pendekatan mundur (backward approach). Dalam Morton dan Pentico (1993) penjadwalan maju didefinisikan sebagai pengurutan pekerjaan dimulai dari arah saat nol (time zero) atau saat sekarang bergerak maju ke waktu yang akan datang, sedangkan pendekatan mundur adalah penjadwalan yang dimulai dari due date dan bergerak mundur ke arah time zero, seperti yang terlihat pada Gambar 2.1. Pada pendekatan maju akan dihasilkan suatu jadwal yang layak, tetapi tidak menjamin due date akan terpenuhi, sedangkan pada pendekatan mundur akan diperoleh penjadwalan yang memenuhi due date, tetapi tidak ada jaminan jadwal yang diperoleh tersebut layak, karena ada kemungkinan untuk melanggar time zero. Penjadwalan dengan menggunakan pendekatan mundur cocok untuk sistem produksi just in time karena produk selesai tepat pada saat diperlukan yaitu pada saat due date.
2.4
Waktu Tinggal Aktual
Halim dan Ohta (1993) dalam Nurainun (2007) mengusulkan kriteria performansi yang disebut sebagai waktu tinggal aktual. Waktu tinggal aktual didefinisikan sebagai lamanya suatu pekerjaan berada di sistem (lantai pabrik) sejak saat pekerjaan tersebut mulai dikerjakan hingga due date dari pekerjaan tersebut. Pernyataan ini dapat ditulis sebagai berikut: Fi a = d − Bi
untuk i = 1,...,N
11
(2.6)
Start time (b i) Due date
Max{D i}
O1 M1 S O2 M2
S
di
T Horison Penjadwalan
a. Pendekatan maju Start time (bi)
Due date
Max{Di}
O1 M1
S O2
M2
S
di
T Horison Penjadwalan
b. Pendekatan mundur
Gambar 2.1 Pendekatan dalam Penyusunan Jadwal
Dengan Fi a , d dan Bi adalah waktu tinggal aktual, common due date dan saat mulai (starting time), dengan asumsi waktu setup konstan dan tidak termasuk dalam waktu proses. Persamaan (2.1) dapat ditulis kembali sebagai berikut:
Fi a = ∑ ( p j + s j ) − s1 i
untuk i = 1,....,N
(2.7)
j =1
Waktu tinggal aktual suatu batch ditentukan dengan cara yang sama seperti Persamaan (2.7). Waktu proses batch diperoleh dengan mengalikan ukuran batch dengan waktu proses part, sehingga waktu tinggal aktual suatu batch adalah:
Fi a = ∑ (t j Q[ j ] + s j ) − s1 i
untuk i = 1...N
j =1
12
(2.8)
Q[j] menyatakan jumlah part yang terdapat dalam batch posisi ke-j dan t j menyatakan waktu proses part pada posisi j. Persamaan (2.6), Persamaan (2.7), Persamaan (2.8) berlaku untuk kasus mesin tunggal.
2.5
Teorema -teorema dalam Penjadwalan Batch
Halim dan Ohta (1993) dalam Nurainun (2007) mengemukakan beberapa teorema tentang penjadwalan batch, yaitu: Teorema 1 Apabila terdapat N batch dari satu item dengan waktu setup konstan yang diproses pada satu mesin, maka urutan batch yang meminimasi waktu tinggal aktual adalah urutan yang disusun sesuai dengan rasio berikut
(tQ
[1]
+ s)
Q[1]
≤
(tQ
[2 ]
+ s)
Q[ 2]
≤ ..... ≤
(tQ
[N ]
+ s)
Q[ N ]
(2.9)
Bukti: Andaikata ada dua jadwal layak untuk N batch. Jadwal pertama memperlihatkan bahwa batch g adalah batch pada urutan g dan batch (g+1) pada urutan ke (g+1), keduanya diurutkan secara mundur. Jadwal kedua berbeda dari jadwal pertama, hanya pada kondisi batch g berada pada urutan ke (g+1) dan batch (g+1) berada pada urutan ke g. Misalkan Fa1 dan Fa2 masing- masing adalah total waktu tinggal aktual seluruh part di shop untuk jadwal pertama dan kedua, maka dari Persamaan (2.4) dapat ditulis:
F a1 − F a2 = (tQ[ g] Q[ g +1] + sQ[ g+1] ) − (tQ[ g ] Q[ g +1] + sQ[ g ] )
(2.10)
Dengan demikian jadwal pertama akan memberikan total waktu tinggal aktual yang lebih baik (lebih kecil) atau sama dengan jadwal kedua (Fa1 = Fa2 ), jika dan hanya jika:
(tQ
+ s )Q[ g +1] ≤ (tQ[ g+1] + s )Q[ g ]
(2.11)
(tQ
+ s )Q[ g ] ≤ (tQ[ g +1] + s )Q[ g +1]
(2.12)
[g ]
atau [g ]
Teorema 2 Bila terdapat N batch yang masing- masing terdiri atas tipe item dan waktu proses per unit sama, serta diketahui besarnya waktu setup batch, yang diproses pada satu mesin, maka
13
susunan batch yang memberikan total waktu tinggal aktual yang minimum adalah urutan batch yang disusun sesuai dengan rasio berikut
(t
Q[1] + s[1] )
[1 ]
Q[1]
≤
(t
Q[ 2] + s[ 2] )
[2 ]
Q[ 2]
≤ ..... ≤
(t
[ N]
Q[ N ] + s[ N ] ) Q[ N ]
(2.13)
Bukti: Andaikata terdapat dua jadwal layak untuk N batch. Jadwal pertama memperlihatkan bahwa batch u adalah batch pada urutan u dan batch (u+1) pada urutan ke (u+1), keduanya diurutkan secara mundur. Jadwal kedua berbeda dari jadwal pertama, hanya pada batch u berada pada urutan ke (u+1) dan batch (u+1) berada pada urutan ke u. Misalkan Fa1 dan Fa2 masing- masing adalah total waktu tinggal aktual seluruh part di shop untuk jadwal pertama dan kedua, maka dapat ditulis:
F a1 − F a2 = (t [u[ Q[ u] Q[ u+1] + s[ u] Q[ u+1] ) − (t [ u+1] Q[ u] Q[u +1] + s[ u+1] Q[u ] )
(2.14)
Dengan demikian jadwal pertama akan memberikan total waktu tinggal aktual yang lebih baik (lebih kecil) atau sama dengan jadwal kedua (Fa1 = Fa2 ), jika dan hanya jika
(t
[ u]
Q[u ] + s[u ] )Q[ u+1] ≤ (t [u ] Q[u +1] + s[u +1] )Q[ u]
(2.15)
(t
[u ]
Q[u ] + s [u ] )Q[u ] ≤ (t[ u +1]Q[ u+1] + s [u +1] )Q[u +1]
(2.16)
atau
14
