BAB II LANDASAN TEORI
2.1 Definisi Penjadwalan Penjadwalan adalah pengurutan pembuatan /pengerjaan produk secara menyeluruh yang dikerjakan pada beberapa buah mesin.Dengan demikian masalah sequencing senantiasa melibatkan pengerjaan sejumlah komponen yang sering disebut dengan istilah ‘job’.Job sendiri masih merupakan komposisi dari sejumlah elemen-elemen dasar yang disebut aktivitas atau operasi.Tiap aktivitas atau operasi ini membutuhkan alokasi sumber daya tertentu selama periode waktu tertentu yang sering disebut dengan waktu proses.(Rosnani Ginting,2007) Penjadwalan
merupakan
alat
ukur
yang
baik
bagi
perencanaan
agregat.Pesanan-pesanan aktual pada tahap ini akan ditugaskan pertama kalinya pada sumber daya tertentu (fasilitas,pekerja,dan peralatan),kemudian dilakukan pengurutan kerja pada tiap-tiap pusat pemrosesan sehingga dicapai optimalitas utilisasi kapasitas yang ada.Pada penjadwalan ini,permintaan akan produk-produk yang tertentu (jenis dan jumlah)dari MPS akan ditugaskan pada pusat-pusat pemrosesan tertentu untuk periode harian.
7
8
2.2 Tujuan Penjadwalan Bedworth
(1987),mengidentifikasi
beberapa
tujuan
dari
aktivitas
penjadwalan adalah sebagai berikut: 1. Meningkatakan penggunaan sumber daya atau mengurangi waktu tunggunya,sehingga total waktu proses dapat berkurang,dan produktivitas dapat meningkat. 2. Mengurangi persediaan barang setengah jadi atau mengurangi jumlah pekerjaan yang menunggu dalam antrian ketika sumber daya yang adamasih mengerjakan tugas yang lain.Teori Baker mengatakan,jika aliran kerja suatu jadwal konstan ,maka antrian yang mengurangi rata-rata waktu alir akan mengurangi rata-rata persediaan barang setengah jadi. 3. Mengurangi beberapa keterlambatan pada pekerjaan yang mempunyai batas waktu penyelesaian sehingga akan meminimalisasi penalty cost (biaya keterlambatan). 4. Membantu pengambilan keputusan mengenai perencanaan kapasitas pabrik dan jenis kapasitas yang dibutuhkan sehingga penambahan biaya yang mahal dapat dihindarkan.
2.3 Model Penjadwalan Proses penjadwalan timbul jika terdapat keterbatasan sumber daya yang dimiliki sehingga diperlukan adanya pengaturan sumber – sumber daya tersebut secara efisien.Berbagai model penjadwalan telah dikembangkan untukmengatasi persoalan penjadwalan tersebut.
9
Menurut Baker (1974),model penjadwalan dapat dibedakan menjadi 4 jenis keadaan : 1. Mesin yang digunakan berupa proses dengan mesin tunggal atau proses dengan mesin majemuk. 2. Pola aliran proses dapat berupa aliran identic atau sembarang. 3. Pola kedatangan pekerjaan statis atau dinamis. 4. Sifat informasi yang diterima dapat bersifat deterministik atau stokastik. Pada keadaan pertama ,sejumlah mesin dapat dibedakan atas mesin tunggal mesin majemuk.Model mesin tunggal adalah mesin dasar dan biasanya dapat diterapkan pada kasus mesin majemuk. Pada keadaan kedua,pola aliran dapat dibedakan atas flow shop dan job shop.Pada flow shop dijumpai pola aliran proses dari urutan tertentu yang sama.Flow shop terbagi lagi menjadi pure flow shop dan general flow shop.Pada pure flow shop berbagai pekerjaan akan mengalir pada lini produksi yang sama dan tidak dimungkinkan adanya variasi. Pada general flow shop dimungkinkan adanya variasi antara pekerjaan atau pekerjaan yang datang tidak harus dikerjakan disemua mesin.Sedangkan pada job shop,setiap pekerjaan memiliki pola aliran kerja yang berbeda.Aliran proses yang tidak searah ini mengakibatkan pekerjaan yang dikerjakan disuatu mesin dapat berupa pekerjaan baru atau pekerjaan yang sedang dikerjakan (work in process) atau pekerjaan yang akan menjadi produk jadi (finished goods) telah diproses di mesin tersebut.
10
Pada keadaan ketiga,pola kedatangan pekerjaan dapat dibedakan atas pola kedatangan statis atau dinamis.Pada pola statis,pekerjaan datang bersamaan pada waktu nol dan siap dikerjakan atau kedatangan pekerjaan bisa tidak bersamaan tetapi saat kedatangan telah diketahui sejak waktu nol.Pada pola dinamis mempunyai sifat kedatangan pekerjaan tidak menentu,artinya terdapat variabel waktu sebagai faktor yang berpengaruh. Pada
keadaan
keempat,perilaku
elemen-elemen
penjadwalan
dapat
dibedakan atas deterministik dan stokastik.Model deterministik memiliki kepastian informasi tentang parameter dalam model,sedangkan model stokastik mengandung unsur ketidakpastian. Parameter yang dimaksud adalah: a. Saat datang ,saat siap,jumlah pekerjaan,batas waktu penyelesaian (due date),dan bobot kepentingan masing-masing pekerjaan. b. Jumlah operasi ,susunan mesin(routing),waktu proses,dan waktu setup. c. Jumlah dan kapasitas mesin,kemampuan dan kecocokan tiap mesin terhadap pekerjaan yang akan dihadapkan. Pada proses penjadwalan produksi deterministik dibutuhkan tiga parameter dasar yaitu : 1. Processing time (ti) atau proses,yaitu waktu yang dibutuhkan untuk memberikan nilai tambah pada order i. 2. Ready time (ri) atau saat siap,yaitu saat paling awal orderi dapat diproses oleh mesin. 3. Due date (di)atau saat kirim,yaitu saat kirim order i kepada konsumen.
11
Ketiga parameter tersebut digunakan pula dalam mengevaluasi hasil penjadwalan.
2.4 Notasi Matematis Penjadwalan Beberapa notasi umum yang digunakan dalam membahas penjadwalan produksi adalah sebagai berikut: a. Processing Time (Waktu Proses) Taksiran peramalan tentang barapa lama waktu yang dibutuhkan untuk menyelesaikan suatu tugas.Taksiran meliputi setup time yang mungkin dibutuhkan ,yang di asumsikan bebas.Pada pemnbahasan ini,processing time untuk tugas i dinyatakan dengan ti. b. Makespan Yaitu waktu yang diperlukan untuk menyelesaikan semua pekerjaan (job) yang ada di shop,yang terdiri dari waktu setup antar job (s[i-1],[i]) dan waktu proses per job (ti). n +1
n
i =1
i =1
M = ∑ s [i −1],[i] + ∑ t i .......... .......... .......... Pers.1
Sumber : Rosnani Ginting,2007 c. Ready Time Adalah waktu yang dibutuhkan suatu job pada saat siap untuk di jadwalkan(ri).
12
d. Waiting Time (Waktu Tunggu) Yaitu waktu yang menunggu order i sejak saat suatu proses selesai dikerjakan sampai saat mulai operasi berikutnya. m
Wi = C i − ri − ∑ t ij .......... .......... .......... Pers.2 i =1
Sumber : Rosnani Ginting,2007 e. Flow Time (Waktu Alir) Rentang waktu antara satu titik dimana tugas tersebut selesai.Jadi,flow time sama dengan processing time di jumlahkan dengan waktu ketika tugas menunggu sebelum diproses.Flow time dinyatakan dengan Fi. Fi = C i - ri ..............................Pers.3 Fi = t i + Wi ..............................Pers.4 Sumber : Rosnani Ginting,2007 f. Completion Time(Waktu Penyelesaian) Rentang antara awal tugas pada pekerjaan pertama ,dimana waktunya mengacu pada t=0,dengan waktu ketika tugas selesai .Rentang dinyatakan dengan Ci.
C i = Fi + ri ..............................Pers.5 Sumber : Rosnani Ginting,2007
13
g. Due Date (Batas Waktu) Batas waktu yang ditentukan untuk tugas yang telah lewat,yang akan dinyatakan dengan terlambat.Denda akan diberikan bila terlambat.Due
date dinyatakan dengan di. h. Slack Ukuran perbadaan antara waktu sisa dari batas waktu tugasdengan waktu prosesnya (processing time).
SL i = d i - t i ..............................Pers.6 Sumber : Rosnani Ginting,2007 i. Lateness (Kelambatan) Merupakan penyimpangan antara waktu penyelesaian pekerjaan dengan batas waktu.Suatu pekerjaan akan mempunyai kelambatan posotif jika di selesaikan sesudah batas waktu dan kelambatan negative jika diselesaikan sebelum batas waktu.Simbol kelambatan ini adalah Li
L i = C i - d i ..............................Pers.7 L i ≤ 0, saat penyelesaian memenuhi batas waktu L i > 0, saat penyelesaian melewati batas waktu Sumber : Rosnani Ginting,2007
j. Rata-Rata Lateness Ls =
1 n .∑ L i .......... .......... .........P ers.8 n i =1
Sumber : Hendra Kusuma,2009f
14
k. Tardiness (Ukuran Kelambatan) Merupakan ukuran kelambatan untuk kelambatan positif.Jika suatu pekerjaan diselesaikan lebih cepat dari batas waktu yang di tetapkan,maka mempunyai
nilai
kelambatan
negatif
tetapi
positif.Ukuran ini disimbolkan dengan Ti dimana Ti l. Rata-Rata Tardiness Ts =
i n .∑ Ti .......... .......... .........P ers.9 n i =1
Sumber : Hendra Kusuma,2009
m. Number Of Tardiness n
N T = ∑ δ i .......... .......... .........P ers.10 i =1
δ i = 1, bila Ti > 0 δ i = 0, bila Ti ≤ 0
Sumber : Hendra Kusuma,2009 n. Tmax atau Lmax Tmax = max(0, L max ) L max = max (L i ) Sumber : Hendra Kusuma,2009
ukuran
kelambatan
15
2.5 Input dan Output Penjadwalan 2.5.1 Input Penjadwalan Pekerjaan-pekerjaan yang merupakan alokasi kapasitas untuk orderorder,penugasan prioritas job,dan pengendalian jadwal produksi membutuhkan informasi terperinci,dimana informasi-informasi tersebut menyatakan input dari sistem penjadwalan.Kita harus menentukan kebutuhan-kebutuhan kapasitas dari order –order yang dijadwalkan dalam hal jumlah dan macam sumberdaya yang digunakan .Untuk produk tertentu,informasi ini bisa diperolah dari lembar kerja operasi dan bill of material (BOM).Kualitas dari keputusan-keputusan penjadwalan sangat dipengaruhi oleh ketetapan estimasi dari input-input tersebut.Oleh karena itu,pemeliharaan catatan terbaru tentang status tenaga kerja dan peralatan yang tersedia,dan perubahan kebutuhan kapasitas yang diakibatkan perubahan disain produk/proses menjadi sangat penting.Bila digambarkan,maka elemen-elemen output-input,prioritas – prioritas dan ukuran kinerja dari sistem penjadwalan akan tampak seperti pada gambar 2.1.
2.5.2 Output Penjadwalan Untuk memastikan bahwa suatu aliran kerja yang lancar akan melalui tahapan produksi,maka sistem penjadwalan harus membentuk aktivitas-aktivitas output sebagai berikut: 1. Pembebanan (loading) Pembebanan melibatkan penyesuaian kebutuhan kapasitas untuk orderorder
yang
diterima/diperkirakan
dengan
kapasitas
yang
16
tersedia.Pembebanan dilakukan dengan menugaskan order-order pada fasilitas-fasilitas ,operator-operator,dan peralatan tertentu. 2. Pengurutan (sequencing) Pengurutan merupakan penugasan tentang order-order mana yang diprioritaskan untuk diproses dahulu bila suatu fasilitas harus memproses banyak job. 3. Prioritas job (dispatching) Dispatching merupakan prioritas kerja tentang job-job mana yang diseleksi dan diprioritaskan untuk diproses. 4. Pengedalian kinerja penjadwalan Pengendalian kinerja penjadwalan dilakukan dengan :
•
Meninjau kembali status order-order pada saat melalui sistem tertentu.
•
Mengatur kembali urutan-urutan,misalnya expediting order-order yang jauh dibelakang atau mempunyai prioritas utama.
5. Up-dating jadwal Up-dating jadwal dilakukan sebagai refleksi kondisi operasi yang terjadi dengan merevisi prioritas-prioritas.
Gambar 2.1Elemen-elemen Sistem Penjadwalan Sumber : Rosnani Ginting,2007
17
18
2.6 Jenis-Jenis Penjadwalan 2.6.1 Penjadwalan Flow Shop Penjadwalan flow shop merupakan suatu pergerakan unit-unit yang terus menerus melalui suatu rangkaian stasiun-stasiun kerja yang disusun berdasarkan produk. Susunan suatu proses produksi jenis flow shop dapat diterapkan dengan tepat untuk produk-produk dengan desain stabil dan diproduksi. Secara banyak (volume produk), sehingga investasi dengan tujuan khusus (special purpose) yang dapat secepatnya kembali. Suatu masalah kritis dalam flow shop adalah pengelompokkan tugas-tugas yang dibutuhkan dalam stasiun kerja, sehingga dicapai suatu kondisi yang memenuhi pembatas-pembatas urutan dan terjadi kesimbangan pada tingkat output produksi. Jika tingkat output bervariasi untuk masing-masing stasiun kerja, maka hal ini berate bahwa lintasan produksi tersebut tidak seimbang. Ketidakseimbangan lintasan akan menghasilkan aliran yang tidak teratur dan rendahnya utilisasi kapasitas yang disebabkan turunnya kecepatan aliran pada stasiun-stasiun penyebab bottleneck (operasi akan berjakan terputus-putus). Problem lain pada penjadwalan flowshop adalah berhubungan dengan ketegangan yang diakibatkan susunan aliran ini terhadap pekerja. Pekerja biasanya menjadi sangat bosan karena terbatanya variasikerja pada tiap-tiap stasiun dan panjangnya rentang pengendalian sepanjang lintasan produksi.Oleh karena itu, pihak manajemen melakukan job rotasi, mengubah lintasan produksi yang panjang menjadi segmen-segmen yang lebih pendek sehingga dapat dikendalikan oleh kelompok kecil pekerja, dan menyediakan penghargaan tingkat
19
output produksi tinggi dan berkualitas. Dengan cara ini, maka kebosanan dan rasa frustasi pekerja dapat dieliminir.
2.6.2 Penjadwalan Batch Banyak dari pabrik dengan jenis MTS memproduksi produk-produk yang berbeda pada fasilitas-fasilitas yang umum. Sebagai contoh, pabrik minuman ringan mungkin memproduksi beberapa rasa minuman yang berbeda pada satu fasilitas atau perusahaan sabun mungkin mengemas produknya dalam beberapa ukuran yang berbeda pada lintasan pengepakan yang sama. Pada kasus seperti ini, produk-produk tersebut umumnya diproduksi dalam ukuran batch. Keputusankeputusan yang dihadapi oleh manajer produksi dalam sistem produksi batch adalah “berapa” jumlah produksi dalam setiap batchnya berikut urut-urutannya, atau perintah mengenai produk-produk mana saja yang harus dibuat secara batch. Kuantitas dari batch (biasa ditentukan berdasarkan panjang waktu yang dibutuhkan untuk setiap production run) dan frekwensi produksi akan mempengaruhi tingkat persediaan dan biaya setup yang lebih panjang, maka dibutuhkan persediaan lebih banyak tetapi dengan setup yang lebih sedikit. Kuantitas batch yang optimal dapat dihitung dengan menggunakan metode EPQ. Meskipun demikian beberapa produk menggunakan fasilitas umum secara bersama-sama, maka kita perlu meodifikasi ukuranbatch.Modifikasi ukuran batch ini dikarenakan ukuran produk juga harus dipertimbangkan. Ukuran produk juga mempengaruhi biaya, karena biaya setup akan bervariasi bergantung dari perubahan urutan-urutan produk.
20
2.6.3 Penjadwalan Job Shop Penjadwalan pada proses produksi tipe job shop lebih sulit dibandingkan penjadwalan flow shop. Hal ini disebabkan oleh 3 alasan, yaitu : 1. Job shop menangani variasi produk yang sangat banyak, dengan pola aliran yang berbeda-beda melalui pusat-pusat kerja. 2. Peralatan pada job shop digunakan bersama-sama oleh bermacam-macam order pada prosesnya, sedangkan peralatan pada flow shop digunakan khusus untuk satu jenis produk. 3. Job-job yang berbeda mungkin ditentukan oleh prioritas berbeda pula. Hal ini mengakibatkan produk tertentu yang dipilih harus diproses seketika pada saat order tersebut ditugaskan pada suatu pusat kerja. Sedangkan pada flow shop tidak terjadi permasalahan seperti tersebut karena keseragaman output yang diproduksi untuk persediaan. Prioritas order pada flow shop dipengaruhi terutama pada pengirimannnya dibandingkan tanggal pemrosesan. Faktor-faktor tersebut menghasilkan sangat banyak kemungkinan kombinasi dari pembebanan (loading) dan urutan-urutan (sequencing).Perhitungan dari identifikasi dan evaluasi jadwal-jadwal yang mungkin menjadi sulit sehingga banyak perhatian diarahkan pada riset penjadwalan job shop.Selain itu, persiapan atau penjadwalanjob shop, penyesuaian dan pembaharuannya membutuhkan investasi yang besar untuk fasilitas komputer. Pada bagian ini akan dibahas masalah penjadwalan job shop dengan memperhatikan permasalahan pada job loading dan job sequencing. Job loading mengartikan bahwa kita harus memutuskan pada pusat-pusat kerja yang mana
21
suatu job harus ditugaskan.Job sequencing mengartikan bahwa kita harus menentukan bagaimana urutan proses dari bermacam-macam job harus ditugaskan pada mesin-mesin tertentu.
2.6.3.1 Job Shop Loading Ketika order-order pada suatu job shop, kegiatan pertama dari penjadwalan adalah menugaskan order-order tersebut kepada bermacam-macam pusat-pusat kerja untuk diproses.Permasalahan loading menjadi lebih sederhana ketika suatu job tidak dapat dipisah.Meskipun halini sering terjadi, biasanya suatu industry sering dalam prateknya melakukan pemisahaan job dan menugaskan bagianbagian terpisah dari job tersebut kepada pusat-pusat yang berbeda untuk tujuan meningkatkan utilisasi sumber daya. Untuk permasalahan yang sederhana, kita mengasumsikan tidak ada pemisahaan job, maka shop loading dapat dibuat dengan mudah dengan menggunakan Gantt Chart dan Metode Penugasan. Loading dengan gantt chart merupakan cara yang paling sederhana, paling tua dan paling banyak digunakan untuk bermacam-macam aktivitas penjadwalan. Meskipun sederhana dan tervisualisasikan, gantt chart sangat lemah dalam mengevaluasi rencana-rencana alternatif untuk loading. Pengguna harus memakai cara trial error dalam improvisasi jadwal. Bila jumlah job meningkat, proses ini menjadi cukup sulit dan tidak layak.
22
Adapun contoh Gantt Chart dapat dilihat pada gambar di bawah ini sebagai berikut:
Gambar 2.2 Contoh Gantt Chart untuk Penjadwalan Job Shop Sumber : Rosnani Ginting,2007 Loading dengan metode penugasan merupakan cara pembebanan pekerjapekerja untuk job-job yang tersedia dengan tujuan meminimasi total waktu kerja atau total biaya kerja. Metode Hungarian merupakan metode yang biasa dipakai untuk permasalahan ini.Dalam situasi yang lebih kompleks, permasalahan loading dapat diformulasikan dengan suatu bentuk problem transportasi.
2.6.3.2 Job shop sequencing Sekali beberapa job telah ditugaskan (loading) pada pusat kerja tertentu, maka langkah berikutnya adalah menentukan urutan-urutan memprosesnya. Pemrosesan order merupakan hal yang penting karena mempengaruhi lamanya suatu job akan diproses dalam sistem tertentu. Lamanya job dalam proses sistem ini akan mempengaruhi batas waktu janji pengiriman kepada konsumen. Yang tidak kalah pentingnya adalah pengaruh urutan-urutan pemrosesan job terhadap utilisasi sumber daya –sumber daya organisasi, khususnya pada kondisi suplai yang kritis.
23
Penjadwalan job shop meliputi aturan-aturan prioritas sequencing aturanaturan sequencing diaplikasikan untuk seluruh job yang sedang menunggu dalam antrian. Bila pusat kerja relay lowong untuk satu job baru, maka job dengan prioritas terdahulu akan diproses. Pemilihan prioritas sequencing tersebut mempertimbangkan efisiensi penggunaan fasilitas dengan kriteria antara lain, biaya setup, biaya persediaan WIP, waktu menganggur stasiun kerja, presentase waktu menganggur, rata-rata jumlah job yang menunggu, dan sebagainya. Beberapa aturan-aturan sequencing yang umum antara lain adalah sebagai berikut:
•
FIRST COME FIRST SERVED (FCFS) Job yang datang diproses sesuai dengan job yang mana yang datang terlenih dahulu.
•
EARLIEST DUE DATE (EDD) Prioritaskan diberikan kepada job-job yang mempunyai tanggal batas waktu penyerahan (due date) paling awal.
•
SHORTEST PROCESSING TIME (SPT) Job dengan waktu proses terpendek akan diproses lebih dahulu,demikian berlanjut untuk job yang waktu prosesnya terpendek kedua.Aturan SPT ini tidak memperdulikan due date maupun kedatangan order baru.
24
2.7 Teknik Penjadwalan 2.7.1 Aturan Shortest Processing Time (SPT) Pada saat menjadwalkan suatu kumpulan pekerjaan di sebuah prosesor dengan aturan SPT,pekerjaan di urutkan mulai waktu pemrosesan (processing
time) terkecil.Aturan SPT berguna untuk meminimasi waktu alir rata-rata dan meminimasi keterlambatan rata-rata pada prosesor tunggal. Sebagai tambahan,manfaat meminimasi kelambatan rata-rata (mean
lateness) adalah berkurangnya waktu menunggu rata-rata(mean waiting time) sehingga meminimasi rata-rata jumlah pekerjaan yang menunggu dalam antrian (mean task waiting in the queue) yang akan menghasilkan minimasi persediaan barang dalam proses (in process inventory). Suatu hal yang harus diperhatikan ialah urutan.Jika pekerjaan cenderung terus-menerus,aturan SPT akan cenderung menghindari pekerjaan dengan waktu pemorsesan yang lama/panjang.Dengan kata lain,aturan ini akan lebih mementikan pekerjaan-pekerjaan
dengan waktu yang lebih singkat,walaupun
pekerjaan-pekerjaan itu muncul belakangan.Oleh karenanya aturan SPT akan menyebabkan waktu alir rata-rata (mean flow time) yang lebih panjang untuk pekerjaan dengan waktu pemrosesan yang panjang.Solusi untuk masalah di atas ialah dengan mengamati secara periodik terhadap pekerjaan-pekerjaan yang telah menunggu terlalu lama.Pekerjaan yang telah menunggu lama harus dijadwalkan segera sebelum muncul lagi pekerjaan sebagai suatu kelompok dan menjalankan pekerjaan-pekerjaan tersebut seluruhnya sebelum pekerjaan baru muncul.
25
2.7.2 Aturan Bobot SPT Suatu variasi dari aturan SPT adalah aturan penjadwalan dengan menggunakan bobot.Aturan ini digunakan jika tingkat kepentingan dan prioritas tiappekerjaan bervariasi.Semakin besar bobotnya maka semakin besar pula prioritasnya.Dengan membagi waktu pemrosesan (processing time) dengan bobotnya maka akan muncul kecenderungan bahwa pekerjaan yang lebih penting akan dijadwalkan terlebih dahulu. Pada saat menjadwlkan n pekerjaan pada sebuah prosesor tunggal dimana tiap pekerjaan i memiliki bobot relatif wi,maka rata-rata waktu alir terbobot (weighted mean flow time) akan diminimasi dengan mengurutkanya berdasarkan aturan berikut.
t1 t t ≤ 2 ≤ .... ≤ n w1 w 2 wn Sumber : Hendra Kusuma,2009
2.7.3 Aturan Earlist Due Date (EDD) Aturan lainya yang peril diketahui ialah aturan EDD.Aturan ini menyebutkan bahwa pengurutan pekerjaan berdasarkan batas waktu (due-date) tercepat.Pekerjaan dengan saat jatuh tempo palin awal harus dijadwalkan terlebih dahulu dari pada pekerjaan dengan saat jatuh tempo belakangan. Aturan ini bertujuan untuk meminimasi kelambatan maksimum (maximum
lateness) atau meminimasi ukuran kelambatan maksimum (maximum tardiness) suatu pekerjaan.Buruknya,aturan ini menyebabkan jumlah pekerjaan yang terlambat menjadi banyak,serta akan menambah keterlambatan rata-rata (mean
tardiness).
26
2.7.4 Algoritma Hodgson Misalkan penalti atas pekerjaan-pekerjaan yang terlambat adalah sama untuk seluruh pekerjaan dan tak tergantung pada seberapa lama tingkat keterlambatanya,maka aturan EDD akan memberikan hasil yang terbaik jika dan
hanya jika terdapat satu atau nol pekerjaan yang terlambat.Jika terdapat lebih dari satu pekerjaan yang terlambat maka algaritma hodgson akan memberikan hasil yang lebih baik.Algoritma Hodgson adalah sebagai berikut: Step 1
: Susun seluruh pekerjaan dengan menggunakan aturan EDD,jika hanya nol pekerjaan atau suatu pekerjaan yang terlambat,stop.Selain dari itu,lanjut ke step 2.
Step 2
: Mulailah dari awal urutan yang dihasilkan aturan EDD dan lihatlah jadwal tersebut sampai akhir.Tandai pekerjaan pertama yang terlambat.Jika ada pekerjaan berikutnya yang terlambat,ke step 4.Lainya ke step 3.
Step 3
: Misalnya pekerjaan yang terlambat tersebut berada di posisi ke I dalam urutan penjadwalan yang dihasilkan.Periksa pekerjaanpekerjaan lainya yang tidak terlambat dan berada di posisi sebelum posisi
ke
i.Tandai
pekerjaan
dengan
waktu
pemrosesan
terbesar.Pindahkan pekerjaan itu dan ulangi lagi perhitungan waktu penyelesaian
seluruh
pekerjaan
setelah
pemindahan.Kemudian
kembali ke step 2. Step 4
: Letakan semua pekerjaan yang dipindahkan tadi dalam urutan semula diakhir penjadwalan.
27
2.7.5 Aturan Slack Slack di definisikan sebagai selisih antara batas waktu penyelesaian pekerjaan dengan waktu proses pekerjaan tersebut.Besaran slack menggambarkan kelonggaran yang dimiliki oleh pekerjaan yang bersangkutan.Aturan slack menyatakan bahwa pekerjaan dengankelonggaran yang sedikit harus dijadwalkan terlebih dahulu.
2.7.6 Algoritma Wilkerson-Irwin Tujuan yang paling sukar untuk dipenuhi adalah minimasi kelambatan ratarata. Hal ini terjadi jika pinalti atas kelambatan suatu pekerjaan sama besarnya dan berbanding lurus dengan lamanya kelambatan. Tidak ada metode yang mudah untuk menyelesaikan masalah ini. Dalam situasi-situasi khusus, terdapat aturan sebagai berikut: a. Jika hanya terdapat satu atau nol pekerjaan yang terlambat, maka aturan EDD akan meminimasi keterlambatan rata-rata (mean tardiness) b. Jika seluruh pekerjaan memiliki batas waktu (due date) yang sama, atau
jika aturan SPT menghasilkan seluruh pekerjaan terlambat; maka aturan SPT akan meminimasi keterlambatan rata-rata (mean tardiness) c. Aturan minimasi kelonggaran (Slack time) memiliki kecenderungan untuk meminimasi untuk keterlambatan rata-rata, tetapi tidak dapat diterapkan untuk seluruh kasus.
28
Untuk itu Wilkerson-Irwin mengemukakan satu algoritma heuristik yang dapat meminimasi keterlambatan rata-rata. Algoritma Wilkerson-irwin dapat dijelaskan sebagai berikut : Step 1 : Susun urutan pekerjaan berdasarkan aturan EDD atau SPT atau slack.Bandingkan dua pekerjaan pertama didaftar tersebut.Sebut kedua pekerjaan ini sebagai x dan y.Jika max (tx,ty) ≤ max (dx,dy),tempatkan pekerjaan x ke kolom alpha dan pekerjaan y ke kolom beta.Jika kondisi di atas tidak terpenuhi maka tempatkan pekerjaan dengan waktu pemrosesan terpendek ke kolom alpha dan lainya ke kolom beta.Pekerjaan ketiga dalam urutan EDD/SPT/Slack itu ditempatkan dalam kolom gamma. Step 2
: Bandingkan beta dan gamma untuk melihat apakah beta akan dapat dijadwalkan bersama dengan alpha.Jika tbeta ≤ tgamma atau jika Falpha + max { tbeta , tgamma} ≤ max {dbeta,dgamma},pindahkan pekerjaan dikolom beta ke kolom alpha,dan pekerjaan gamma ke kolom beta.Selanjutnya pekerjaan di dalam daftar EDD/SPT/Slack akan ditempatkan di kolom gamma.Jika tidak ada lagi pekerjaan di dalam daftar,tambahkan pekerjaan di kolom alpha dan betake dalam jadwal dan ke step 5.Jika tidak,ulangi step2.Jika kedua kondisi yang disebutkan di atas tak terpenuhi maka kerjakan step 3.
Step3
: Kembalikan pekerjaan di kolom beta ke dalam daftar EDD/SPT/Slack dan pindahkan pekerjaan di kolom gamma ke dalam kolom beta.Bandingkan alpha dan beta untuk melihat apakah beta akan di jadwalkan bersama dengan alpha.Jika talpha ≤ tbeta atau jika Falpha –
29
talpha+ max {talpha,tbeta} ≤ max{dalpha,dbeta},pindahkan pekerjaan di kolom beta ke kolom alpha dan pilih dua pekerjaan berikutnya dalam daftar EDD/SPT/Slack sebagai beta dan gamma yang baru.Ulangi step 2.Jika kedua kondisi di atas tidak dipenuhi maka kerjakan step 4. Step 4
: Pindahkan
pekerjaan
di
kolom
alpha
kembali
ke
daftar
EDD/SPT/Slack dan tempatkan pekerjaan terakhir yang masuk ke dalam jadwal sebagai alpha yang baru.Ke step 3.Jika tidak ada pekerjaan yang telah di jadwalkan,letakkan beta ke dalam jadwal dan dua pekerjaan pertama dalam daftar EDD/SPT/Slack menjadi beta dan gamma.Ke step 2. Step 5
: Bandingkan hasil penjadwalan dengan menggunakan jadwal inisial yang lain yang di masukan ke dalam metode Wilkerson Irwin.Pilih jadwal yang memberikan keterlambatan rata-rata minimum.
Ada kesulitan lain untuk menggunakan pendekatan Wilkerson Irwin, yaitu bahwa langkah yang dijalankannya cukup rumit sehingga membutuhkan waktu pekerjaan yang cukup panjang. Namun bila menggunakan komputer maka pendekatan Wilkerson-irwin ini dapat deprogram sehingga waktu pengolahan datanya menjadi lebih cepat.
2.8 Penjadwalan Satu Prosesor Pengurutan pekerjaan disebuah prosesor digunakan untuk mencapai tujuan minimasi
waktu
alir
rata-rata
atau
minimasi
keterlambatan
–
keterlamabatan.Seperti telah disebutkan,makespan penjadwalan suatu prosesor selalu kontan besarnya.Walaupun penjadwalan satu prosesor tidak akan
30
berpengaruh pada waktu alir rata-rata(mean flow time),keterlambatan ratarata(mean lateness),atau ukuran kelambatan rata-rata (mean tardiness).Bedworth dan Bailey menyebutkan bahwa terdapat teknik-teknik tertentu untuk mencapai sasaran penjadwalan satu prosesor.Teknik tersebut diperinci seperti terlihat pada tabel 2.1.
Tabel 2.1Teknik Penjadwalan untuk Mencapai Sasaran Penjadwalan Satu Prosesor Sasaran Utama Minimasi waktu Alir Minimasi waktu Kelambatan (lateness)
Sasaran Antara Minimasi waktu alir Minimasi waktu alir terbobot Minimasi kelambatan maksimum Minimasi jumlah pekerjaan terlambat Minimasi kelambatan rata-rata Minimasi Minimasi keterlambatan maksimum keterlambatan Minimasi keterlambatan rata-rata (tardiness) Minimasi keterlambatan total Sumber : Hendra Kusuma,2009
Teknik Penjadwalan Aturan SPT Aturan Bobot SPT Aturan EDD Aturan Hodgson Aturan SPT Al.Wilkerson Irwin Aturan Slack
Perlu pula diperhatikan bahwa penjadwalan merupakan basis perencanaan ditingkat floor-shop.Penjadwalan dilakukan hanya satu kali pada awal penugasan.Jika muncul pekerjaan baru,maka pekerjaan itu disimpan dalam daftar tunggu dan baru dijadwalkan bersama dengan pekerjaan lainya setelah kumpulan penjadwalan pertama selesai diproses.Sebagai contoh,jika penjadwalan dilakukan untuk 10 pekerjaan dan baru dikerjakan satu atau dua pekerjaan,maka pekerjaan ke 11 akan masuk ke dalam daftar tunggu yang baru akan dijadwalkan untuk dikerjakan setelah 10 pekerjaan pertama selesai.Pekerjaan ke 11 itu akan dijadwalkan dengan pekerjaan 11,12,13, dan seterusnya.Hal ini di lakukan untuk
31
menghindari terjadinya penundaan sautu pekerjaan akibat munculnya pekerjaan lain dengan prioritas lebih tinggi.
2.9 Penjadwalan m Prosesor Paralel Pada penjadwalan prosesor jamak parallel, setiap pekerjaan hanya perlu memasuki salah satu prosesor.Situasi ini dapat digambarkan seperti gambar 2.3.Dengan adanya prosesor jamak, pekerjaan penjadwalan menjadi agak sukar bila dibandingkan dengan penjadwalan pada prosesor tunggal. Jika penjadwalan satu prosesor memiliki masalah pada bagaimana urutan pekerjaan yang akan memberikan hasil optimal, maka pada prosesor paralel masalah yang terjadi ialah urutan pekerjaan yang paling optimal dan prosesor manakah yang akan mengerjakan pekerjaan tersebut.
Gambar 2.3 Gambaran Prosesor Pararel Sumber : Hendra Kusuma,2009
2.9.1 Minimasi Waktu Alir Rata-Rata Masalah minimasi mean flow time pada m prosesor parallel dapat dipecahkan dengan menggunakan algoritma: Step 1
: Urutkan seluruh pekerjaan dengan urutan SPT
32
Step 2
: Dengan mengambil urutan pekerjaan dari awal sampai dengan selesai satu per satu, tugaskan
pada prosesor yang memiliki waktu
penugasan terkecil.
2.9.2 Minimasi Makespan Dengan adanya prosesor jamak,maka makespan akan tergantung pada penyusunan urutanpekerjaan (pada prosesor tunggal makespan tidak tergantung dari urutan pekerjaan).Oleh karena itu pada prosesor jamak pararel,masalah minimasi makespan perlu di bahas.Dalam masalah ini tidak ada satupun aturan penjadwalan yang akan menghasilkan makespan yang optimal sehingga diperlukan suatumetode heuristic yang cukup mendekati solusi optimal.Algoritma ini dilakukan dengan aturan LPT (Longest Processing Time) dan setelah pembebanan pekerjaan selesai dilakukan,urutanya dibalik sehingga menjadi SPT.Algoritma ini dapat dijelaskan sebagai berikut: Step 1
: Urutkan n pekerjaan tersebut dengan menggunakan aturan LPT
Step 2
: Jadwalkan pekerjaan yang di hasilkan dari step 1 diatas pada tiapprosesor dengan pembebanan waktu pekerjaan yang terkecil.
Step 3
: Setelah seluruh pekerjaan selesai di bebankan,balikan urutan pekerjaan pada tiap prosesor hingga urutanya mengikuti aturan SPT.
Intisari algoritma ini terletak pada gagasan bahwa meminimasi makespan akan sama dengan meminimasi waktu idle di akhir penugasan.Untuk meminimasi makespan,di inginkan sebanyak mungkin pekerjaan dengan waktu proses yang pendek di akhir penjadwalan sehingga terdapat sebanyak alternative pengisian blok waktu tersisa yang tersedia.Maksud pembalikan urutan pekerjaan menjadi SPT ialah agar urutan yang diperoleh tetapmenghasilkan mean flow time yang
33
kecil (ingat bahwa minimasi mean flow time diperoleh dengan menggunakan metode SPT).
2.9.3 Minimasi Keterlambatan Jika sasaran penjadwalan ialah minimasi keterlambatan atau keterlambatan (lateness/tardiness),maka
tidak ada
aturan yang menjamin akan
dapat
memberikan hasil optimal.Walapun demikian berbagai aturan penjadwalan satu prosesor seperti EDD,Slack,Hodgson,dan Wilkerson-Irwin dapat digunakan dengan hasil yang cukup memuasakan di m prosesor pararel.Untuk meminimasi keterlambatan maksimum (maximum tardiness) digunakan aturan EDD,untuk meminimasi total keterlambatan (total tardiness) digunakan aturan slack, untuk meminimasi kelambatan rata-rata digunakan algoritma Wilkerson-Irwin dan untuk meminimasi jumlah pekerjaan yang terlambat dapat digunakan algoritma Hodgson.Algoritma-algoritma di atas dapat di jelaskan sebagai berikut : a. Minimasi Keterlambatan Maksimum Step 1 : Urutkan seluruh pekerjaan dengan menggunakan aturan EDD. Step 2 : Dengan mengambil pekerjaan satu per satu dari hasil pengurutan EDD,jadwalkan pekerjaan tersebut pada prosesor dengan waktu proses terkecil. b. Minimasi keterlambatan total Step 1 :
Urutkan seluruh pekerjaan menggunakan aturan Slack
Step 2 :Dengan mengambil pekerjaan satu per satu dari hasil pengurutan Slack,Jadwalkan pekerjaan tersebut pada prosesor dengan waktu proses terkecil.
34
c. Minimasi Keterlambatan Rata-Rata Lakukan Step 1 tiga kali,masing-masing dengan aturan SPT,EDD,dan Slack.Pilih jadwal yang di hasilkan dari step 3 yang akan mengahasilkan rata-rata keterlambatan terkecil. Step 1 :
Susun pekerjaan dengan salah satu aturan di atas (SPT,EDD atau Slack).
Step 2 :
Dengan mengambil pekerjaan satu per satu dari hasil pengurutan di atas,jadwalkan pekerjaan tersebut pada prosesor dengan waktu proses terkecil.
Step 3 :
Perlakukan setiap prosesor secara terpisah dan minimasikan kelambatan rata-rata pekerjaan pada masing-masing prosesor dengan menggunakan aturan Wilkerson-Irwin.
d. Minimasi Jumlah Pekerjaan yang Terlambat Step 1 :
Susun pekerjaan dengan aturan EDD.
Step 2 :
Dengan mengambil pekerjaan satu per satu dari hasil pengurutan di atas,jadwalkan pekerjaan tersebut pada prosesor dengan waktu proses terkecil.
Step 3 :
Perlakukan setiap prosesor secara terpisah dan minimasikan jumlah pekerjaan yang terlambat yang terlambat pada masingmasing prosesor dengan menggunakan aturan Hodgson.
