8 BAB 2 LANDASAN TEORI
1.7
Penjadwalan Penerbangan Penjadwalan dapat diartikan sebagai suatu 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). Definisi lain penjadwalan adalah suatu petunjuk atau indikasi apa saja yang harus dilakukan, dengan siapa, dan dengan peralatan apa yang digunakan untuk menyelesaikan suatu pekerjaan pada waktu tertentu. Keputusan dalam suatu penjadwalan yang diartikan pada penugasan adalah berupa mengurutkan pekerjaan dan watu untuk memulai pekerjaan, dimana untuk menentukan semuanya itu harus diketahui urutan operasinya terlebih dahulu. Penjadwalan menurut Pinedo (2002) selalu berhubungan dengan pengalokasian sumber daya yang ada pada jangka waktu tertentu, hal tersebut adalah proses pengambilan keputusan yang tujuannya adalah untuk optimalitas. Penyusunan jadwal penerbangan adalah hal yang wajib dilakukan oleh setiap maskapai penerbangan. Jadwal yang tersusun akan mempengaruhi keoptimalan utilisasi pesawat dan juga biaya operasional. Penyusunan jadwal adalah hal yang cukup rumit karena dalam penyusunan jadwal banyak faktor yang harus diperhitungkan. Oleh karena itu, penyusunan jadwal dibagi menjadi empat tahap yang dapat digambarkan sebagai berikut:
9
Gambar 0.1 Penjadwalan Penerbangan
1.7.1
Schedule Design Tahap ini dapat dibagi lagi menjadi dua bagian yaitu: 1.
Time table construction adalah sebuah proses penentuan jadwal penerbangan dengan mempertimbangkan banyaknya permintaan terhadap suatu rute pada suatu segmen waktu;
2.
Yield Management adalah sebuah proses untuk menentukan jumlah kapasitas penumpang pada tiap kelas yang untuk mengoptimalkan pendapatan dengan mempertimbangkan hasil dari proses time table management. Proses ini dimulai dari saat jadwal ditentukan dan mulai dijual hingga terjadinya penerbangan dari jadwal tersebut.
1.7.2
Fleet Assignment Fleet assignment hanya berlaku pada maskapai yang cukup besar dan memiliki beberapa tipe pesawat dengan perbedaan kapasitas yang cukup signifikan. Pada maskapai yang tidak memiliki banyak pesawat dengan tipe berbeda-beda, tahap ini dapat diabaikan. Setelah tahap schedule design dilakukan
10 dan diperoleh hasil berupa jadwal dari rute-rute yang akan dilayani, tahap selanjutnya adalah menentukan jenis pesawat mana yang akan ditugaskan untuk setiap rute yang telah ditentukan. Tahap ini lah yang disebut tahap fleet assignment. Pesawat dengan kapasitas penumpang besar akan dialokasikan untuk rute dengan permintaan penumpang besar, dan pesawat dengan kapasitas penumpang yang lebih kecil akan dialokasikan untuk rute dengan permintaan penumpang yang lebih sedikit.
1.7.3
Aircraft Routing Aircraft routing atau sering disebut juga tail assignment adalah proses identifikasi armada pesawat mana yang akan digunakan untuk melayani rute-rute penerbangan yang sudah ditentukan sebelumnya. Proses yang dilakukan dalam tail assignment adalah merencanakan waktu setiap pesawat yang akan diterbangkan untuk melayani rute mana, jadwal maintenance dengan memberikan pesawat alternatif yang akan menggantikan dan aktivitas lainnya yang ada di darat. Di dalam menentukan semua constraint operasional seluruh aktivitas tersebut bergantung kepada kepastian tanggal dan jam dari masingmasing proses dalam suatu periode waktu. Dalam menentukan tail assignment ini ada beberapa constraint penting yang sangat mempengaruhi tahap ini.
11 A. Maintenance Constraint Tujuan utama dilakukannya maintenance dalam sebuah airline adalah untuk memberikan keamanan dan membuat pesawat memiliki daya jual untuk setiap jadwal yang ada. Beberapa tujuan efisiensi dari maintenance itu adalah: 1.
Meminimalkan waktu out of service, Karena keuntungan dari sebuah
pesawat
bergantung
pada
ketersediaannya
untuk
digunakan pada jadwal yang telah disusun, perusahaan harus berusaha keras untuk merancang sistem maintenance dengan standar yang tinggi sekaligus meminimalkan waktu out of service dari pesawat yang sedang dipelihara (maintenance). 2.
Memanfaatkan waktu maksimum yang disediakan untuk program inspeksi dan pemeriksaan: bagian program ini adalah yang paling memakan banyak biaya
dalam operasional
airline, tapi
harus berorientasi pada waktu pengerjaan yang minimal. 3.
Personil dan beban kerja: setiap inspeksi harus dilakukan teknisi yang sudah memiliki lisensi dari organisasi terkait sehingga terjamin kualitasnya. Utilisasi dari setiap personil juga harus dimaksimalkan untuk mengurangi biaya tenaga kerja.
4.
Memanfaatkan fasilitas pada tingkat paling maksimum: investasi yang besar untuk sektor fasilitas seperti untuk gedung, peralatan dan perlengkapan khusus agar tidak keluar dengan percuma.
12 B. Connection Constraint Connection Constraint adalah salah satu constraint dasar yang menyatakan hubungan antara dua aktivitas yaitu pemberangkatan dan pendaratan. Constraint ini dapat dilihat secara mudah dengan cara hanya memberikan waktu jeda yang minimum antara aktivitas kedatangan dan keberangkatan. Dalam waktu yang minimum itu proses untuk pembersihan, pengisian bahan bakar dan persiapan lainnya untuk pemberangkatan selanjutnya dilakukan. Pada sebuah bandar udara yang cukup ramai waktu koneksi ini juga dipengaruhi oleh waktu tunggu armada dan waktu transfer antar gates dan terminal yang ada. Secara umum, biasanya selisih waktu pesawat antara kedatangan dan keberangkatan selanjutnya sedikitnya 30-45 menit. Jika memungkinkan, setelah melakukan pendaratan sebuah pesawat diharapkan langsung kembali melakukan penerbangan selanjutnya, tentunya setelah melakukan persiapan tertentu.
C. Flight Restriction Constraint Constraint ini adalah kondisi dimana suatu pesawat tidak dapat melakukan penerbangan atau pendaratan atau hal yang lainnya yang dikarenakan suatu alasan tertentu, seperti kondisi landasan yang tidak dapat didarati karena cuaca dan lainnya sebagainya.
13 D. Constraint Lainnya Beberapa kondisi constraint yang juga mempengaruhi selain constraint waktu koneksi, maintenance, larangan penerbangan adalah constraint-constraint dalam masalah penugasan crew.
1.7.4
Crew Pairing Crew Pairing adalah proses penentuan crew dengan menetukan siapa saja yang akan melayani dalam suatu rute penerbangan dengan biaya yang minimal tanpa memperdulikan spesifikasi crew tersebut. Proses penentuan ini menentukan crew yang sama dalam penerbangan yang berurutan dengan titik awal dan titik akhir crew yang sama. Hasil optimal dari penentuan crew ini adalah biaya dikeluarkan seminimal mungkin dan semaksimal mungkin crew tersebut dapat melayani kebutuhan yang ada dengan memperhatikan peraturan keselamatan yang ada. Selanjutnya proses pengaturan crew akan dilanjutkan dengan berfokus pada penugasan masing-masing individu dengan mempertimbangkan kualifikasi, waktu perjalanan, permintaan dari crew tersebut dan faktor lainnya dengan meminimalkan fungsi biaya. Tahap ini disebut tahap crew rostering.
1.8
Pengoperasian Penerbangan dan Penjadwalan Awak Pesawat Oleh karena penjadwalan penerbangan saat dipublikasikan harus disertai dengan awak pesawat penerbangan perusahaan, departemen operasi penerbangan harus memastikan bahwa penerbangan dijadwalkan dengan cara yang menjamin
14 mereka dioperasikan secara efisien tapi aman. Berikut ini adalah faktor-faktor operasional yang penting untuk perencanaan penjadwalan: 1. Panjang landasan terbang di bandara sangat berpengaruh pada pengoperasian pesawat terbang karena landasan yang pendek akan memakan bahan bakar lebih banyak sedangkan landasan yang cukup panjang akan lebih hemat bahan bakar bila digunakan secara maksimal. 2. Kapasitas bahan bakar pesawat: pesawat dengan kapasitas bahan bakar yang sedikit tentunya akan diprioritaskan untuk terbang pada rute-rute berjarak pendek untuk menghindari keharusan pengisian bahan bakar di tengah jalan yang akan memakan biaya bahan bakar lebih besar untuk mendarat dan lepas landas lagi di bandara transit. 3. Cuaca musiman yang merugikan: pada musim dingin, cuaca akan kurang menguntungkan untuk penerbangan malam pada beberapa kota yang tidak tersedia fasilitas hangar. 4. Pengendali lalu lintas udara (Air traffic control) dan routing: Air traffic control (ATC) yang menyusun rute lalu lintas penerbangan dapat mengakibatkan pesawat harus melewati jalur yang lebih panjang dan membutuhkan bahan bakar lebih banyak. 5. Batasan jam terbang awak pesawat: menurut peraturan resmi CASR. setiap awak pesawat yang ikut serta dalam pengoperasian pesawat terbang, memiliki batasan waktu kerja yang harus ditaati oleh setiap perusahaan. Untuk konfigurasi pesawat dengan dua pilot (1 kapten dan 1 copilot), dalam 24 jam mereka dapat dijadwalkan terbang
15 selama maksimal 9 jam. Perusahaan juga tidak diperkenankan menjadwalkan penerbangan untuk pilot yang telah memiliki jam terbang sebanyak 30 jam dalam 7 hari, atau 110 jam dalam 30 hari, atau 1050 jam dalam 1 tahun. Apabila terjadi keadaan di luar kendali seperti masalah cuaca sehingga persyaratan tersebut terlanggar, maka pilot bersangkutan harus diberikan cuti selama 24 jam kerja penuh.
1.9
Constraint Programing Constraint Programming adalah suatu pendekatan deklaratif dalam problem solving dengan cara mendeskripsikan permasalahan menjadi himpunan batasan–batasan permasalahan
(constraints). optimisasi
Untuk
menyelesaikan
(optimization
problems).
kombinatorial Dalam
atau
constraint
programming, kita cukup memodelkan permasalahan sebagai suatu constraint satisfaction problem, dan selanjutnya solver yang akan mencari solusi atas permasalahan tersebut. Dalam memodelkan permasalahan, kita menggunakan variabel, domain dan batasan (constraints) yang merepresentasikan himpunan penyelesaian. Sebuah constraint pada dasarnya merupakan relasi dari beberapa variabel yang memiliki nilai yang dinyatakan dalam suatu domain. Constraint merupakan batasan terhadap nilai yang mungkin untuk suatu variabel. Beberapa kelebihan dari constraint programming: 1. Outputnya singkat; 2. Programnya sederhana sehingga dapat dengan mudah diadaptasi bila terjadi perubahan kebutuhan;
16 3. Karena programnya dapat dibuat dan dimodifikasi dengan cepat, maka sangat mungkin untuk bereksperimen untuk mendapatkan penyelesaian yang paling efisien dan waktu komputasi tercepat.
1.9.1
Constraints Satisfaction Problem Constraint satisfaction terkait dengan permasalahan yang domainnya terbatas (finite domains) dan biasanya disebut sebagai Constraint Satisfaction Problems (CSP). CSP berfungsi untuk medapatkan nilai dari variabel yang memenuhi semua constraint. CSP didefinisikan sebagai: 1. Himpunan variabel X = {x1 ,L, x n } ; 2. Domain yang merupakan himpunan terbatas dari nilai yang mungkin untuk setiap variabel Di ; 3. Himpunan constraint yang membatasi nilai yang mungkin untuk setiap variabel. Dalam constraint programming terdapat tiga tahapan yang harus selalu ada, yaitu: 1. Deklarasi domains dari setiap variabel; 2. Deskripsi dari constraint poblem (problem model) 3. Mencari solusi yang tepat dengan menggunakan backtrack search, atau mencari solusi optimal berdasarkan branch-and-bound search.
17 Solusi dalam CSP adalah suatu pemetaan nilai dari domain setiap variabel yang memenuhi semua constraint. Solusi dari sebuah CSP diperoleh melalui pencarian (searching) secara sistematik terhadap semua nilai dari variabel yang mungkin berdasarkan constraint yang ada. Dalam hal ini metode pencarian untuk mendapatkan solusi dapat dibagi atas dua kelompok utama, yaitu melalui solusi parsial (partial value assignments) dan solusi lengkap (complete value assignments) terhadap semua variabel. Dalam propagation,
constraint yaitu
programming
memangkas
atau
juga
dikenal
memendekkan
istilah
constraint
pencarian
dengan
menggunakan constraint yang ada. Setiap constraint memiliki algoritma filtering yang dapat mengurangi jumlah domain dari variabel yang ada dalam constraint tersebut, dengan cara membuang nilai yang tidak mungkin menjadi solusi permasalahan. Algoritma ini dipanggil setiap kali sebuah domain dari variabel dalam constraint mengalami perubahan dan perubahan ini dipropagasikan terhadap domain dari variabel lainnya dan begitu seterusnya. Untuk menutupi kekurangan dari local propagation (incompleteness/lack of shortage), dilakukan pengelompokan beberapa constraint menjadi sebuah constraint khusus yang disebut sebagai global constraint. Global constraints adalah kumpulan dari beberapa constraint kecil yang diperlakukan sebagai sebuah unit yang lebih besar (gabungan).
18 1.9.2
Constraint Satisfaction Optimization Problem Kadangkala dalam kehidupan nyata, dibutuhkan suatu solusi yang terbaik. Standar dari teknik constraint satisfaction adalah hanya mencari solusisolusi yang mungkin, tapi ini dapat diperluas untuk mendapatkan solusi yang optimal. Untuk mendapatkan solusi yang optimal digunakan Constraint Satisfaction Optimization Problem (CSOP). Kualitas dari solusi biasanya diukur berdasarkan suatu fungsi yang disebut fungsi objektif. CSOP terdiri atas sebuah CSP standar dan sebuah fungsi optimisasi yang memetakan setiap solusi terhadap nilai numeriknya. Sebagian besar aplikasi industri menggunakan konsep CSOP ini. Algoritma yang paling banyak digunakan untuk mendapatkan solusi yang optimal dalam CSOP adalah Branch and Bound. Algroritma Branch and Bound ini menggunakan heuristic function yang memetakan partial labeling terhadap suatu nilai numerik dengan algoritma depth first search untuk mendapatkan solusi. Dalam proses pencarian, bila nilai domain melewati constraint yang ada, maka subtree yang ada di bawah partial labeling tersebut dipangkas untuk melakukan propagasi. Solusi yang paling optimal berdasarkan constraint dipilih sebagai solusi. Algoritma Branch and Bound adalah metode algoritma umum untuk mencari solusi optimal dari berbagai permasalahan optimisasi, terutama untuk optimisasi diskrit dan kombinatorial. Algoritma Branch and Bound juga merupakan metode pencarian di dalam ruang solusi secara sistematis. Algoritma Branch and Bound membangun ruang solusinya dengan skema BFS (Breadth First Search).
19
1.10 Collumn Generation Pemrograman linier (linier programming) adalah salah satu bahasan dalam optimisasi yang berkembang cukup pesat. Perumusan masalah pemrograman linier beserta pemecahannya secara sistematis baru dimulai pada tahun 1947 ketika George B Dantzig merancang sebuah metode untuk keperluan angkatan udara AS. Dalam perkembangan selanjutnya diperlukan pendekatan lebih khusus untuk memecahkan masalah pemrograman linier yang melibatkan banyak variabel dan/atau constraint. Untuk masalah pemrograman linier yang mempunyai bentuk khusus, yaitu block-angular. Dantzeig dan Wolfe pada tahun 1960 sudah merumuskan metode yang dapat memecahkan metode tersebut secara lebih efisien. Suatu masalah pemrograman linier dikatakan berbentuk primal-block angular jika memiliki sejumlah constraint umum, yaitu constraint yang memuat semua variabel yang muncul dalam masalah. Pandang masalah pemrograman linier dalam bentuk primal-block angular sebagai berikut.
20 Maksimumkan Z terhadap
= C1T X 1
A1 X 1
+
+ C 2T X 2
+ ... + C Tp X p
+ ... +
A2 X 2
Ap X p
=
…. (1)
B0
= B1 = B2
D1 X 1 D2 X 2 O
Dp X p
= Bp
X k ≥ 0, k = 1,..., p; Dimana untuk k = 1,K, p ukuran matriks Xk, Ak, Bk, Ck, Dk masingmasing adalah (nk x 1), (mo x nk), (mk x 1), (nk x 1), dan (mk x nk); sedangkan Bo p
berukuran (mo x 1). Constraint
∑A k =1
constraint
umum
(common
k
X k = B0 untuk selanjutnya disebut sebagai constraint),
constraint
sedangkan
Dk X k = Bk (k=1,…,p) disebut constraint bebas. Dengan demikian, masalah p
pemrograman linier (1) di atas mempunyai
∑m k =0
Masalah
pemrograman
linier
(1)
p
k
constraint dan
∑n k =0
menurut
k
variabel.
Dantzig,
dapat
didekomposisikan menjadi sub-sub masalah yang lebih kecil dengan tidak menghilangkan karakteristik masalah awalnya. Kemudian solusi dari sub-sub masalah ini digunakan untuk memodifikasi masalah awalnya sehingga diperoleh masalah pemrograman linier baru yang identik dan lebih sederhana. Prosedur untuk menentukan solusi basis dari masalah pemrograman linier tersebut selengkapnya adalah sebagai berikut. Langkah 1: Pandang constraint bebas dari masalah (1), yaitu
21
Dk X k = Bk (k = 1,..., p)
…(2)
yang mempunyai mk constraint. Constraint-constraint ini ditambah dengan syarat kenonnegatifan X k ≥ 0 mendefinisikan suatu himpunan solusi fisible. Asumsikan bahwa constraint (2) adalah himpunan konveks yang terbatas. Misalkan jumlah titik ekstrim dari himpunan tersebut adalah sk . Secara teori diketahui bahwa setiap titik sebarang Xk dapat dinyatakan sebagai kombinasi liner konveks dari titik-titik ekstrimnya. Dengan kata lain, Xk dapat dituliskan sebagai berikut.
X k = λ k ,1 X
(1) k
+ λk ,2 X
( 2) k
+ ... + λ k , sk X
( sk ) s
sk
= ∑ λ k ,i X k(i )
…(3)
i =1
sk
λk ,1 + λk , 2 + ... + λk ,s = ∑ λk ,i = 1 k
λ k ,i ≥ 0, i = 1,..., s k
i =1
(k = 1,..., p ),
Dimana X k(1) ,..., X k( sk ) adalah titik-titik ekstrim dari himpunan fisibel yang didefinisikan oleh himpunan constraint bebas (2). Titik-titik ekstrim ini dapat ditentukan dengan menyelesaikan (2) ditambah dengan syarat kenonnegatifan
Xk ≥ 0. Langkah 2: Dengan mensubtitusikan (3) ke dalam (1), maka constraint bebas (2) dapat dieliminasi dari masalah awal. Sehingga, setelah melewati proses ini masalah pemrograman liniernya menjadi s1
s2
sp
i =1
i =1
i =1
Z = ∑ (C1T X 1( i ) )λ1,i + ∑ (C 2T X 2( i ) )λ 2,i + ... + ∑ (C Tp X p( i ) )λ p ,i
…(4)
22 terhadap constraint s1
∑(A
T 1
i =1
s1
∑ i =1
X
(i ) 1
s2
)λ1,i + ∑ ( A X i =1
sp
(i ) 2
)λ 2,i + ... + ∑ ( ATp X p( i ) )λ p ,i = B0 i =1
λ1,i = 1
s2
∑λ i =1
T 2
=1
2 ,i
sp
∑λ i =1
p ,i
=1
λ k ,i ≥ 0, i = 1,..., s k
(k = 1,..., p).
Jelas bahwa variabel dari masalah (4) adalah λ k ,i . Titik-titik ekstrim X k(1) ,..., X k( sk ) didapatkan dari himpunan constraint bebas ditambah dengan syarat
kenonnegatifan, yaitu Dk X k = Bk , X k ≥ 0 (k = 1,..., p) . Jika didefinisikan masalah pemrograman linier (4)
U k ,i = C kT X k(i ) , Wk ,i = Ak X k(i ) ; dimana i= 1,…,sk
(k = 1,…,p),
didekomposisikan, maka akan berubah menjadi s1
s2
sp
i =1
i =1
i =1
Z = ∑ U 1,i λ1,i + ∑ U 2,i λ2,i + ... + ∑ U p ,i λ p ,i
…(5)
terhadap constraint s1
∑W1,i λ1,i i =1
+
s2
∑ W 2 ,i λ 2 , i i =1
+ ... +
sp
∑W i =1
p ,i
λ p ,i
=
B0
23 s1
∑λ i =1
= 1
1,i
s2
∑λ i =1
= 1
2 ,i
s2
∑λ i =1
λk ,i ≥ 0, i = 1,..., s k
2 ,i
= 1
(k = 1,..., p) .
Masalah (5) diatas kita sebut sebagai masalah induk (master problem). p
Masalah ini mempunyai (mo + p) constraint dari
∑s k =1
k
variabel. Dalam hal ini
untuk menjamin adanya proses optimisasi, kita mengasumsikan bahwa p
( m0 + p ) < ∑ s k . k =1
dengan mengingat penurunan zj-cj dalam metode simpleks, maka sub masalah kek didefinisikan dengan ⎡Wk ,i ⎤ z k ,i − c k ,i = C BT AB−1 ⎢ ⎥ − U k ,i ⎢⎣e k ⎥⎦
…(6)
⎡ Ak X k( i ) ⎤ ⎥ − C T X (i ) , =πT ⎢ k k ⎢ ⎥ e k ⎣⎢ ⎦⎥
dimana e k adalah vektor satuan berdimensi p yang bernilai 1 pada baris ke-k dan bernilai 0 pada baris lainnya; sedangkan π T = C BT AB−1 adalah vektor pengali simpleks
yang
berukuran
(1
x
(mo
+
p)).
Dengan
memandang
24
π T = (π 1T : π 01 ,..., π 0 p ) , dimana π 1T berukuran (1xm0) dan π 0k (k = 1,…,p ) konstan, maka (6) akan menjadi
z k ,i − c k ,i = π 1T Ak X k(i ) + π 0 k − C kT X k(i )
…(7)
= −(C kT − π 1T Ak ) X k(i ) + π 0 k Penentuan harga z k ,i − c k ,i yang paling negatif (sebagai syarat vektor kolom masuk) adalah identik dengan mencari harga Xk yang mampu memaksimumkan
Z k = (C kT − π 1T Ak ) X k
terhadap constraint yang terkait
dengannya. Oleh karenanya, pandang submasalah ke-k berikut: maksimumkan Z k = (C kT − π 1T Ak ) X k
…(8)
terhadap constraint Dk X k = Bk
Xk ≥ 0 Misalkan solusi optimal dari masalah (8) adalah X k(q ) . Titik ini adalah salah satu titik ekstrim dari himpunan constraint bebas ke-k yang memberikan z k ,i − c k ,i paling negatif. Dengan demikian, kita akan membangkitkan kolom
⎡Wk ,q ⎤ ⎡ Ak X k( q ) ⎤ ⎥ ⎥=⎢ ⎢ ⎢ ⎥ ⎥ ⎢ ⎢⎣ e k ⎥⎦ ⎢⎣ e k ⎥⎦ Untuk memasuki basis dalam masalah induk (5). dalam masalah induk kolom ini berhubungan dengan variabel λ k , q ; sedangkan koefisien harga yang berhubungan dengan kolom ini adalah U k ,q = C kT X k( q ) . Proses diatas diulangi untuk semua nilai k,yaitu k = 1,…,p.
25 Untuk lebih jelasnya bagaimana metode dekomposisi dengan teknik column generation dijalankan, berikut ini diberikan algoritma dekomposisinya. Asumsikan bahwa solusi basis fisibel awal dari masalah induk (5) beserta
AB−1
matriks basis
dan pengali simpleks π T = (π 1T : π 01 ,..., π 0 p )
sudah
didapatkan. Langkah 1: Dengan menggunakan pengali simpleks π 1T , selesaikan submasalah (8) untuk mendapatkan solusi optimal X k(q ) dan nilai fungsi objektif optimal z k0 . Langkah 2: Hitunglah nilai min {z k − c k } , yaitu dari (7) diketahui bernilai − z k0 + π 0 k . Jika min {z k − ck } ≥ 0 , maka proses dihentikan karena solusi sudah
optimal. Dan solusi dari masalah awal (1) adalah
X * = ( X 1* , X 2* ,..., X *p ) T , sk
dimana X k* = ∑ λ*k ,i X k( i ) , k = 1,..., p . i =1
⎡ Ak X k( q ) ⎤ ⎥, Langkah 3: Jika min {z k − ck } < 0 , maka bangkitkan kolom ⎢ ⎢ ⎥ ⎢⎣ e k ⎥⎦
yang mana kolom ini berhubungan dengan variabel λ k , q . Koefisien harga yang berhubungan
dengan
kolom
ini
adalah
U k ,q = C kT X k( q ) .
Dan
dengan
menggunakan operasi pivoting dalam metode simpleks diperoleh invers basis dan vektor pengali simpleks yang baru. Kemudian kembali pada langkah 1.
26 1.11 Database
Database merupakan suatu bentuk pengorganisasian data pada media eksternal dengan tujuan mempermudah pengaksesan, dalam hal ini penyimpanan atau pengambilan data. Menurut Connolly (2002), database merupakan sekumpulan data yang berhubungan secara logikal dan deskripsi dari data ini dirancang untuk memenuhi kebutuhan informasi dari suatu organisasi. Metode yang digunakan untuk mengakses database dalam aplikasi ini adalah DBMS (Database Management System) dengan model RDBMS (Relational Database Management System). Menurut Connoly (2002), DBMS adalah sistem piranti lunak yang memungkinkan pengguna untuk mendefinisikan, membuat, memelihara, dan mengontrol akses ke dalam suatu database, dimana dengan kata lain, seluruh akses ke database harus melalui DBMS. Sementara RDBMS merupakan pengembangan dari DBMS yang menitik-beratkan kepada hubungan atau relasi di dalam database. DBMS memiliki fitur Data Definition Language (DDL) dan Data Manipulation Language (DML). DDL memberikan kemungkinan bagi pengguna untuk mendefiniskan database, sementara DML memberikan kemungkinan bagi pengguna untuk melakukan operasi insert, update, delete, dan retrieve data dari database. DBMS menyediakan akses terkontrol kepada database, dengan keamanan, integritas, concurrency dan recovery control. DBMS juga
27 menyediakan suatu mekanisme tampilan untuk memudahkan data yang akan digunakan oleh pengguna. Beberapa keuntungan dalam menggunakan pendekatan database antara lain pengendalian terhadap redundansi data (duplikasi data), konsistensi data, pembagian data, dan keamanan dan integritas yang lebih baik. Tetapi beberapa kerugian dari pendekatan ini antara lain adanya kompleksitas, biaya yang mahal, dan performansi yang berkurang.
1.12 Rekayasa Piranti Lunak
Rekayasa Piranti Lunak menurut Fritz Bauer (Pressman, 2001) adalah penetapn dan pemakaian prinsip-prinsip rekayasa dalam rangka mendapatkan piranti lunak yang ekonomis yaitu terpecaya dan bekerja efisien pada mesin (komputer). Menurut Pressman (2001), rekayasa piranti lunak mencakup 3 elemen yang mampu mengontrol proses pengembangan piranti lunak,yaitu: 1. Metode-metode (methods) menyediakan cara-cara teknis untuk membangun piranti lunak 2. Alat-alat bantu (tools) mengadakan dukungan otomatis atau semi otomatis untuk metodemetode seperti CASE (Computer Aided Software Engineering) yang mengkombinasikan software, hardware, dan software engineering database. 3. Prosedur-prosedur (procedurs) merupakan pengembangan metode dan alat bantu.
28 Dalam perancangan software dikenal istilah software life cycle yaitu serangkaian kegiatan yang dilakukan selama masa perancangan software. Berikut adalah visualisasi dari kegiatan pada software life cycle model waterfall (Dix, 1997, p180): 1. Spesifikasi kebutuhan (Requirement specification) Pada tahap ini, pihak pengembang dan konsumen mengidentifikasi apa saja fungsi-fungsi yang diharapkan dari sistem dan bagaimana sistem memberikan layanan yang diminta. Pengembang berusaha mengumpulkan berbagai informasi dari konsumen. 2. Perancangan arsitektur (Architectural design) Pada tahap ini, terjadi pemisahan komponen-komponen sistem sesuai dengan fungsinya masing-masing. 3. Detailed design Setelah memasuki tahap ini, pengembang memperbaiki deskripsi dari komponen-komponen dari sistem yang telah dipisah-pisah pada tahap sebelumnya. 4. Coding and unit testing Pada tahap ini, disain diterjemahkan ke dalam bahasa pemrograman untuk dieksekusi. Setelah itu komponen-komponen dites apakah sesuai dengan fungsinya masing-masing. 5. Integration and testing Setelah tiap-tiap komponen dites dan telah sesuai dengan fungsinya, komponen-komponen tersebut disatukan lagi. Lalu sistem dites untuk
29 memastikan sistem telah sesuai dengan kriteria yang diminta konsumen. 6. Pemeliharaan (maintenance) Setelah
sistem
diimplementasikan,
maka
perlu
dilakukannya
perawatan terhadap sistem itu sendiri. Perawatan yang dimaksud adalah
perbaikan
error
yang
ditemkan
setelah
sistem
diimplementasikan.
Gambar 0.2 Software Life Cycle Model Waterfall
Penjelasan yang telah dijabarkan di atas adalah teori-teori dasar yang akan digunakan dalam penyusunan skripsi ini, sekaligus menjadi acuan dalam menganalisis, membahas, mengevaluasi, serta mengambil simpulan pada babbab berikutnya.
30 1.13 Pengertian Teknologi Informasi
Menurut Ward dan Peppard (2002, p3), teknologi informasi secara khusus ditujukan untuk teknologi, khususnya hardware, software dan jaringan telekomunikasi. Teknologi informasi memfasilitasi perolehan, pemrosesan, penyimpanan, pengiriman dan pembagian informasi dan isi digital lainnya.
1.14 Interaksi Manusia Komputer
Menurut Shneiderman (1998, p4), Interaksi manusia dan komputer merupakan disiplin ilmu yang berhubungan dengan, perancangan, evaluasi, dan implementasi sistem komputer interaktif untuk digunakan oleh manusia, serta studi fenomena-fenomena besar yang berhubungan dengannya. Pada interaksi manusia dan komputer ditekankan pada pembuatan antarmuka pemakai (user interface), dimana user interface yang dibuat diusahakan sedemikian rupa sehingga seorang user dapat dengan baik dan nyaman menggunakan aplikasi perangkat lunak dibuat. Antar muka pemakai (user interface) adalah bagian sistem komputer yang memungkinkan manusia berinteraksi dengan komputer. Tujuan antar muka pemakai adalah agar sistem komputer dapat digunakan oleh pemakai (user interface), istilah tersebut digunakan untuk menunjuk kepada kemampuan yang dimiliki oleh piranti lunak atau program aplikasi yang mudah dioperasikan dan dapat membantu menyelesaikan suatu persoalan dengan hasil yang sesuai dengan keinginan pengguna, sehingga pengguna merasa betah untuk mengoperasikan program tersebut.
31 1.14.1 Program Interaktif
Suatu program yang interaktif dan baik harus bersifat user friendly. Scheiderman (1998,p15) menjelaskan lima kriteria yang harus dipenuhi oleh suatu program yang user friendly, yaitu: 1. Waktu belajar yang tidak lama; 2. Kecepatan penyajian informasi yang tepat; 3. Tingkat kesalahan pemakaian rendah; 4. Penghafalan sesudah melampaui jangka waktu; 5. Kepuasan pribadi.
1.14.2 Pedoman Merancang User Interface
Beberapa pedoman yang dianjurkan dalam merancang suatu program, guna mendapatkan suatu program yang user friendly yaitu: 1. Delapan aturan emas ( Eight Golden Rules ) Untuk merancang sistem interaksi manusia dan komputer yang baik, harus memperhatikan delapan aturan emas dalam perancangan antarmukan, seperti: strive for consistency (konsisten dalam merancang tampilan), enable frequent user to use shorcuts ( memungkinkan pengguna menggunakan shortcuts secara berkala), offer informative feed back (memberikan umpan balik yang informatif), design dialogs to yield closure (merancang dialog untuk menghasilkan
keadaan
akhir),
offer
simple
error
handling
(memberikan penanganan kesalahan), permit easy reversal of actions (mengijinkan pembalikan aksi dengan mudah), support internal locus
32 of control (mendukung pengguna menguasai sistem), dan reduce short-term memory load (mengurangi beban jangka pendek pada pengguna). 2. Teori waktu respon Waktu respon dalam sistem komputer menurut Scheiderman (1998,p352) adalah jumlah detik dari saat pengguna program memulai aktifitas sampai menampilkan hasilnya di layar atau printer. Beberapa pedoman yang disarankan: pemakai lebih menyukai waktu respon yang pendek, waktu respon yang panjang mengganggu, waktu respon yang pendek menyebabkan waktu pengguna berpikir lebih pendek, waktu respon harus sesuai denga tugasnya, dan pemakai harus diberi tahu mengenai penundaan yang panjang.
1.15 Unified Model Langguage (UML)
Unified Model Language (UML) merupakan suatu alat bantu dari pembuat sistem yang memudahkan untuk menciptakan gambaran dari suatu sistem yang dibuat berdasarkan visi dari pembuat sistem dengan sistematika standar, sehingga mudah dimengerti dan mudah dikomunikasikan (Schmuller, 1999, p6).
1.15.1 Diagram Use Case
Use Case menunjukkan hubungan interaksi antara aktor dengan use case di dalam suatu sistem (Mathiassen, 2000, p343) yang bertujuan untuk
33 menentukan bagaimana aktor berinteraksi dengan sebuah sistem. Aktor adalah orang atau sistem lain yang berhubungan dengan sistem. Ada tiga simbol yang mewakili komponen sistem seperti terlihat pada gambar dibawah ini.
Gambar 0.3 Notasi Use Case Diagram
Menurut Schneider dan Winters, ada lima hal yang harus diperhatikan dalam pembuatan diagram use case (Schneider dan Winters, 2001): 1. Aktor: segala sesuatu yang berhubungan dengan sistem dan melaksanakan use case yang terkait. 2. Precondition: kondisi awal yang harus dimiliki aktor untuk masuk ke dalam sistem untuk terlibat dalam suatu use case. 3. Postcondition: kondisi akhir atau hasil apa yang akan diterima oleh aktor setelah menjalankan suatu use case. 4. Flow of Events: kegiatan-kegiatan yang dilakukan pada sebuah proses use case. 5. Alternative Paths: kegiatan yang memberikan serangkaian kejadian berbeda yang digunakan dalam Flow of Events.
34 1.15.2 Diagram Statechart
Diagram Statechart menggambarkan state (keadaan) yang dialami semua objek dalam suatu class yang spesifik serta transisi (event) yang memicu terjadinya suatu state (Mathiassen et. al., 2000, p341). Seperti terlihat pada gambar dibawah ini.
Gambar 0.4 Notasi Statechart Diagram
1.15.3 Diagram Activity
Menurut Whitten et. al. (2004, p442) diagram activity digunakan untuk menggambarkan urutan aliran kegiatan-kegiatan dari sebuah proses bisnis atau sebuah use case. Diagram ini juga dapat digunakan untuk memodelkan aksi dan hasil ketika operasi berlangsung. Seperti terlihat pada gambar dibawah ini:
35
Gambar 0.5 Notasi Activity Diagram
1.15.4 Diagram Sequence
Menggambarkan bagaimana objek berinteraksi satu sama lain melalui pesan
pada
pelaksanaan
use
case
atau
operasi.
Diagram
sequence
mengilustrasikan bagaimana pesan dikirim dan diterima antar objek secara berurutan. (Whitten et. al., 2004, p441). Beberapa notasi diagram sequence terlihat pada gambar dibawah ini.
Gambar 0.6 Notasi Sequence Diagram
36 1.15.5 Diagram Class
Menggambarkan kumpulan dari class-class yang ada serta hubungan diantara class tersebut. Class mempunyai attributes dan operations yang berbeda-beda (Mathiassen, 2000, p336). Seperti terlihat pada gambar dibawah ini.
Gambar 0.7 Notasi Class Diagram
1.15.6 Diagram Collaboration
Menurut Whitten et. al. (2004, p441) diagram collaboration mirip dengan diagram sequence, namun diagram collaboration tidak fokus pada urutan datangnya pesan. Diagram collaboration menyediakan interaksi antar objek pada sebuah format jaringan. Seperti terlihat pada gambar dibawah ini.
Gambar 0.8 Notasi Collaboration Diagram
37
1.15.7 Diagram Component
Menurut Whitten et. al. (2004, p442) diagram component digunakan untuk menggambarkan perusahaan dan ketergantungan dari komponenkomponen perangkat lunak dari sistem. Diagram ini menunjukkan bagaimana kode program dibagi menjadi modul-modul (atau komponen-komponen). Seperti terlihat pada gambar dibawah ini.
Gambar 0.9 Notasi Component Diagram
1.15.8 Diagram Deployment
Menurut Whitten et. al. (2004, p442) diagram ini mendeskripsikan arsitektur secara fisik dalam bentuk node-node dari perangkat keras dan lunak dari sistem. Diagram deployment menggambarkan konfigurasi dari komponenkomponen, prosesor dan alat-alat perangkat lunak run-time yang membuat arsitektur sistem. Seperti terlihat pada gambar dibawah ini.
38
Gambar 0.10 Notasi Deployment Diagram
1.16 Keuntungan UML
Beberapa keuntungan dalam menggunakan UML antara lain: 1.
Sebagai bahasa permodelan yang general-purpose, difokuskan pada pokok himpunan konsep yang dapat dipakai bersama, dan menggunakan
pengetahuan
bersama
dengan
mekanisme
perluasan. 2.
Sebagai bahasa permodelan yang mudah diaplikasikan, dapat diaplikasikan untuk berbagai tipe sistem (software dan nonsoftware), domain (bisnis melawan software), dan metode atau proses.
3.
Sebagai bahasa permodelan standar industri, bukan merupakan bahasa yang tertutup atau satu-satunya, tapi bersifat terbuka dan sepenuhnya dapat diperluas.
1.17 Java
Java adalah sebuah bahasa pemrograman komputer berbasiskan kepada Object Oriented Programming. Java diciptakan setelah C++ dan didesain
39 sedemikian sehingga ukurannya kecil, sederhana, dan portable (dapat dipindahpindahkan di antara bermacam platform dan sistem operasi). Program yang dihasilkan dengan bahasa Java dapat berupa applet (aplikasi kecil yang jalan di atas web browser) maupun berupa aplikasi mandiri yang dijalankan dengan program Java Interpreter. Kelebihan Bahasa Pemogroman Java: 1. Multiplatform Kelebihan utama dari Java ialah dapat dijalankan di beberapa platform / sistem operasi komputer, sesuai dengan prinsip tulis sekali, jalankan di mana saja. Dengan kelebihan ini pemrogram cukup menulis sebuah program Java dan dikompilasi (diubah, dari bahasa yang dimengerti manusia menjadi bahasa mesin / bytecode) sekali lalu hasilnya dapat dijalankan di atas beberapa platform tanpa perubahan. Kelebihan ini memungkinkan sebuah program berbasis Java dikerjakan diatas sistem operasi Linux tetapi dijalankan dengan baik di atas Microsoft Windows. Platform yang didukung sampai saat ini adalah Microsoft Windows, Linux, Mac OS dan Sun Solaris. Penyebanya adalah setiap sistem operasi menggunakan programnya sendiri-sendiri (yang dapat diunduh dari situs Java) untuk menginterpretasikan bytecode tersebut. 2. OOP (Object Oriented Programming-Pemrogram Berorientasi Objek) yang artinya semua aspek yang terdapat di Java adalah Objek. Java merupakan salah satu bahasa pemrograman berbasis oebjek secara murni. Semua tipe data diturunkan dari kelas dasar yang disebut
40 Object. Hal ini sangat memudahkan pemrogram untuk mendesain, membuat, mengembangkan dan mengalokasi kesalahan sebuah program dengan basis Java secara cepat, tepat, mudah dan terorganisir. Kelebihan ini menjadikan Java sebagai salah satu bahasa pemograman termudah, bahkan untuk fungsi fungsi yang advance seperti komunikasi antara komputer sekalipun. 3. Perpustakaan
Kelas
Yang
Lengkap,
Java
terkenal
dengan
kelengkapan library/perpustakaan (kumpulan program program yang disertakan dalam pemrograman
Java) yang sangat memudahkan
dalam penggunaan oleh para pemrogram untuk membangun aplikasinya.
Kelengkapan
perpustakaan
ini
ditambah
dengan
keberadaan komunitas Java yang besar yang terus menerus membuat perpustakaan-perpustakaan baru untuk melingkupi seluruh kebutuhan pembangunan aplikasi. 4. Bergaya C++, memiliki sintaks seperti bahasa pemrograman C++ sehingga menarik banyak pemrogram C++ untuk pindah ke Java. Saat ini pengguna Java sangat banyak, sebagian besar adalah pemrogram C++ yang pindah ke Java. Universitas-universitas di Amerika juga mulai berpindah dengan mengajarkan Java kepada murid-murid yang baru karena lebih mudah dipahami oleh murid dan dapat berguna juga bagi mereka yang bukan mengambil jurusan komputer. 5. Pengumpulan sampah otomatis, memiliki fasilitas pengaturan penggunaan memori sehingga para pemrogram tidak perlu melakukan
41 pengaturan memori secara langsung (seperti halnya dalam bahasa C++ yang dipakai secara luas). Kekurangan Bahasa Pemrograman Java 1. Mudah didekompilasi. Dekompilasi adalah proses membalikkan dari kode jadi menjadi kode sumber. Ini dimungkinkan karena kode jadi Java merupakan bytecode yang menyimpan banyak atribut bahasa tingkat tinggi, seperti nama-nama kelas, metode, dan tipe data. Hal yang sama juga terjadi pada Microsoft .NET Platform. Dengan demikian, algoritma yang digunakan program akan lebih sulit disembunyikan dan mudah dibajak/direverse-engineer. 2. Penggunaan memori yang banyak. Penggunaan memori untuk program berbasis Java jauh lebih besar daripada bahasa tingkat tinggi generasi sebelumnya seperti C/C++ dan Pascal (lebih spesifik lagi, Delphi dan Object Pascal). Biasanya ini bukan merupakan masalah bagi pihak yang menggunakan teknologi terbaru (karena trend memori terpasang makin murah), tetapi menjadi masalah bagi mereka yang masih harus berkutat dengan mesin komputer berumur lebih dari 4 tahun.
1.18 MySQL
MySQL adalah salah satu perangkat lunak Sistem Manajemen Database atau Database Management System (DBMS) yang sangat terkenal dan Populer saat ini. MySQL memiliki banyak kemudahan untuk dipelajari dan digunakan.
42 Beberapa hal penting yang menyebabkan MySQL dikenal dan banyak digunakan orang adalah: •
MySQL mudah dipelajari, baik dalam hal struktur database maupun pengguna query.
•
MySQL dapat dijalankan dan menangani banyak user dalam waktu bersamaan.
•
Kelebihannya dapat menampung lebih dari lima puluh juta record membuat MySQL merupakan pilihan tepat untuk menampung record suatu instansi atau perusahaan skala kecil dan menengah.
•
MySQL mempunyai kecepatan cukup signifikan dalam hal eksekusi perintah dibandingkan dengan paket database lainnya.
•
MySQL menyediakan dokumen open source sehingga pengguna leluasa melakukan perubahan-perubahan source code untuk mengembangkan sistem sesuai dengan kebutuhan.
•
MySQL memiliki User Privilege System yang sangat mudah dan efisien.
•
Database MySQL dapat dipindahkan atau dimigraasikan ke paket database lainnya, misalnya Oracle yang sudah membuat modul khusus untuk memudahkan proses.
