BAB 3 LANDASAN TEORI
3.1
Definisi Penjadwalan Penjadwalan dapat didefinisikan sebagai keputusan dalam penugasan dan waktu
untuk memulai pekerjaan yang menggunakan sumber daya seperti manusia, peralatan, dan fasilitas yang digunakan untuk kegiatan proses produksi untuk pekerjaan [Martinich, 1997]. Penjadwalan dapat juga diartikan sebagai suatu petunjuk atau indikasi apa saja yang harus dilakukan, dengan siapa, dan dengan peralatan apa yang digunakan untuk menyelesaikan suatu pekerjaan pada waktu tertentu [Scroeder, 2000]. Keputusan dalam suatu penjadwalan yang diartikan pada penugasan adalah berupa mengurutkan pekerjaan (sequencing) dan waktu (timing) untuk memulai pekerjaan, dimana untuk menentukan semuanya itu harus diketahui urutan operasinya terlebih dahulu. Penjadwalan selalu berhubungan dengan pengalokasian sumber daya yang ada pada jangka waktu tertentu, hal tersebut adalah proses pengambilan keputusan yang tujuannya adalah untuk optimalitas [Pinedo, 2002]. Penjadwalan berperan penting dalam industri manufaktur dan industri servis. Penjadwalan tidak bisa lepas dari sequencing yaitu pekerjaaan/job mana yang harus dikerjakan terlebih dahulu dalam suatu pesanan. Penjadwalan bisa menjadi suatu masalah apabila terdapat suatu sekumulan tugas yang datang secara bersamaan pada waktu tertentu, seperti per bulan, per minggu, per hari, atau skala waktu lainnya, sedangkan fasilitas yang dimiliki perusahaan terbatas. Biasanya jika hal ini terjadi, maka akan diberlakukan aturan prioritas.
12 Untuk membuat suatu penjadwalan maka masukan yang dibutuhkan untuk membuatnya adalah mencakup jenis dan banyaknya job yang akan diproses, urutan ketergantungan antar operasi/proses produksinya, waktu proses untuk masing-masing operasi, serta fasilitas yang dibutuhkan oleh setiap operasi. Dari masukan tersebut, penjadwalan yang dihasilkan adalah berupa urutan pekerjaan yang akan dijadwalkan. Dalam membuat penjadwalan yang baik, perusahaan membutuhkan suatu perencanaan produksi dan pengendalian produksi agar fasilitas yang digunakan untuk memproduksi dapat digunakan secara efisien, dengan demikian perencanaan dan pengendalian produksi yang dibutuhkan tersebut antara lain adalah sebagai berikut : 1. Membuat suatu daftar pesanan yang datang dengan memperhitungkan kapasitas produksinya. 2. Sebelum pesanan tersebut diproduksi, periksa terlebih dahulu mengenai ketersediaan bahan bakunya. 3. Menentukan batas waktunya untuk pekerjaan yang ada, dan melakukan pengawasan saat produksi berlangsung. 4. Dari aktifitas produksi yang berjalan dibuat laporannya sebagai feedback. 5. Dilakukan pengwasan terhadap efisiensi peroduksi yang berjalan.
3.2
Tujuan Penjadwalan Diadakannya penjadwalan tentu terdapat tujuan-tujuan yang ingin dicapai oleh
suatu perusahaan yang pastinya akan lebih menguntungkan bagi perusahaan. Tujuan adanya penjadwalan adalah untuk mengurangi waktu keterlambatan dari batas waktu yang ditentukan agar dapat memenuhi batas waktu yang disetujui dengan konsumen,
13 dengan penjadwalan perusahaan juga dapat meningkatkan produktifitas mesin dan mengurangi waktu menganggur. Dengan produktifitas mesin meningkat dan waktu menganggur berkurang, maka secara tidak langsung perusahaan dapat mengurangi ongkos produksi, dan dengan mengurangi waktu keterlambatan dan jika tepat waktu dalam pemenuhan produksi, dan dengan mengurangi waktu keterlambatan dan jika tepat waktu dalam pemenuhan produk perusahaan, maka hal ini dapat menjadi nilai tambah bagi perusahaan dalam hal pelayanan. Jika tujuan penjadwalan ini dapat tercapai maka hal ini dapat juga dijadikan suatu keuntungan dan strategi bagi perusahaan dalam pemuasan pelanggan.
3.3
Permasalahan Penjadwalan Produksi Seperti yang sudah diungkapkan sebelumnya bahwa suatu penjadwalan produksi
dapat menjadi suatu masalah yang rumit jika terdapat sekumpulan tugas yang datang secara bersama-sama, jika demikian solusi yang dapat diambil adalah dengan membuat suatu pengurutan pekerjaan/job dengan memperhitungkan batasan waktu, dan fasilitas yang ada. Penjadwalan akan semakin sulit ditangani jika terdapat sekumpulan job yang diproses dengan banyak mesin. Dengan adanya pengurutan job maka diharapkan dapat memenuhi tujuan dari diadakannya penjadwalan, yaitu mengurangi waktu keterlambatan dari batas waktu yang ditentukan agar dapat diusahakan memenuhi batas waktu yang ditetapkan dengan konsumen, dengan demikian perusahaan dapat lebih meningkatkan kegunaan sumber daya yang terdapat dalam perusahaan sehingga dapat meningkatkan produktifitas mesin dan mengurangi waktu menganggur.
14 3.4
Fungsi Penjadwalan Fungsi penjadwalan di dalam sebuah sistem produksi harus berinterksi dengan
fungsi-fungsi lainnya. Interaksi ini begantung pada sistem yang ada dalam perusahaan, bisa melalui jaringan komputer, dapat juga melalui rapat. Lantai produksi bukanlah satu-satunya bagian dari organisasi yang menetukan jalannya proses penjadwalan. Proses penjadwalan juga dipengaruhi oleh proses perencanaan produksi yang menangani jangka waktu menengah dan jangka waktu panjang keseluruhan perusahaan. Proses ini bertujuan untuk mengoptimalkan komposisi produk yang dihasilkan oleh perusahaan dan alokasi sumber daya jangka panjang berdasarkan inventori, peramalan permintaan, dan kebutuhan sumber daya. Keputusankeputusan yang diambil pada level perencanaan yang lebih tinggi dapat memberikan dampak langsung pada proses penjadwalan. Dalam lingkungan manufaktur, fungsi penjadwalan harus berinterkasi dengan prosedur pengambilan keputusan lain yang digunakan dalam perusahaan/pabrik. Salah satu sistem yang cukup banyak digunakan adalah MRP (Material Requirement Planning). Setelah semua jadwal disusun, semua sumber bahan baku dan sumber daya yang diperlukan harus tersedia pada waktu yang telah ditentukan bersama-sama oleh perencanaan produksi.
3.5
Klasifikasi Penjadwalan Penjadwalana produksi dapat diklasifikasikan dilihat dari perbedaan kondisi
yang mendasarinya, klasifikasi penjadwalan yang sering terjadi dalam proses produksi adalah sebagai berikut :
15 1. Berdasarkan mesin yang digunakan : a. Penjadwalan pada mesin tungal (Single machine shop) b. Penjadwalan pada mesin jamak/paralel (m machine) 2. Berdasarkan strategi desain proses : a. Flow Shop Proses produksi yang berdesain flow shop bergerak dalam satu arah, identik dengan pola aliran dari satu mesin ke mesin lain walaupun penggunaan mesinnya tidak selalu berurutan. P1
P2
M1
M2
M3
M4
P3
dimana P adalah pekerjaan / job dan M adalah mesin. Gambar 3.1 Aliran Flow Shop Flow Shop ada banyak jenisnya, antara lain adalah : -
Continuous Flow, ditujukan untuk produksi secara masal, dimana produk yang dibuat hanya untuk satu macam produk saja.
-
Dedicated Repetitive, ditujukan untuk produksi yang jumlahnya masih dapat terhitung (part diskrit) dan produk yang dibuat terdiri dari satu macam produk tetapi banyak variasi, namun tidak memerlukan waktu setup.
-
Batch Flow, ditujukan untuk produksi masal atau part diskrit untuk satu macam produk dengan banyak variasi (lebih banyak dari
16 dedicated repetitive) namun untuk setiap pergantian variasi memerlukan waktu setup. -
Mixed Model Repetitive Batch Flow, ditujukan untuk produksi yang bisa dihitung, dengan ciri satu fasilitas namun dapat digunakan untuk banyak jenis produk, dimana waktu setup adalah hanpir nol.
b. Job Shop Proses produksi dengan aliran job shop tidak selalu sama untuk setiap jobnya. Setiap job dikerjakan dengan urutan mesin tertentu sesuai dengan kebutuhan prosesnya. Dengan demikian pola alirannya berbedabeda, tidak selalu dalam satu arah. Keluaran dari setiap mesin untuk jenis job shop bisa berarti langsung sebagai produk jadi, dapat juga berarti produk setengah jadi. P1
P2
M1
M2
M3
M4
P3
dimana P adalah pekerjaan / job dan M adalah mesin. Gambar 3.2 Aliran Job Shop 3. Berdasarkan product positioning : a. Make to order Jumlah dan jenis produk yang dibuat berdasarkan permintaan dari konsumen, biasanya salah satu tujuan kebijakan ini adalah mengurangi biaya simpan.
17 b. Make to stock Jumlah dan jenis produk terus menerus dibuat untuk disimpan dalam inventory. 4. Berdasarkan pola kedatangan job : a. Statik, pengurutan job terbatas pada pesan yang ada. Job yang baru tidak mempengaruhi pengurutan job yang sudah dibuat. b. Dinamik, pengurutan job selalu diperbaharui jika ada job baru yang datang. 5. Berdasarkan waktu proses : a. Deterministik, waktu proses yang diterima sudah diketahui dengan pasti. b. Stokastik, waktu proses yang diterima belum pasti, oleh karena itu perlu diperkirakan dengan menggunakan distribusi probabilitas.
3.6
Kriteria Optimalitas Ada kriteria-kriteria optimalitas dalam menyusun penjadwalan, antara lain
adalah : 1. Berkaitan dengan waktu [Jay Heizer and Barry Render, 2001] : a. Meminimalkan waktu penyelesaian (makespan). b. Meminimalkan tardiness. c. Memaksimalkan utilitas mesin d. Meminimalkan persediaan dalam proses. e. Meminimalkan waktu tunggu pelanggan.
18 2. Berkaitan dengan ongkos Kriteria ini berkaitan dengan biaya produksi, seperti mengurangi denda akibat terlambatnya pengiriman barang/produk.
3.7
Aturan Prioritas Aturan prioritas (priority rule) adalah aturan dalam penjadwalan produksi untuk
menentukan pekerjaan/job mana yang harus dikerjakan terlebih dahulu. Aturan prioritas ini digunakan untuk membantu menyusun penjadwalan dalam usaha mencapai tujuan penjadwalan, yaitu meminimasi keterlambatan, dan meningkatkan utilitas mesin. Beberapa aturan prioritas yang sering digunakan antara lain adalah : 1. Acak (Random) Mengerjakan job secara urutan yang acak, job yang mana saja dapat diproses terlebih dahulu 2. FCFS (First Come First Serve) Mengerjakan job sesuai dengan urutan waktu kedatangannya, yang datang lebih awal akan diproses terlebih dahulu. 3. SPT (Shortest Processing Time) Proses pengerjaan job dilakukan sesuai dengan waktu proses dari yang paling kecil. 4. EDD (Earliest Due Date) Urutan pengerjaan job dilakukan berdasarkan dari batas waktu penyelesaian yang lebih kecil.
19 5. LPT (Longest Processing Time) Aturan ini bertolak belakang dengan SPT, yaitu mengerjakan job berdasarkan urutan waktu proses dari yang paling besar/lama. 6. Critical Ratio Aturan ini mengurutkan job-job dengan menghitung waktu sisa sampai dengan batas waktu kerjanya.
3.8
Tardiness Tertimbang Total Wighted tardiness (tardiness tertimbang) merupakan salah satu fungsi tujuan
yang umum dalam masalah penjadwalan. Beberapa fungsi tujuan yang lain adalah makespan, weighted flowtime, maximum flowtime, maximum tardiness, weighted number of tardy jobs dan weighted earliness plus weighted tardiness. Dalam masalah penjadwalan dengan fungsi tujuan tardiness tertimbang, tiap job memiliki bobot (kepentingan) dan due date. Bobot merepresentasikan tingkat kepentingan dari suatu job. Bobot yang lebih tinggi menunjukkan tingkat kepentingan yang lebih besar. Jika waktu akhir penyelesaian job melebihi due date atau batas waktu penyelesainnya maka job tersebut dikenakan suatu penalti yang direpresentasikan oleh bobotnya. Tardiness didefinisikan sebagai selisih waktu antara waktu akhir penyelesaian suatu job dengan due date jika waktu akhir pnyelesaian job lebih besar dari due date. Secara matematis, fungsi tujuan tardiness tertimbang total dirumuskan sebagai berikut. Misalkan Di dan wi masing-masing menyatakan due date dan bobot untuk tiap job i, Ci menyatakan waktu akhir penyelesaian job i. Jika Ti didefinisikan sebagai tardiness untuk job i, maka :
20 Ti = Ci – Di =0
jika Ci > Di jika Ci ≤ Di
Dengan demikian dapat dikatakan nilai Ti adalah : Ti = max {0, Ci-Di} Fungsi tujuan meminimumkan tardiness tertimbang total selanjutnya dapat dirumuskan sebagai berikut : Min
∑w T
t i
i
Dengan Ti = max {0, Ci-Di} , ∀i
3.9
Algoritma Relaksasi Lagrange Relaksasi Lagrange merupakan suatu algoritma yang semakin banyak digunakan
dalam berbagai penerapan pemrograman matematika berskala besar. Penerapan relaksasi lagrange dimotivasi oleh adanya pengamatan bahwa banyak masalah pemrograman bilangan bulat dapat dimodelkan dengan mudah dengan menghilangkan nasty side constraints [Fisher, 1995]. Nasty side constraints dihilangkan dari himpunan pembatas dan ditempatkan pada fungsi tujuan. Ini dikenal dengan istilah dualisasi (dualizing) nasty side constraints. Proses dualisasi ini menghasilkan suatu masalah yang relatif mudah untuk dipecahkan dan solusinya memberikan suatu batas bawah bagi solusi optimal dari masalah awal. Bagi masalah penjadwalan dengan kriteria meminimumkan tardiness tertimbang total untuk pendekatan relaksasi lagrange adalah sebagai berikut (disebut masalah P) : Minimasi J =
∑w T
t i
i
dengan memperhatikan pembatas-pembatas :
21 •
precedence : cij ≥ cil + tij ; ∀i , j ; j , l є J
•
ketersediaan sumber :
∑∑ δ i
•
ijhk
≤ M hk
j
kebutuhan waktu proses : bij = cij – tij + 1 ; ∀i , j ; j є J
dengan : cij
adalah slot waktu akhir (penyelesaian) pengerjaan operasi j untuk job i.
bij
adalah slot waktu awal pengerjaan operasi j untuk job i.
tij
adalah waktu pemrosesan/pengerjaan operasi j untuk job i.
δ ijhk adalah variabel biner 0 atau 1; δ ijhk = 1 jika operasi j untuk job i menggunakan sumber h pada slot waktu k, δ ijhk = 0 jika sebaliknya. Mhk adalah konstanta yang menunjukkan ketersediaan sumber h pada slot waktu k. Misalkan J adalah nilai tujuan optimal untuk masalah P dan diberikan suatu vektor pengali Lagrange tak negatif πhk untuk merelaksasi pembatas ketersediaan sumber
∑∑ δ i
ijhk
≤ M hk maka akan diperoleh masalah Lagrange R, dimana :
j
R : min
⎛
⎞
⎝ i, j
⎠
{ ∑ wt Ti + ∑ π hk ⎜⎜ ∑ δ ijhk − M hk ⎟⎟ } i
h ,k
dengan memperhatikan pembatas precedence dan pembatas kebutuhan waktu proses. Karena nilai L(π) merupakan batas bawah untuk sembarang π ≥ 0, maka masalahnya sekarang adalah bagaimana menentukan
pengali Lagrange
π* yang
memberikan batas bawah terbaik. Masalah ini disebut dengan masalah Dual Lagrange, dan dinyatakan dengan masalah D, yaitu :
22
D : maks L , dengan L ≡
{
Ni ⎛ ⎞ ⎜ − ∑π hk M hk + min∑⎜ wiTi + ∑∑π hkδ ijhk ⎟⎟ h, k i ⎝ j =1 h,k ⎠
dengan memperhatikan pembatas πhk
}
≥ 0 , pembatas precedence dan pembatas
kebutuhan waktu proses. Jika suatu operasi job dikerjakan pada slot waktu tertentu dan sumber tertentu, maka δ ijhk = 1. Jadi, jika πhk dikalikan dengan δ ijhk untuk slot waktu k dan sumber h Ni
yang digunakan, hasilnya akan tetap bernilai πhk. Maka nilai
∑∑ π j =l h , k
hk
δ ijhk
akan
sama dengan nilai π pada sumber h yang digunakan dan slot waktu k yang terpakai (dari slot waktu awal operasi (bij) sampai slot waktu akhir operasi (cij)), yaitu Ni
cij
∑ ∑π j =l k =bij
ijhk
Sehingga dapat dilakukan penyederhanaan sebagai berikut :
D : maks L , dengan L ≡
{
Ni cij ⎛ ⎞ ⎜ − ∑π hk Mhk + min∑ wiTi + ∑∑π ijhk ⎟ ⎜ ⎟ h,k i ⎝ j =1 k =bij ⎠
}
dan jika job-job adalah independen maka minimum dari penjumlahan adalah jumlah dari minima sehingga bentuk rumusan D dapat dinyatakan sebagai berikut :
D : maks L , dengan L ≡
{
Ni cij ⎛ ⎞ − ∑π hk M hk + ∑min⎜ wiTi + ∑∑π ijhk ⎟ ⎜ ⎟ h, k i j =1 k =bij ⎝ ⎠
dengan memperhatikan pembatas πhk kebutuhan waktu proses.
}
≥ 0 , pembatas precedence dan pembatas
23 Berdasarkan rumusan Dual Lagrange di atas, maka model permasalahan tersebut dapat disederhanakan menjadi dekomposisi dari submasalah untuk tiap job i (untuk { πhk } yang diberikan) sebagai berikut : Ni
Ri : min Li dengan Li ≡
cij
wiTi + ∑∑π ijhk j =1 k =bij
dengan memperhatikan pembatas
3.10
•
cij ≥ cil + tij ; ∀i , j ; j , l є J
•
bij = cij – tij + 1 ; ∀i , j ; j є J
Metode Subgradien Masalah yang muncul pada algoritma Relaksasi Lagrange adalah bagaimana
mendapatkan pengali Lagrange πhk* yang memberikan batas bawah terbaik. Untuk mendapatkan solusi dual Lagrange yang optimal πhk* , terdapat berbagai teknik yang tersedia, diantaranya adalah metode elipsoid, metode ascent direction dan metode subgradien. Di antara metode-metode tersebut, metode subgradien merupakan metode yang paling banyak diterapkan karena kemudahannya dalam implementasinya. Misalkan πhk menyatakan vektor dari pengali Lagrange maka : πhk = πhk + ∆πhk dimana ∆πhk = λ
ΔLi H
dengan : •
H merupakan horizon waktu dari job
24 •
λ merupakan suatu skalar yang nilainya dipilih antara 0 dan 2. Selanjutnya untuk meningkatkan konvergensi geometrik menuju keoptimalan, Fisher (1995) menentukan nilai λ terbaik adalah 2.
•
ΔLi = Li − Li dimana Li n = 1,3Li sehingga ΔLi = 0,3Li n
Prosedur pencarian nilai tersebut diusulkan oleh Caramis & Kaskavelis (1998), didapat dari percobaan numerik yang berulang-ulang.
3.11
Pemrograman Dinamis Pemrograman dinamis (Dynamic Programming) adalah prosedur matematis
yang
terutama
dirancang
untuk
memperbaiki
efisiensi
perhitungan
masalah
pemrograman matematis tertentu dengan menguraikannya menjadi bagian-bagian masalah yang lebih kecil, dan karena itu lebih sederhana dalam perhitungan. Pemrograman dinamis pada umunya menjawab masalah dalam tahap-tahap, dengan setiap tahap meliputi tepat satu variabel optimasi. Perhitungan di tahap yang berbedabeda dihubungkan melalui perhitungan rekursif dengan cara menghasilkan pemecahan optimal yang mungkin bagi seluruh masalah. Nama pemrograman dinamis muncul karena penggunaan metode ini yang melibatkan pengambilan keputusan yang berkaitan dengan waktu (seperti masalah sediaan). Tetapi, situasi lain saat waktu bukan merupakan faktor juga dipecahkan oleh pemrograman dinamis, untuk alasan ini, nama lain dari pemrograman dinamis adalah pemrograman multitahap (multistage programming), karena prosedur ini umumnya menentukan pemecahan dalam tahap-tahap.
pada
25 Sebagai suatu konsep, pemrograman dinamis lebih luwes dibanding kebanyakan model dan metode matematika dalam riset operasi. Penerapan pendekatan pemrograman dinamis telah mampu menyelesaikan aneka masalah, seperti : alokasi, muatan, capital budgeting, pengawasan persediaan, penjadwalan, dan lain lain. Tidak seperti linear programming, dalam masalah pemrograman dinamis tak ada formulasi matematika yang baku, sehingga merupakan kesulitan bagi seorang pemula untuk mempelajari pemrograman dinamis ini. Pemrograman dinamis sebagai suatu teknik optimasi memiliki beberapa kelebihan diantaranya : •
Proses pemecahan suatu masalah yang kompleks menjadi sub-sub masalah yang lebih kecil membuat sumber permasalahan dalam rangkaian proses masalah tersebut menjadi lebih jelas untuk diketahui.
•
Pendekatan pemrograman dinamis dapat diaplikasikan untuk berbagai macam masalah pemrograman matematika, karena pemrograman dinamis cenderung lebih fleksbel daripada teknik optimasi lain.
•
Prosedur perhitungan pemrograman dinamis juga memperkenankan bentuk analisis sensitivitas terdapat pada setiap variabel status (state) maupun pada variabel yang ada di masing-masing tahap keputusan (stage).
•
Pemrograman dinamis dapat menyesuaikan sistematika perhitungannya menurut ukuran masalah yang tidak selalu dengan tetap dengan tetap melakukan perhitungan satu per satu secara lengkap dan menyeluruh Disamping memiliki kelebihan, pemrograman dinamis juga memiliki beberapa
kekurangan, diantaranya :
26 •
Penggunaan pemrograman dinamis jika tidak dilakukan secara tepat, akan mengakibatkan ketidakefisienan biaya maupun waktu. Karena dalam menggunakan pemrograman dinamis dibutuhkan keahlian, pengetahuan, dan seni untuk merumuskan suatu masalah yang kompleks, terutama yang berkaitan dengan penetapan fungsi transformasi dari permasalahan tersebut.
•
Pemrograman dinamis tidak memiliki suatu bentuk formulasi matematika yang baku untuk digunakan secara konsekuen, sehingga perhitungan untuk menghasilkan keputusan optimal yang dilakukan terbatas pada kondisi tertentu.
•
Hambatan
terbesar
pada
pemrograman
dinamis
adalah
masalah
dimensionalitas, yaitu masalah dimana peningkatan variabel keadaan yang digunakan dalam perhitungan pemrograman dinamis akan menambah beban memori komputer serta menambah lama waktu perhitungan. Tahap keputusan (stage) sebagai salah satu unsur penting dalam model pemrograman dinamis merupakan bagian-bagian masalah yang lebih sederhana. Serangkaian tahap keputusan yang berurutan dan terkait satu sama lain akan membentuk keseluruhan masalah. Keadaan sistem merupakan salah satu konsep yang paling penting dalam suatu model pemrograman dinamis, karena keadaan sistem mewakili hubungan antara tahaptahap keputusan yang berurutan. Dimana ketika setiap tahap dioptimalkan secara terpisah, maka keputusan yang dihasilkan tersebut layak dan optimal untuk keseluruhan masalah. Lebih lanjut, hal tersebut memungkinkan pengambilan keputusan adalah
27 optimum untuk tahap-tahap selanjutnya tanpa harus melakukan pemeriksaan terhadap pengaruh keputusan yang telah diambil sebelumnya. Definisi keadaan biasanya adalah konsep yang paling tidak jelas dalam perumusan pemrograman dinamis. Tidak ada jalan yang mudah untuk mendefinisikan keadaan, tetapi petunjuk untuk itu dapat ditemukan dengan mengajukan dua pertanyaan berikut : •
Hubungan apa yang mempersatukan tahap-tahap itu?
•
Informasi apa yang diperlukan untuk mengambil keputusan yang layak pada tahap sekarang tanpa memeriksa kelayakan dari keputusan yang diambil pada tahap-tahap sebelumnya ? Alternatif keputusan merupakan pilihan keputusan yang harus ditentukan agar
keputusan pada tiap-tiap tahap optimal, sehingga keputusan akhir untuk keseluruhan masalah juga optimal. Alternatif dalam model pemrograman dinamis dinyatakan dalam bentuk variabel keputusan yang memiliki batasan-batasan tertentu. Penyelesaian masalah dalam pendekatan pemrograman dinamis dapat dilakukan secara maju (forward recursive equation) ataupun secara mundur (backward recursive equation). Perbedaan utama antara forward recursive equation dan backward recursive equation terletak dalam cara mendefinisikan status (state) atau yang sering disebut dengan definisi keadaan. Secara umum dirumuskan sebagai berikut : •
forward recursive equation (perhitungan dari depan ke belakang) f0(X0) = 0 fi*(Xi) = opt {Rj(kj)@fj-1*(Xj@kj)} , j = 1,2,…,n
28 •
backward recursive equation (perhitungan dari belakang ke depan) fn(Yn) = 0 fj*(Yj) = opt {Rj(kj)@fj+1*(Yj@kj)} , j = 1,2,…,n
Keterangan : f*(X) atau f*(Y)
= optimum return function
X atau Y
= status (state)
X @ k atau Y @ k
= fungsi transisi
j
= tahap ke-
k
= variabel keputusan
@
= simbol atau lambang operasi matematik
Pada umumnya, penyelesaian masalah dengan forward recursive equation dan backward recursive equation akan mengarah kepada efisiensi perhitungan yang berbeda jika tahap-tahap keputusan dalam model pemrograman dinamisnya dikondisikan dalam urut-urutan yang spesifik. Secara umum, masalah optimasi dapat diselesaikan dengan prosedur forward recursive equation maupun backward recursive equation. Tetapi untuk masalah tertentu, khususnya masalah yang tahap-tahap keputusannya berhubungan dengan periode waktu, penyelesaian masalah tidak dapat menggunakan prosedur forward recursive equation namun harus menggunakan prosedur backward recursive equation. Formulasi pemrograman dinamis untuk pemecahan masalah Ni
Ri : min Li dengan Li ≡ adalah sebagai berikut :
cij
wiTi + ∑∑π ijhk j =1 k =bij
29
Vi , j (bi , j ) = min{ Δ i , j wiTi +
= Δ i , j wiTi +
ci , j
∑π
k = bi , j
ci , j
∑π
k = bi , j
ijhk
ijhk
+ Vi , j −1 (bi , j −1 )}
+ min Vi , j −1 (bi , j −1 )
dimana
Vi , j (bi, j ) adalah nilai/biaya minimum subproblem Li
Δ i, j = 1 jika operasi (i,j) adalah operasi tahap terakhir dan 0 untuk yang lainnya.
3.12
Algoritma List Scheduling
Menurut Hurink dan Knust (2001), list scheduling adalah konsep yang telah digunakan secara luas dalam masalah penjadwalan. Pada dasarnya algoritma list scheduling adalah sebuah prosedur yang menempatkan sejumlah urutan pekerjaan (dibuat dalam bentuk list sesuai kriteria keputusan penjadwalan) pada posisi jadwal yang sesuai dengan jumlah pekerjaan tersebut. Prosedur tersebut menempatkan pekerjaan-pekerjaan tersebut pada jadwal berdasarkan list pekerjaan yang telah dibuat. Menurut Ladsaria (2002) algoritma ini pada dasarnya adalah melakukan langkah-langkah sebagai berikut :
•
Menentukan prioritas atau aturan tertentu terhadap semua operasi/aktivitas.
•
Mengurutkan operasi/aktivitas berdasarkan prioritas tersebut.
•
Mengisi tempat/sumber yang tersedia pertama dengan operasi/aktivitas sesuai urutan yang telah dibuat dengan memperhatikan operasi/aktivitas yang telah mengisi tempat/sumber yang telah tersedia (hubungan ketergantungan antar operasi).
30 Prioritas atau pengurutan operasi amat menentukan kualitas dari jadwal dan terpenuhinya tujuan dari penjadwalan yang dilakukan. Suprayogi dan Mardiono (1997) memodifikasi algoritma list scheduling dari Luh et al.(1990) dalam masalah penjadwalan job majemuk operasi tunggal sumber majemuk paralel simultan. Konsep dasar algoritma yang dikembangkan tersebut adalah sebagai berikut : Setiap waktu awal aktivitas yang didapatkan dari suatu solusi matematis yang belum layak diurutkan dari yang terkecil sampai yang terbesar. Jika terdapat waktu awal aktivitas yang sama, digunakan kriteria biaya (berdasarkan besarnya bobot job dan keterlambatan terhadap due date aktivitas tersebut) untuk pemilihan aktivitas yang akan didahulukan. Maksudnya, jika aktivitas tersebut terlambat untuk satu satuan waktu berapakah biaya tambahan yang terjadi. Semakin kecil biaya yang terjadi maka aktivitas tersebut akan didahulukan. Kemudian berdasarkan urutan aktivitas tersebut, tiap aktivitas dimasukkan ke dalam slot waktu penjadwalan dengan memperhatikan kendala ketersediaan tiap sumber yang digunakan untuk mengerjakan aktivitas-aktivitas. Ketika sumber yang dibutuhkan sudah digunakan (kapasitas tidak memenuhi lagi untuk slot waktu k), aktivitas-aktivitas yang tersisa (membutuhkan sumber tersebut pada slot waktu k) akan ditunda selama satu unit slot waktu. Dengan algoritma ini, setiap solusi awal yang akan dijadikan sebagai dasar untuk melakukan list scheduling akan menentukan apakah hasil list scheduling yang dilakukan baik atau buruk. Solusi yang baik akan menghasilkan jadwal layak yang baik, sementara solusi yang buruk akan menghasilkan jadwal layak yang buruk.
31 Pseudocode dari algoritma list scheduling menurut Suprayogi dan Mardiono (1997) dalam masalah penjadwalan banyak job operasi tunggal dengan sumber majemuk paralel simultan adalah sebagai berikut : Setelah mendapatkan waktu awal untuk tiap operasi pada tiap job melalui penjadwalan job individu dan iterasi subgradien pada Relaksasi Lagrange, maka dilakukanlah prosedur list scheduling. Misal didefinisikan Si adalah urutan dari N – i + 1 job, yaitu 1 , 2, …, N – i + 1 yang berkaitan dengan satu himpunan N = I +1 slot waktu awal {Bj}, yang diurutkan dari paling kecil ke terbesar sedemikian sehingga B1≤B2≤…≤BN-i+1 dan jika Bl = Bl+1 maka wl(Tl + 1) ≥ wl+1(Tl+1 +1 ). Diberikan Si dan {Mhk} Langkah 0 :
Tetapkan i =1
Langkah 1 :
Tetapkan k = 1
Langkah 2 :
Jika Mhk ≠ 0 (h = 1,...,Hi,
Hi є H) maka jadwalkan job i mulai dari
waktu k, Bi = k, tetapkan Mhl = Mhl – 1 untuk l =k, k+l,…,k+ti-1 dan lanjutkan ke langkah 5. Jika tidak, lanjutkan ke langkah 3. Langkah 3 :
Tetapkan k = k+1, jika Bi ≥ k, lanjutkan ke langkah 2. Jika tidak, lanjutkan ke langkah 4.
Langkah 4 :
Untuk semua job yang belum terjadwal sedemikian sehingga Bi < k, tetapkan Bi = k dan urutkan Si, dan lanjutkan ke langkah 2.
Langkah 5 :
Tetapkan i = i + 1. Jika i ≤ N kembali ke langkah 1. Jika tidak behenti.
32 3.13
Rekayasa Piranti Lunak
3.13.1 Pengertian Rekayasa Piranti Lunak
Menurut Sommerville (1995) rekayasa piranti lunak mencakup tiga elemen utama yang mengkontrol keseluruhan dari proses pengembangan piranti lunak , yaitu : 1. Metode-metode (Methods) Menyediakan cara teknis membangun piranti lunak, terdiri dari :
•
Perencanaan proyek estimasi
•
Analisis kebutuhan sistem dan piranti lunak
•
Rancangan struktur data
•
Arsitektur program
•
Algoritma prosedur
•
Pengkodean
•
Testing
•
Pemeliharaan
2. Alat-alat (tools) Memberi dukungan otomatis terhadap metode Computer Aided Software Engineering (CASE) yang mengkombinasikan piranti lunak dan piranti keras. 3. Prosedur-prosedur (procedures/theories) Merupakan penggabungan antara metode dengan alat bantu.
33 3.13.2 Model Rekayasa Piranti Lunak
Model rekayasa piranti lunak yang digunakan adalah Classic Cycle (Waterfall Model). Model ini dipilih karena sistem yang dirancang akan mudah dievaluasi walaupun belum mendapatkan hasil akhir. Terdiri dari lima tahap : 1. Requirements definition Dalam tahapan ini, difokuskan pada perancangan piranti lunak yang akan dibangun, pembatasan kegunaan dan tujuan yang akan dicapai oleh sistem. Dikumpulkan pula informasi yang dibutuhkan dan dipahami fungsi apa saja yang diinginkan sesuai dengan kesepakatan dalam konsultasi antara pengguna dan perancang piranti lunak. 2. System and software design Dalam tahapan ini, didesain penggambaran modul dari piranti lunak secara terperinci dan dilakukan pengkajian kualitas. Tahapan ini berfokus pada struktur data, arsitektur piranti lunak dan prosedur secara detil. Selain itu dilakukan juga langkah pengkodean dengan mengubah desain yang telah dirancang ke dalam bentuk yang dapat dibaca oleh mesin. 3. Implementation and unit testing Sebuah piranti lunak terdiri dari sekumpulan unit program (program units) yang memiliki tugas dan deskripsi masing-masing yang lebih spesifik. Pada tahapan ini dilakukan pengujian setiap unit program secara terpisah dengan melihat kesesuaian unit dengan spesifikasi yang diinginkan.
34 4. Integration and system testing Setelah pengujian setiap unit program, maka semua unit program yang ada akan diintegrasikan menjadi sebuah piranti lunak yang lengkap dan dilakukan pengujian pada semua fungsi dalam piranti lunak yang sudah dibangun. Pengujian ini dimaksudkan untuk menemukan kemungkinan adanya kesalahan serta memastikan keluaran yang dihasilkan telah sesuai dengan yang diinginkan. 5. Operation and maintenance Piranti lunak yang baik harus mampu melakukan penyesuaian terhadap perubahan/peningkatan yang mungkin terjadi di masa mendatang, baik dikarenakan peningkatan kebutuhan pengguna ataupun pengembangan dari lingkungan di luar sistem piranti lunak tersebut sehingga tidak perlu dibuat program baru hanya untuk memenuhi kebutuhan yang mungkin menjadi lebih kompleks. Kelebihan model ini adalah :
•
Hasil akhir sesuai dengan kebutuhan yang diinginkan.
•
Bila terjadi kesalahan atau kekurangan dalam proses perancangan dapat langsung dievaluasi dan dilengkapi.
•
Penghematan biaya karena hasil akhir dari perancangan piranti lunak tidak akan mengalami perubahan atau penambahan dalam skala besar karena telah sesuai dengan kebutuhan dan keinginan.
35 Kekurangan model ini adalah :
•
Dibutuhkan pemakai yang mampu memprediksikan kebutuhan secara terperinci dan lengkap, agar tidak mengalami penambahan berkali-kali yang akan menghambat perancangan.
•
Bila ada penambahan kebutuhan, maka akan mengulang proses pembuatan dari awal yang akan memboroskan waktu.
•
Tidak ada gambaran hasil akhir dari perancangan.
•
Penjelasan dalam perancangan harus jelas, karena hal ini akan menjadi acuan dalam proses desain pengkodean.
Berikut ini merupakan tahapan dalam Classic Cycle atau Waterfall Model menurut Sommerville (1995) :
Requirements definition System and Software Design Implementation and Unit Testing Integration and System Testing Operation and Maintenance
Gambar 3.3 Waterfall Model
