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. Keputusan-

keputusan 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.

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

P2P3

P1

M1 M2 M3 M4

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 berbeda-

beda, 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.

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.

P2P3

P1

M1 M2 M3 M4

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 jika Ci > Di

= 0 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 ∑i

itTw

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 = ∑i

itTw

dengan memperhatikan pembatas-pembatas :

21

• precedence : cij ≥ cil + tij ; i∀ , j ; j , l є J

• ketersediaan sumber : hki j

ijhk M≤∑∑δ

• 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

hki j

ijhk M≤∑∑δ maka akan diperoleh masalah Lagrange R, dimana :

R : min { ∑i

itTw + }⎟⎟⎠

⎞⎜⎜⎝

⎛−∑∑

jihkijhk

khhk M

,,δπ

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 ≡ { }∑ ∑∑∑ ⎟⎟⎠

⎞⎜⎜⎝

⎛++−

=i

N

j khijhkhkii

khhkhk

i

TwM1 ,,

min δππ

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

yang digunakan, hasilnya akan tetap bernilai πhk. Maka nilai ∑∑=

iN

lj khijhkhk

,δπ 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

∑∑= =

i ij

ij

N

lj

c

bkijhkπ

Sehingga dapat dilakukan penyederhanaan sebagai berikut :

D : maks L , dengan L ≡ { }∑ ∑∑∑ ⎟⎟⎠

⎞⎜⎜⎝

⎛++−

= =i

N

j

c

bkijhkii

khhkhk

i ij

ij

TwM1,

min ππ

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 ≡ { }∑ ∑∑∑ ⎟⎟⎠

⎞⎜⎜⎝

⎛++−

= =i

N

j

c

bkijhkii

khhkhk

i ij

ij

TwM1,

min ππ

dengan memperhatikan pembatas πhk ≥ 0 , pembatas precedence dan pembatas

kebutuhan waktu proses.

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 :

Ri : min Li dengan Li ≡ ∑∑= =

+i ij

ij

N

j

c

bkijhkiiTw

1

π

dengan memperhatikan pembatas

• cij ≥ cil + tij ; i∀ , j ; j , l є J

• bij = cij – tij + 1 ; i∀ , j ; j є J

3.10 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 = HLiΔ

λ

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.

• in

ii LLL −=Δ dimana in

i LL 3,1= sehingga ii LL 3,0=Δ

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 berbeda-

beda 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 pada

umumnya menentukan pemecahan dalam tahap-tahap.

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 tahap-

tahap 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

Ri : min Li dengan Li ≡ ∑∑= =

+i ij

ij

N

j

c

bkijhkiiTw

1

π

adalah sebagai berikut :

29

( ) ( )}min{, 1,1,,,

,

,

−−=

++Δ= ∑ jiji

c

bkijhkiijiji bVTwjbiV

ji

ji

π

( )1,1,, min,

,

−−=

++Δ= ∑ jiji

c

bkijhkiiji bVTw

ji

ji

π

dimana

( )jbiV ji ,, adalah nilai/biaya minimum subproblem Li

ji,Δ = 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) :

Gambar 3.3 Waterfall Model

Requirements definition

System and Software Design

Integration and System Testing

Operation and Maintenance

Implementation and Unit Testing