METODE PENCARIAN LANGSUNG UNTUK MENYELESAIKAN PROBLEMA CAR SEQUENCING
TESIS
Oleh
NICE REJOICE REFISIS 077021007/MT
SEKOLAH PASCASARJANA UNIVERSITAS SUMATERA UTARA MEDAN 2009
Nice Rejoice Refisis : Metode Pencarian Langsung Untuk Menyelesaikan Problema Car Sequencing, 2009 USU Repository © 2008
METODE PENCARIAN LANGSUNG UNTUK MENYELESAIKAN PROBLEMA CAR SEQUENCING
TESIS
Diajukan Sebagai Salah Satu Syarat Untuk Memperoleh Gelar Magister Sains dalam Program Studi Magister Matematika pada Sekolah Pascasarjana Universitas Sumatera Utara
Oleh
NICE REJOICE REFISIS 077021007/MT
SEKOLAH PASCASARJANA UNIVERSITAS SUMATERA UTARA MEDAN 2009
Nice Rejoice Refisis : Metode Pencarian Langsung Untuk Menyelesaikan Problema Car Sequencing, 2009 USU Repository © 2008
Judul Tesis
Nama Mahasiswa Nomor Pokok Program Studi
: METODE PENCARIAN LANGSUNG UNTUK MENYELESAIKAN PROBLEMA CAR SEQUENCING : Nice Rejoice Refisis : 077021007 : Matematika
Menyetujui Komisi Pembimbing
(Dr. Saib Suwilo, M.Sc) Ketua
Ketua Program Studi
(Prof.Dr.Herman Mawengkang)
(Prof. Dr. Opim Salim S, M.Sc) Anggota
Direktur
(Prof.Dr.Ir.T.Chairun Nisa, B.,M.Sc)
Tanggal lulus : 2 Juni 2009
Nice Rejoice Refisis : Metode Pencarian Langsung Untuk Menyelesaikan Problema Car Sequencing, 2009 USU Repository © 2008
Telah diuji pada Tanggal : 2 Juni 2009
PANITIA PENGUJI TESIS Ketua Anggota
: :
Dr. Saib Suwilo, M.Sc 1. Prof. Dr. Opim Salim S, M.Sc 2. Dr. Tulus, M.Si 3. Drs. Marwan Harahap, M.Eng
Nice Rejoice Refisis : Metode Pencarian Langsung Untuk Menyelesaikan Problema Car Sequencing, 2009 USU Repository © 2008
ABSTRAK Program Integer Linier (ILP) menghadirkan suatu formula matematika pada sebuah problema optimisasi. Maksudnya bahwa fungsi objektif linier harus meminimumkan atau memaksimumkan subjek pada kendala linier. Variabel keputusan harus integer dan penyelesaiannya harus memenuhi semua kendala. Metode Pencarian Langsung untuk menyelesaikan Problema Car Sequencing diselesaikan menggunakan Program Integer Linier (ILP). Proses penjadwalan kendaraan sepanjang jalur produksi harus mengikutkan dalam perhitungan, beberapa kendala yakni pada proses pembuatan bodi, proses pengecatan dan proses perakitan. Pencarian langsung membantu pengerjaan praktis untuk problema car sequencing. Metode Pencarian Langsung adalah efektif untuk variasi permasalahan optimisasi. Kata kunci : Program Integer Linier, Problema Car Sequencing, Metode Pencarian Langsung
i
Nice Rejoice Refisis : Metode Pencarian Langsung Untuk Menyelesaikan Problema Car Sequencing, 2009 USU Repository © 2008
ABSTRACT An Integer Linear Programming (ILP) represents a mathematical formulation of an optimization problem. It means that a linear objective function which has to be minimized or maximized subject to linear constraint. The dicision variables have to be integer and the solution has to fulfill all constraint. Methods of Direct Search for solving the Car Sequencing Problem (CarSP) are solved using an Integer Linear Program (ILP). The process of scheduling vehicles along a production line has to take several constraints into account which are defined by the body shop, the paint shop and the assembly shop. A Direct Search is helping practice job in car sequencing problem. Direct search methods are affective option for variaties of difficult optimization problems. Keywords : Integer Linear Programming, Car Sequencing Problem, Direct Search . Method
ii
Nice Rejoice Refisis : Metode Pencarian Langsung Untuk Menyelesaikan Problema Car Sequencing, 2009 USU Repository © 2008
KATA PENGANTAR
Penulis mengucapkan puji syukur kepada Tuhan Yang Maha Esa atas berkat dan karuniaNya sehingga penulisan tesis yang berjudul Metode Pencarian Langsung untuk Menyelesaikan Problema Car Sequencing dapat dirampungkan. Tesis ini merupakan tugas akhir pada Sekolah Pascasarjana Program Studi Magister Matematika, Universitas Sumatera Utara. Pada kesempatan ini, penulis menyampaikan ucapan terima kasih dan penghargaan yang sebesar-besarnya kepada : Prof. Chairuddin P. Lubis, DTM&H, Sp.A(K) selaku Rektor Universitas Sumatera Utara dan Prof. Dr. Ir. T. Chairun Nisa B, M.Sc selaku direktur Sekolah Pascasarjana Universitas Sumatera Utara yang telah memberikan kesempatan kepada penulis untuk mengikuti perkuliahan pada Sekolah Pascasarjana pada Program Magister Matematika Universitas Sumatera Utara, Medan. Prof. Dr. Herman Mawengkang, selaku Ketua Program Studi Matematika Sekolah Pascasarjana USU dan juga sebagai pembanding pada penulisan tesis ini dengan penuh kesabaran memotivasi dan membimbing penulis serta memberikan buku dan jurnal-jurnal yang berkaitan dengan penelilitian yang penulis lakukan sehingga tesis ini dapat selesai. Dr. Saib Suwilo, M.Sc, selaku Sekretaris Program Studi Matematik Sekolah Pascasarjana USU dan juga sebagai pembimbing-I yang dengan penuh kesabaran memotivasi dan membimbing penulis sehingga penulis dapat menyelesaikan tesis ini
iii
Nice Rejoice Refisis : Metode Pencarian Langsung Untuk Menyelesaikan Problema Car Sequencing, 2009 USU Repository © 2008
Prof.
Dr.
Opim Salim S, MSc, selaku pembimbing-II yang telah
banyak memberikan saran , masukan dan arahan yang membangun terhadap kesempurnaan penulisan tesis ini. Dr. Tulus, M.Si dan Drs. Marwan Harahap, MEng selaku pembanding berkat saran dan bantuannya kepada penulis sehingga penulisan tesis ini dapat diselesaikan. Dr.
Sutarman, MSc, Dr.
Marwan Ramli, MSi, Drs.
Open
Darnius, MSc, Dra. Mardiningsih, MSi, Dra. Esther Nababan, MSc, Drs. Sawaluddin, MIT sebagai staf pengajar pada Sekolah Pascasarjana Program Studi Matematika atas bimbingan dan bantuannnya selama perkuliahan. Kepada orang tua tercinta Drs. Ridolf Sianturi dan Arlene Manurung, SPd yang selalu mendukung dalam doa dan dana, serta penuh kesabaran memotivasi saya; adik-adik tersayang : Serenity Deliver Refisis S.H(Mahasiswi Sekolah Pascasarjana Program Studi Magister Hukum USU stambuk 2008), Eternal Dean Refisis (Mahasiswa Teknik Elektro USU semester 8), Ardent Perfervid Refisis (Mahasiswa Polmed D3 USU Teknik Mesin semester 4) Harinuan Pity Mentor Refisis (SDN kls 6), Fervent Worthy Refisis (SD kls 1);Ompungku yang baik Tialam Siahaan (Ompu boru Marhabin Chakerpeh Sianturi), seta adik sepupuku Julita Manurung(mahasiswi tata boga Unimed semester 6), Brigadir Pol. Daniel Jani Damanik yang senantiasa mendoakan dan memberikan dorongan dalam menyelesaikan studi . Seluruh Staf Administrasi Sekolah Pascasarjana USU yang telah memberikan bantuan dan pelayanan yang baik kepada penulis, serta rekanrekan seperjuangan (kelas Reguler stambuk 2007) atas kebersamaan sela-
iv
Nice Rejoice Refisis : Metode Pencarian Langsung Untuk Menyelesaikan Problema Car Sequencing, 2009 USU Repository © 2008
ma perkuliahan. Juga disampaikan terimakasih kepada teman - teman saya Mikha Sihombing, Brigadir Pol. Lorent Manurung, kakak Ervina Batubara dan abang, adek Lisna Damanik beserta keluarga serta pihak yang tidak dapat disebutkan satu persatu yang turut memberi semangat, bantuan, dan membawakan saya dalam doa untuk menyelesaikan studi dengan baik. Semoga tesis ini bermanfaat bagi pembaca dan pihak-pihak yang memerlukannya. Kiranya Tuhan Memberkati kita semua.
Medan, Juni 2009 Penulis,
Nice Rejoice Refisis
v
Nice Rejoice Refisis : Metode Pencarian Langsung Untuk Menyelesaikan Problema Car Sequencing, 2009 USU Repository © 2008
RIWAYAT HIDUP
Nice Rejoice Refisis dilahirkan di Medan, pada tanggal 3 Maret 1984. Ayah bernama St. Drs. Ridolf Sianturi dan Ibu bernama Arlene Manurung, S.Pd, dan merupakan anak pertama dari enam bersaudara. Pada tahun 1989 penulis masuk TK Nasrani Medan, dan lulus pada tahun 1990. Pada Tahun 1990, penulis masuk SD Negeri No. 106162 Medan Estate dan pindah Tahun 1995 ke SD Negeri No. 105332 Tanjung Morawa, lulus pada tahun 1996. Pada tahun 1996, penulis melanjutkan sekolah di SLTP Negeri I Tanjung Morawa, lulus pada tahun 1999. Pada tahun 1999, penulis melanjutkan sekolah di SMU Negeri I Tanjung Morawa dan lulus pada tahun 2002. Pada tahun 2002 penulis diterima di Program Studi Pendidikan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Negeri Medan, dan lulus pada tanggal 28 Pebruari 2007. Pada tahun 2007, penulis melanjutkan pendidikan Program Studi Magister Matematika Kosentrasi Optimisasi dan Riset Operasi di Sekolah Pascasarjana Universitas Sumatera Utara, dan lulus pada tanggal 1 Juni 2009.
vi
Nice Rejoice Refisis : Metode Pencarian Langsung Untuk Menyelesaikan Problema Car Sequencing, 2009 USU Repository © 2008
DAFTAR ISI Halaman ABSTRAK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
i
ABSTRACT
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
ii
KATA PENGANTAR . . . . . . . . . . . . . . . . . . . . . . . . .
iii
RIWAYAT HIDUP . . . . . . . . . . . . . . . . . . . . . . . . . .
vi
DAFTAR ISI . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
vii
DAFTAR TABEL . . . . . . . . . . . . . . . . . . . . . . . . . . .
ix
BAB 1 PENDAHULUAN . . . . . . . . . . . . . . . . . . . . . . .
1
1.1 Latar Belakang . . . . . . . . . . . . . . . . . . . . . .
1
1.2 Perumusan Masalah . . . . . . . . . . . . . . . . . . . .
3
1.3 Tujuan Penelitian . . . . . . . . . . . . . . . . . . . . .
3
1.4 Manfaat Penelitian . . . . . . . . . . . . . . . . . . . .
4
1.5 Metode Penelitian . . . . . . . . . . . . . . . . . . . . .
4
BAB 2 TINJAUAN PUSTAKA . . . . . . . . . . . . . . . . . . . .
6
2.1 Problema Car Sequencing . . . . . . . . . . . . . . . . .
6
2.2 Beberapa Bentuk Untuk CarSP . . . . . . . . . . . . . .
7
2.2.1 Metode Eksak . . . . . . . . . . . . . . . . . . . .
7
2.2.2 Heuristik Greedy . . . . . . . . . . . . . . . . . .
7
2.2.3 Metode Local Search
. . . . . . . . . . . . . . . .
8
2.2.4 Ant Colony Optimization . . . . . . . . . . . . . .
8
BAB 3 PROGRAM INTEGER . . . . . . . . . . . . . . . . . . . .
9
3.1 Program Linier . . . . . . . . . . . . . . . . . . . . . .
9
vii
Nice Rejoice Refisis : Metode Pencarian Langsung Untuk Menyelesaikan Problema Car Sequencing, 2009 USU Repository © 2008
3.1.1 Dualitas
. . . . . . . . . . . . . . . . . . . . . .
11
3.1.2 Metode Simplex . . . . . . . . . . . . . . . . . . .
12
3.2 Program Integer Linier . . . . . . . . . . . . . . . . . .
14
3.3 Program Tak Linier . . . . . . . . . . . . . . . . . . . .
17
3.4 Program Taklinier Integer . . . . . . . . . . . . . . . . .
18
BAB 4 PEMBAHASAN
. . . . . . . . . . . . . . . . . . . . . . .
21
4.1 Pencarian Langsung . . . . . . . . . . . . . . . . . . . .
21
4.2 Ide Dasar Integer Linier . . . . . . . . . . . . . . . . . .
22
4.3 ILP pada CarS . . . . . . . . . . . . . . . . . . . . . .
23
4.3.1 Formula ILP
. . . . . . . . . . . . . . . . . . . .
4.4 Penggunaan Metode Pencarian Langsung
28
. . . . . . . . .
29
4.5 Contoh Untuk Formula . . . . . . . . . . . . . . . . . .
32
BAB 5 KESIMPULAN DAN SARAN . . . . . . . . . . . . . . . . .
34
5.1 Kesimpulan . . . . . . . . . . . . . . . . . . . . . . . .
34
5.2 Saran . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
DAFTAR PUSTAKA . . . . . . . . . . . . . . . . . . . . . . . . .
36
viii
Nice Rejoice Refisis : Metode Pencarian Langsung Untuk Menyelesaikan Problema Car Sequencing, 2009 USU Repository © 2008
DAFTAR TABEL
Nomor
Judul
Halaman
4.1
Penggunaan Simbol . . . . . . . . . . . . . . . . . . . . . .
23
4.2
Sebuah Uji Coba . . . . . . . . . . . . . . . . . . . . . . .
32
ix
Nice Rejoice Refisis : Metode Pencarian Langsung Untuk Menyelesaikan Problema Car Sequencing, 2009 USU Repository © 2008
BAB 1 PENDAHULUAN
1.1 Latar Belakang Problema sequencing dan penjadwalan adalah problema optimisasi kombinatorial, yang boleh saja mempunyai lebih daripada satu fungsi objektif. Ruang hasil penyelesaian cakupannya sangat luas, menyebabkan bertambah sulitnya penyelesaian. Untuk problema car sequencing, Dincbas et al. (1988) mengemukakan bahwa kendala - kendala yang ada membuat permasalahan sulit, dan terkadang mustahil untuk menemukan suatu penyelesaian yang sesuai. Dalam kasus ini ada suatu penyelesaian terhadap pelanggaran dengan sedikitnya kendala yang mungkin. Problema car sequencing (CarSP) menentukan urutan memasangkan satu unit mobil pada suatu pabrik pembuatan mobil yang terdiri dari tiga urutan proses, yakni: proses fabrikasi bodi, proses pengecatan dan proses perakitan. Pada proses fabrikasi bodi, dilakukan pengepresan dan pembentukan logam yang digabungkan dengan las untuk membentuk bodi mobil. Waktu pengerjaan pada bagian pengepresan cenderung lebih lama dalam urutan pengerjaan mobil sejenis ini. Pada proses pengecatan, bodi mobil akan diperiksa, kemudian disiapkan sedemikian rupa berikutnya dilakukan pengecatan. Pembersihan moncong alat cat dilakukan apabila terjadi pergantian warna sehingga mengakibatkan adanya penundaan waktu serta terbuangnya sebahagian bahan cat yang mempengaruhi penambahan biaya. Meminimumkan biaya ini, perlu ditentukan suatu urutan yang panjang dari mobil yang identik warna catnya. Pada proses perakitan,
1
Nice Rejoice Refisis : Metode Pencarian Langsung Untuk Menyelesaikan Problema Car Sequencing, 2009 USU Repository © 2008
2
ribuan perlengkapan mekanik dan kelistrikan serta berbagai komponen lainnya dipasangkan pada bodi mobil untuk penyelesaian pembuatan satu unit kendaraan. Setiap mobil dapat diperlengkapi dengan berbagai pilihan, seperti ’pelindung (sun-roof)’ atau ’AC (air-conditioning)’, yang juga memerlukan banyak operasi kerja. Mobil dapat dikelompokkan menjadi kelas-kelas kendaraan yang identik. Kendaraan yang memerlukan proses kerja tinggi harus dipecah dalam deret untuk melancarkan beban kerja dalam stasiun kerja tertentu. Karena komponen yang ditambahkan dalam bagian perakitan menyajikan 70% dari harga kendaraan, deretan perakitan membutuhkan perencanaan yang lebih tinggi untuk memastikan keseimbangan beban dan suplai komponen. Ketiga proses di atas masing-masing mengandung kendala yang cenderung terjadinya konflik. Misalnya, deretan yang baik dalam proses perakitan membutuhkan deretan warna dalam proses pengecatan yang singkat. Namun, akibat dari keruwetan problema, CarSP adakalanya diformulasikan dalam literatur dengan hanya memperhitungkan kendala dari proses perakitan. Kemudian deretan diaplikasikan terhadap seluruh proses produksi. Dengan menerima pandangan ini yang memakai sequence proses perakitan sebagai penyelesaian, CarSP telah dinyatakan sebagai persoalan NP-hard (Kis, 2004). Lopez dan Roubellat (2001) mempublikasikan review dari literatur terkait dan melaporkan metode analitik dan heuristik. Namun dalam review ini skala persoalan yang diangkat relatif kecil. Beberapa peneliti telah mengajukan metode heuristik untuk penyelesaian persoalan ini. Misalnya, optimisasi koloni semut dipakai oleh Solnon (2000) dan Gottlieb et al. (2003), dan metode pencarian sekitar (neighbourhood search methods) diajukan oleh Davenport et al. (1994), Davenport dan Tsang (1999), Puchata
Nice Rejoice Refisis : Metode Pencarian Langsung Untuk Menyelesaikan Problema Car Sequencing, 2009 USU Repository © 2008
3
dan Gottlieb (2002) serta Gottlieb et al. (2003). Metode pencarian langsung yang dikembangkan oleh Mawengkang (1997), pada dasarnya dipergunakan untuk menyelesaikan persoalan program integer tak linier berskala besar. Namun metode ini dapat diadopsi untuk menyelesaikan persoalan CarSP yang dapat dimodelkan sebagai program integer linier berskala besar. Ide dasarnya adalah melepaskan peubah tak basis yang dijumpai dalam penyelesaian optimal kontinu, dari batasannya sehingga akan mengubah basis non-integer yang terkait mengambil nilai integer disekitarnya. 1.2 Perumusan Masalah Persoalan CarSP merupakan persoalan optimisasi kombinatorial berskala besar. Kelemahan utama dalam memakai metode heuristik untuk menentukan penyelesaian optimal persoalan berikut ialah bahwa penyelesaian yang diperoleh adalah sub optimal dan tidak ada suatu cara untuk mengukur seberapa jauh sub optimal penyelesaian tersebut. Metode Branch and Bound yang biasa dipakai dalam integer linier programming, secara praktis untuk persoalan berskala besar proses percabangannya berhenti sebelum penyelesaian optimum dicapai (Murtagh, 1981). Oleh karena itu perlu diajukan suatu metode langsung yang harus dipakai untuk menyelesaikan persoalan program integer berskala besar. 1.3 Tujuan Penelitian Tujuan dari penelitian ini adalah menerapkan metode pencarian langsung untuk menyelesaikan problema car sequencing (CarSP) yang dimodelkan sebagai program integer linier berskala besar. Dengan adanya metode pencarian langsung dapat membantu pengerjaan yang praktis dalam problema car sequencing untuk menemukan pengaturan yang optimal dari kendaraan yang beroperasi disepanjang
Nice Rejoice Refisis : Metode Pencarian Langsung Untuk Menyelesaikan Problema Car Sequencing, 2009 USU Repository © 2008
4
jalur produksi. Pengembangan metode pencarian langsung yang akan dihasilkan dari penelitian ini juga memberikan kontribusi penting dalam bidang program integer linier. 1.4 Manfaat Penelitian Manfaat dari penelitian ini adalah memberikan pengaturan optimal sepanjang jalur fabrikasi (produksi) mobil dengan meminimalkan kesalahan proses pengerjaan dan pergantian warna. Melalui metode pencarian langsung ini dengan pemodelan program linier integer, variabel keputusan haruslah integer dan penyelesaian memenuhi semua kendala. 1.5 Metode Penelitian Persoalan CarSP ini dikerjakan dengan metode pencarian langsung untuk program integer linier. Persolan CarSP merupakan persoalan NP-hard, sehingga sulit untuk memakai teknik optimisasi dan eksak dalam menyelesaikannya. Bagaimanapun, dalam penyelesaiannya tetap diperoleh hasil perhitungan. Program Integer Linier menghadirkan formula matematika untuk permasalahan optimisasi. Fungsi objektif linier ini meminimumkan atau memaksimumkan subjek pada kendala linier. Veriabel keputusan harus integer dan penyelesaian harus memenuhi setiap kendala.
Nice Rejoice Refisis : Metode Pencarian Langsung Untuk Menyelesaikan Problema Car Sequencing, 2009 USU Repository © 2008
5
Prosedur yang dilakukan pada penelitian ini sebagai berikut :
I. Menjelaskan permasalahan car sequencing (CarSP). II. Pembahasan dan pemahaman tentang metode pencarian langsung untuk digunakan pada program integer linier. III. Merancang model CarSP : a. Adanya kendala pada CarSP harus dipetakan ke model ILP. b. Kendala tersebut dipastikan pada setiap mobil menandai tiap-tiap posisi, dan keseluruhan mobil memiliki penyelesaian. c. Penyelesaian car sequence dilakukan pada keseluruhan kendala berat adalah baik dan fungsi optimisasinya yakni minimum.
Nice Rejoice Refisis : Metode Pencarian Langsung Untuk Menyelesaikan Problema Car Sequencing, 2009 USU Repository © 2008
BAB 2 TINJAUAN PUSTAKA
2.1 Problema Car Sequencing Tujuan car sequence adalah untuk menemukan pengaturan yang optimal dari kendaraan yang beroperasi disepanjang jalur produksi. Pertama, disajikan semua langkah yang diperlukan, yakni keseluruhan perencanaan dari berbagai mobil yang berbeda pada suatu baris yang sama, kemudian memberikan penjelasan urutan perencanaan kendala yang diberikan. Renker Gerrit (2005) mengemukakan, meskipun setiap mobil yang mirip dengan satu sama lain, setiap mobil membutuhkan komponen yang digabungkan, dengan bekerja di sepanjang jalur baris produksi. Setiap mobil dicat dengan pilihan warna yang tepat. Proses pengerjaan untuk setiap tahap yakni proses pembentukan bodi, proses pengecatan dan proses perakitan, ketiga ini harus terlaksana mulus (smoothed) untuk memastikan output yang baik. CarSP telah dinyatakan sebagai persoalan NP-hard (Kis, 2004). Lopez dan Roubellat (2001) mempublikasikan review dari literatur terkait dan melaporkan metode analitik dan heuristik. Namun dalam review ini skala persoalan yang diangkat relatif kecil. Dimana persoalan CarSP merupakan persoalan NP-hard, sehingga sulit untuk dapat memakai teknik optimisasi dan eksak untuk menyelesaikannya, apalagi persoalan demikian ini biasanya berskala besar. Oleh karena itu dalam penelitian ini akan dikaji sesuatu sehingga heuristik dan teknik analitik untuk menyelesaikan persoalan yang merupakan suatu metode pencarian langsung.
6
Nice Rejoice Refisis : Metode Pencarian Langsung Untuk Menyelesaikan Problema Car Sequencing, 2009 USU Repository © 2008
7
2.2 Beberapa Bentuk Untuk CarSP Problem car sequencing (CarSP) terdapat sebuah solusi optimal tanpa beberapa pelanggaran kendala pada proses perakitan sebagai NP-hard, (Gent, 1998). Beberapa perbedaan pendekatan yang ada untuk memecahkan CarSP atau varians-varians didalamnya, dapat diselesaikan dengan metode Greedy Heuristik untuk meta-heuristik yakni seperti Optimisasi Koloni Semut (Ant Colony Optimization), selain dari Metode Eksak yang saat ini dipakai. 2.2.1 Metode Eksak Gravel et al. (2005) mengusulkan pendekatan ILP untuk varians CarSP tanpa kendala khusus pada proses pengecatan. Hal ini dilakukan pada pemecahan benchmark yakni pada contoh berikut, kira - kira sekitar 200 mobil dan 5 komponen untuk membuktikan pengoptimalan kepraktisan waktu. Ide utama mengaplikasikan rumus ini pada grup mobil dengan persamaan bentuk pengkelasan untuk menghindari simetrik. Pengembangan pendekatan ILP mengambil kendala dengan batasan perhitungan pada proses pengecatan. Kelemahannya, ukuran terpenting pemecahan pada contoh dibatasi kira - kira 30 mobil dengan 80 komponen, (Hu, 2004). 2.2.2 Heuristik Greedy Gottlieb et al. (2003) mengusulkan heuristic greedy sebagai strategi. Sikuen mobil yang dibangun selalu ditambah sehingga berikutnya diperoleh mobil yang paling baik pada berbagai fungsi yang diperiksa pada setiap bagian penting guna peningkatan sikuennya.
Nice Rejoice Refisis : Metode Pencarian Langsung Untuk Menyelesaikan Problema Car Sequencing, 2009 USU Repository © 2008
8
Satu kali mobil ditempatkan pada posisinya, diusulkan fungsi evaluasi mendapatkan mobil yang bernilai baik dan siap sebagai bagian sikuen perhitungan, dimana perhitungan umumnya mempengaruhi nilai apakah mobil sukar disusun tanpa pelanggaran kendala atau tidak. 2.2.3 Metode Local Search Beberapa percobaan memecahkan CarSP berdasarkan konsep Local Search. Puchta et al. (2003) mengusulkan pendekatan pembuatan enam perbedaan tipe struktur persekitaran (neighborhood) yang mana dibatasi oleh perpindahan berikut : pertukaran dua mobil (swap moves), perpindahan satu mobil dan menyisipkannya ke posisi yang lain (insert move), pergantian pada deretan mobil (transposition moves), pergantian dua mobil yang sama dalam bentuk tetap (similar swap moves), penyisipan dalam sikuen (urutan) mobil (Lin2Opt moves) dan pengaturan acak mobil dalam sikuen (random move). Dimana aplikasi jenis - jenis perpindahan (move) tersebut dimaksudkan untuk mencari perpindahan (move) yang disesuaikan pada posisinya. 2.2.4 Ant Colony Optimization Gravel et al. (2005) menghadirkan varians berbeda yakni Ant Colony Optomization (ACO) sebagai pendekatan CarSP. Mengusulkan varians berbeda dalam heuristic local dalam aplikasi pemilihan mobil berikutnya dan dalam persekitaran (neighborhood) pada local search. Bentuk penyelesaian iterative dibentuk oleh heuristic local dan keputusan acak. Beberapa varians pendekatan ACO, setiap keterwakilan dapat menyelesaikan sebaik hasil akhir yakni dengan perbaikan oleh local search.
Nice Rejoice Refisis : Metode Pencarian Langsung Untuk Menyelesaikan Problema Car Sequencing, 2009 USU Repository © 2008
BAB 3 PROGRAM INTEGER
3.1 Program Linier Problema program linier melibatkan optimisasi dari fungsi objektif linier, dengan subjeknya adalah persamaan linier dan kendala merupakan pertidaksamaan. Program linier mencoba mendapatkan keluaran terbaik (contoh : memaksimumkan laba, mengurangi biaya, dan lain-lain) dengan memberikan beberapa daftar kendala (contoh : hanya bekerja 30 jam/ minggu, tidak melakukan hal yang ilegal, dan lain-lain), menggunakan model matematika linier. Contoh lainnya ada pada polytope (polygon dan polyhedral) dan nilai rill fungsi affine f(x1 , x2, ..., xn) = a1x1 + a2x2 + a3x3 + b didefenisikan pada polytope, tujuannya adalah menemukan titik pada polytope dimana fungsinya mempunyai nilai terkecil atau terbesar. Titik mungkin tidak ada, tapi jika dicari sepanjang vertex polytope maka digaransi menemukan paling sedikit satu darinya. Program linier adalah problema yang dapat diekspresikan dalam bentuk kanonik :
Maximize cT x kendala A≤ b;
dimana
x≥0
x direpresentasikan vector variabel, c dan b adalah koefisien vektor dan A adalah koefisien matriks. Ekspresi untuk memaksimumkan atau meminimumkan
9
Nice Rejoice Refisis : Metode Pencarian Langsung Untuk Menyelesaikan Problema Car Sequencing, 2009 USU Repository © 2008
10
disebut fungsi objektif (cT x). Persamaan Ax ≤ b adalah fungsi kendala yang khususnya polyhedral konvex yang fungsi objektifnya dioptimisasi. Program linier dapat diaplikasikan untuk bermacam-macam field. Lebih diperluas, program linier digunakan dalam situasi bisnis dan ekonomi, tetapi dapat juga dimanfaatkan untuk beberapa masalah teknik. Beberapa industri menggunakan model program linier dalam transportasi, energy, telekomunikasi dan manufaktur. Dan dibuktikan juga pada problema dalam perencanaan, rute, jadwal, tugas dan desain. Problema dari sistem penyelesaian persamaan linier muncul setelah eliminasi Fourier-Motzkin. Program linier muncul sebagai model matematika yang dibangun selama Perang dunia ke-II untuk merencanakan pengeluaran dan pendapatan dalam mengurangi biaya untuk tentara dan meningkatkan kerugian dari musuh. Ini tetap menjadi rahasia sampai tahun 1947. Setelah perang berakhir banyak industri menemukan dan menggunakannya dalam perencanaan mereka. Penemu dari program linier adalah George B. Dantzig yang memperkenalkan metode simplex tahun 1947, John Von Neumann yang membangun teori dualitas dan Leonid Kantorovich, matematika Rusia yang menggunakan teknik yang sama pada bidang ekonomi sebelum Dantzig dan memenangkan penghargaan Nobel tahun 1975 dalam bidang ekonomi. Problema program linier pertama kali dapat dipecahkan pada polynomial oleh Leonid Khachiyan (1979) tetapi teori dan praktis yang paling luas pada field muncul tahun 1984 ketika Narendra Karmarkar memperkenalkan metode titik interior yang baru untuk menyelesaiakan problema program linier.
Nice Rejoice Refisis : Metode Pencarian Langsung Untuk Menyelesaikan Problema Car Sequencing, 2009 USU Repository © 2008
11
Contoh Dantzig dalam menemukan tugas terbaik dari 70 orang pada 70 pekerjaan menunjukkan kegunaan dari program linier. Kekuatan perhitungan mengharuskan pengujian semua permutasi untuk memilih tugas yang terbaik; jumlah konfigurasi yang mungkin melebihi jumlah partikel diseluruh bidang; kemudian menemukan solusi optimum dengan mengajukan problem ini dan pengaplikasian algoritma simplex. Program linier merupakan salah satu teknik operasi riset yang digunakan paling luas dan diketahui dengan baik. Problema khusus dari program seperti aliran jaringan network flow) dan aliran multicomodity dianggap cukup penting untuk dibangun dan diteliti algoritma yang khusus untuk solusinya. Terdapat sejumlah algoritma untuk problema optimisasi dalam penyelesaian program linier diantaranya adalah dualitas, dekomposisi, convexcity dan generalisasinya. Demikian juga program linier ini juga sangat sering digunakan dalam microekonomi dan manajemen bisnis, yaitu memaksimumkan pendapatan atau meminimumkan biaya dari produksi. Contoh lainnya pada manajemen persediaan, portfolio, manajemen keuangan, sumberdaya manusia, dan merencanakan iklan perusahaan. 3.1.1 Dualitas Setiap program linier disukai sebagai problema primal, dapat dikonversi kedalam problema dual yang menyediakan batas atas nilai optimal dari problema primal. Dalam bentuk matriks dapat diekspresikan sebagai berikut :
maximize cT x kendala Ax ≤ b, x ≥ 0
Nice Rejoice Refisis : Metode Pencarian Langsung Untuk Menyelesaikan Problema Car Sequencing, 2009 USU Repository © 2008
12
problema dual yang tepat adalah :
maximize bT x kendala AT y ≥ c, y ≥ 0
dimana y digunakan sebagai pengganti variabel vektor. Terdapat dua ide mendasar untuk teori dualitas. Salah satunya adalah dual dari program linier semula adalah program linier primal. Penambahannya adalah setiap solusi yang layak untuk program linier memberikan batas pada nilai optimal dari fungsi objektif dualitas. Kelemahan teorema dualitas bahwa nilai fungsi objektif dari dual pada solusi yang layak lebih baik atau sama dengan nilai fungsi objektif dari primal untuk solusi yang layak. Teorema dualitas yang kuat pada saat primal mempunyai solusi optimal x* maka dual juga mempunyai solusi optimal y* sehingga cT x∗ = bT y ∗. Program linier dapat juga tidak tak terbatas dan tidak layak. Teori dualitas mengatakan bahwa jika primal tidak terbatas dan tidak layak. teori dualitas mengatakan bahwa jika primal tidak terbatas maka dual tidak layak. Demikian juga jika dual tidak terbatas maka primal harus tidak layak. Atau mungkin juga untuk keduanya dual dan primal tidak layak. 3.1.2 Metode Simplex Karena kesulitan menggambar grafik berdimensi banyak maka penyelesaian masalah program linier yang melibatkan lebih dari dua variabel menjadi tidak praktis atau tidak mungkin. Dalam keadaan ini kebutuhan metode solusi yang lebih umum menjadi nyata. Metode umum ini dikenal dengan nama Algoritma Simplex yang dirancang untuk menyelesaiakn seluruh masalah program linier,
Nice Rejoice Refisis : Metode Pencarian Langsung Untuk Menyelesaikan Problema Car Sequencing, 2009 USU Repository © 2008
13
baik yang melibatkan dua variabel maupun lebih dua variabel. Penyelesaian masalah program linier menggunakan metode simpleks ini melalui perhitungan ulang (iterasi) dimana langkah-langkah perhitungan yang sama diulang berkali-kali sebelum solusi optimum dicapai. Dalam penyelesaian masalah program linier dengan grafik, telah dinyatakan bahwa solusi optimum selalu terletak pada titik pojok ruang solusi. Metode simplex didasarkan pada gagasan ini, dengan langkah-langkah sebagai berikut :
1. Dimulai pada titik pojok yang layak, biasanya titik asal (yang disebut sebagai solusi awal). 2. Bergerak dari suatu titik pojok yang layak ke titik pojok yang lain yang berdekatan, pergerakan ini akan menghasilkan nilai fungsi tujuan yang lebih baik (meningkat untuk masalah maksimisasi dan menurun untuk masalah minimisasi). Jika solusi yang lebih baik telah diperoleh, prosedur simplex dengan sendirinya akan meghilangkan semua solusi-solusi lain yang kurang baik. 3. Proses ini dilakukan berulang-ulang sampai suatu solusi yang lebih baik tak dapat ditemukan. Proses simplex kemudian berhenti dan solusi optimum diperoleh.
Nice Rejoice Refisis : Metode Pencarian Langsung Untuk Menyelesaikan Problema Car Sequencing, 2009 USU Repository © 2008
14
Mengubah bentuk baku model program linier ke dalam bentuk tabel akan memudahkan proses perhitungan simplex. Langkah-langkah perhitungan dalam algoritma simplex adalah :
1. Berdasarkan pada bentuk baku, tentukan solusi awal, dengan menetapkan (n − m) variabel nonbasis sama dengan nol. Dimana n jumlah variabel dan m banyaknya kendala. 2. Pilih sebuah entering variabel diantara yang sedang menjadi variabel nonbasis, yang jika dinaikkan di atas nol dapat memperbaiki nilai funsi tujuan. Jika tak ada, berhenti berarti solusi sudah optimal. Jika tidak dilanjutkan ke langkah satu. 3. Pilih sebuah leaving variabel diantara yang sedang menjadi variabel basis yang harus menjadi nonbasis (nilainya menjadi nol) ketika entering variabel menjadi variabel basis. 4. Tentukan solusi yang baru dengan membuat entering variabel dan leaving variabel menjadi nonbasis. Kembali kelangkah dua.
3.2 Program Integer Linier Jika variabel tak diketahui diharuskan integer maka problema ini disebut program integer atau program linier integer. Perbedaan dengan program linier adalah dapat diselesaikan lebih efisien pada kasus yang buruk. Problema program integer banyak terjadi pada situasi praktis (dengan variabel terbatas) NP hard. Program integer 0-1 adalah kasus yang khusus dari program integer dimana variabel diharuskan 0 atau 1. Masalah ini juga diklasifikasikan sebagai masalah yang sulit non polynomial.
Nice Rejoice Refisis : Metode Pencarian Langsung Untuk Menyelesaikan Problema Car Sequencing, 2009 USU Repository © 2008
15
Jika hanya beberapa variabel tak diketahui diharuskan integer maka problema ini disebut program integer campuran. Hal ini juga merupakan masalah sulit non polynomial. Bagaimanapun terdapat beberapa subklas dari program integer dan program integer campuran bahwa dapat diselesaikan dengan efisien, khususnya masalah dimana matriks kendalanya unimodular dan sisi sebelah kanan dari integer adalah integer. Program integer adalah bentuk dari program linier dimana asumsi divisibilitasnya melemah atau hilang sama sekali. Bentuk ini muncul karena dalam kenyataannya tidak semua variabel keputusan dapat berubah berupa bilangan pecahan. Asumsi divisibilitas melemah artinya sebagian dari nilai variabel keputusan harus berupa bilangan bulat (integer) dan sebagian lainnya boleh berupa bilangan pecahan. Persoalan program integer dimana hanya sebagian dari variabel keputusan yang harus integer disebut sebagai persoalan Mixed Integer Programming. Tetapi jika seluruh variabel keputusan dari suatu persoalan program linier harus berharga integer, maka persoalan tersebut disebut sebagai persoalan Pure Integer Programming. Dalam hal ini asumsi divisibilitas dari program linier hilang sama sekali. Contoh Maksimumkan z = 8x1 + 5x2 Kendala x1 + x2 ≤ 6 9x1 + 5x2 ≤ 45 x1, x2 ≥ 0, x2integer Tampaknya cukup untuk mendapatkan solusi integer dari masalah program linier dengan menggunakan metode simpleks biasa dan kemudian membulatkan nilai-nilai pecahan solusi optimum. Hal ini bukan tugas yang mudah untuk membulatkan nilai-nilai pecahan variabel basis yang menjamin tetap memenuhi semua
Nice Rejoice Refisis : Metode Pencarian Langsung Untuk Menyelesaikan Problema Car Sequencing, 2009 USU Repository © 2008
16
kendala dan tidak menyimpang cukup jauh dari solusi bulat yang tepat. Karena itu perlu prosedur yang sistematis untuk mendapatkan solusi bulat optimum terhadap masalah itu. Ada beberapa pendekatan solusi terhadap masalah program integer yaitu salah satu diantaranya adalah pendekatan dengan cutting plane. Dalam program linier, metode simpleks didasari oleh pengenalan bahwa pemecahan optimum terjadi di titik ekstrim dari ruang solusi. Hasil yang penting ini pada intinya mengurangi usaha pencarian pemecahan optimum dari sejumlah pemecahan yang tidak terbatas menjadi sejumlah yang terbatas. Sebaliknya Program Linier Integer memulai dengan sejumlah titik pemecahan yang terbatas. Tetapi sifat variabel yang berbentuk bilangan bulat mempersulit perancangan sebuah algoritma yang efektif utnuk mencari secara langsung diantara titik integer yang layak dari ruang penyelesaian. Terdapat dua metode untuk menghasilkan batasan-batasan khusus yang akan memaksa pemecahan optimim dari masalah program linier yang dilonggarkan untuk bergerak kearah pemecahan integer yang diinginkan yaitu metode Bidang Pemotong (Gomory Cutting Plane) dan metode Branch and Bound. Algoritma lanjutan untuk menyelesaikan program linier integer adalah :
a. Metode Cutting Plane b. Metode Branch and Bound c. Metode Branch and Cut d. Metode Branch and Price e. Metode Pencarian Langsung
Nice Rejoice Refisis : Metode Pencarian Langsung Untuk Menyelesaikan Problema Car Sequencing, 2009 USU Repository © 2008
17
Dalam penelitian ini hanya dibahas tentang metode Pencarian Langsung. 3.3 Program Tak Linier Program Taklinier adalah proses dari penyelesaian sistem persamaan dan tidak persamaan yang memiliki kendala. Himpunan dari variabel real yang tidak diketahui sepanjang fungsi objektifnya memaksimumkan atau meminimumkan dengan beberapa kendala atau fungsi objektif disebut nonlinier. Problema ini dapat disederhanakan sabagai berikut : max/ min f(x) untuk memaksimumkan atau meminimumkan fungsi objektif dimana f : Rm → R danX ⊆ Rm Jika fungsi objektif f adalah linier dan ruang kendala adalah polytope, problema ini adalah problema program linier yang dapat diselesaikan dengan menggunakan solusi program linier. Jika fungsi objektif adalah konkaf/ konveks dan himpunan kendala adalah konveks maka metode yang umum dari optimisasi konveks dapat digunakan. Beberapa metode dalam penyelesaian problema non-konveks. Salah satu pendekatannya menggunakan formula yang khusus dari problema program linier. Metode lain meliputi penggunaan teknik Branch and Bound dimana program ini dibagi dalam subkelas untuk diselesaikan dengan aproksimasi linier dari batas bawah pada keseluruhan biaya sampai subdivisi. Dengan divisi berikut, beberapa titik solusi aktual akan diperoleh jika biaya sama atau lebih rendah dari batas bawah terbaik. Untuk solusi aproksimasi, solusi ini optimal meskipun tidak mungkin tunggal. Algoritma dapat berhenti cepat dengan jaminan bahwa solusi terbaik tidak lebih dari persentase tertentu yang lebih baik dari solusi yang ditemukan. Hal ini khususnya berguna bagi problema yang sulit dan luas. De-
Nice Rejoice Refisis : Metode Pencarian Langsung Untuk Menyelesaikan Problema Car Sequencing, 2009 USU Repository © 2008
18
ngan biaya atau nilai yang pasti dimana ketidakpastian tersebut dapat diestimasi dengan estimasi kelayakan yang tepat. 3.4 Program Taklinier Integer Program taklinier integer pada hakekatnya adalah masalah yang sulit. Metode yang biasa untuk menyelesaikan program taklinier integer berdasarkan bermacam rangkaian linierisasi dari problema dan beberapa variasi pada strategi Branch and Bound. Bagaimanapun dibeberapa kasus kegunaan khusus dapat diambil dari struktur pada problema. Problema umum dari program linier tak integer khususnya skala luas dikenal luas sebagai persoalan yang sangat sulit dan dapat diselesaikan dengan membangun rangkaian solusi untuk program linier yang beberapa pengertian aproksimasi pada program taklinier. Duran dan Grosmannn (1986) mengemukakan secara detail dari algoritma outer aproksimasi untuk menyelesaikan MINLP. Pendekatan meliputi konstruksi dan solusi dari rangkaian bolak balik pada master problem program linier dan sub problema pada program taklinier. Subproblema sekarang diselesaikan dengan variabel integer yang tetap dan master problema yang dibentuk dengan linierisasi fungsi pada solusi dari subproblema. Metode Duran Grossmann menggunakan prinsip dekomposisi untuk mengeksploitasi struktur problema yang diasumsikan pada bentuk berikut : linier pada variabel integer dan konveks pada porsi taklinier dari fungsi objektif dan kendala. Bentuk umum dari klas problema berikut ditulis : minimum cT y + f (x)
Nice Rejoice Refisis : Metode Pencarian Langsung Untuk Menyelesaikan Problema Car Sequencing, 2009 USU Repository © 2008
19
kendala g(x) = By ≤ 0 x ∈ X ⊆ Rn y ∈ U ⊆ Rm + fungsi tak linier f : Rn → R dan fungsi vektor g : Rn → Rp diharuskan differensial kontinu dan konveks pada domain yang kompak. Seperti biasanya, domain U dari variabel integer diasumsikan pada himpunan diskrit yang berhingga. Linieriti dari variabel diskrit membolehkan karakteristik bebas dari ruang pencarian yang layak diskrit dan kontinu dari problema. Ruang kontinu diekspresikan sebagai irisan daerah konvex kompak dan berhingga, tiap-tiapnya diparametrik dengan nilai dari variabel diskrit. Outer Aproksimasi dari himpunan konveks dengan irisan dari ruang bagian yang mendukung yang digunakan utnuk mendefenisikan master program linier integer-campuran. Beberapa hasil dari Mawengkang and Murtagh (1985/6) talah memberikan hasil membuat bentuk umum dan sering digunakan pada kelas program tak linier dimana proporsi dari variabel integer dan variabel taklinier keduanya kecil. Mawengkang and Murtagh (1985), mengajukan penyelesaian program taklinier integer dengan software optimisasi yang skala luas menggunakan MINOS. Teknik ini dipresentasikan untuk memperluas pencarian kendala untuk menyalidiki solusi Integer yang layak sehingga solusi optimal kontinu diperoleh. Perhitungan menggunakan pendekatan ini digambarkan untuk dua kelas problema yaitu problema kuadratik dan desain jaringan problema. Secara umum, kebanyakan tujuan dari penelitian pemograman matematika adalah untuk membentuk teori yang mengacu pembuatan algoritma untuk digunakan secara modern, komputasi digital kecepatan tinggi. Metode survey yang
Nice Rejoice Refisis : Metode Pencarian Langsung Untuk Menyelesaikan Problema Car Sequencing, 2009 USU Repository © 2008
20
baik digunakanuntuk menyelesaikan masalah Program taklinier dapat ditemukan dan digolongkan kedalam kategori-kategori berikut :
1. Teknik Linierisasi 2. Pendekatan Branch and Bound 3. Teknik Enumerasi Implisit 4. Pendekatan Program Dinamik 5. Metode-metode lain
Nice Rejoice Refisis : Metode Pencarian Langsung Untuk Menyelesaikan Problema Car Sequencing, 2009 USU Repository © 2008
BAB 4 PEMBAHASAN
4.1 Pencarian Langsung Salah satu metode numeris untuk mencari lokasi minimum dari fungsi real f (x), x ∈ Rn , adalah metode pencarian langsung direct search yang diajukan oleh Hooke dan Jeeves. Metode ini memanfaatkan dua langkah, yaitu langkah penjelajahan exploratory moves untuk menentukan arah pencarian yang tepat, dan langkah pola pattern moves untuk mempercepat pencarian. Parameter-parameter yang digunakan dalam metode ini adalah: maxm fpk wk
≡ jumlah maksimum langkah pola yang diijinkan, ≡ panjang langkah awal, dinyatakan sebagai fraksi dari jangkauan xk − xp,dimana xk ∈ Rn adalah perkiraan batas atas dan xp ∈ Rn adalah perkiraan batas bawah. ≡ fraksi dari panjang langkah awal sebagai kriteria konvergensi.
Keterangan lebih lanjut mengenai metode Hooke dan Jeeves diberikan antara lain oleh Avriel (1976) dan Bronson (1982). Pencarian langsung belum tentu menemukan minimum yang merupakan global minimum. Untuk memperbesar peluang itu, digunakan kombinasi berupa pencarian langsung dan acak (direct and random search), yang memanfaatkan parameter-parameter berikut: ntest nh ntmc nraz
≡ jumlah lokasi acak dalam pencarian shotgun. ≡ jumlah maksimum pencarian shotgun yang diijinkan. ≡ jumlah lokasi acak untuk memperoleh lokasi awal pencarian yang baru. ≡ jumlah pencarian yang dilakukan menggunakan lokasi awal pencarian yang baru.
21
Nice Rejoice Refisis : Metode Pencarian Langsung Untuk Menyelesaikan Problema Car Sequencing, 2009 USU Repository © 2008
22
4.2 Ide Dasar Integer Linier Program Integer Linier (ILP) menghadirkan sebuah formula matematika untuk permasalahan optimisasi. Fungsi objektif liniernya harus minimum atau maksimum untuk subjek pada kendala linier. Variabel keputusan harus integer dan penyelesaian harus memenuhi keseluruhan kendala. Dibawah ini disajikan bentuk standard sebuah ILP, dimana c adalah n-dimensi besaran vektor, x adalah n-dimensi vektor pada variabel keputusan, A adalah koefisien matrik dan b adalah besaran skalar. minimum cT x kendala Ax ≥ b x ∈ Zn
Bentuk standard ILP
Umumnya, ILP diselesaikan menggunakan algoritma eksak seperti pada ”Branch and Bound” atau ”Branch and Cut”. Hasil algoritma eksak ini adalah sebuah solusi optimal. Artinya, bahwa tidak terdapat penyelesaian lain dengan nilai objektifnya lebih baik. Pada problema sequence mobil, terdapat sebuah penyelesaian optimal untuk susunan sepanjang jalur produksi dengan meminimalkan kesalahan pada proses pengerjaan dan pergantian warna. Jika beragam solusi optimal, tapi tetap hanya satu solusi diperlukan. Walaupun secara umum, hal yang mungkin terjadi bahwa tidak diperoleh solusi, problema car sequencing pada contoh memiliki sedikitnya satu solusi integer yang diperoleh dari perhitun-
Nice Rejoice Refisis : Metode Pencarian Langsung Untuk Menyelesaikan Problema Car Sequencing, 2009 USU Repository © 2008
23
gan. Pada percobaan untuk memecahkan problema car sequencing dalam eksak menggunakan ILP. Hu (2004) mengusulkan pendekatan ILP. Diluar ILP, pengerjaannnya yakni dapat dengan menggunakan pendekatan heuristik. 4.3 ILP pada CarS Berikut disajikan Formula ILP pada problema car sequencing (CarSP), Prandtstetter (2005). Tabel 4.3 berikut menunjukkan simbol digunakan pada formula ILP yang disebut komponen ILP (C-ILP). Konfigurasi k ∈ K berbanding relevant pada komponen c ∈ C .
n k∈K δK c∈C f ∈F ⊆C s lc/mc s/(s + 1) costc costf
..... ..... ..... ..... ..... ..... ..... ..... ..... .....
Tabel 4.1 : Penggunaan Simbol banyaknya mobil bentuk k permintaan untuk konfigurasi k ∈ K komponen c warna f batas pengecatan kendala untuk komponen c ∈ C\F kendala untuk warna f ∈ F biaya kesalahan komponen c biaya untuk perubahan warna ke warna f ∈ F
Entri-entri matriks A menunjukkan hubungan berikut :
ack =
(
1”jika − konfigurasi − k − terdapat − kompenen − c” ∀c ∈ C, ∀k ∈ K 0”lainnya”
Dengan perhitungan kompleks, hal yang penting yakni ∃c : aci 6= acj ∀ (i, j) ”dengan”i 6= j Kendala ini menjamin, bahwa setiap konfigurasi terdapat pasangan berbeda. Dengan begitu terdapat reduksi jarak. Perhitungan berikut menunjukkan per-
Nice Rejoice Refisis : Metode Pencarian Langsung Untuk Menyelesaikan Problema Car Sequencing, 2009 USU Repository © 2008
24
mintaan untuk setiap komponen c ∈ C : dc =
X
(ack .δk )
∀c ∈ C
k∈K
Untuk perhitungan sejumlah pelanggaran, produksi pada N − 1 hari harus sesuai. Dimana matriks E = eci bernilai 1 jika mobil pada posisi n − i pada komponenc. Kolom matriks E yakni maxc∈C {mc } − 1, maksudnya bahwa maksimum banyaknya mobil yang mungkin memiliki pelanggaran beberapa kendala untuk N hari. eci =
∀c ∈ C,∀i ∈
1”jika − mobil − pada − posisi − (n − i) − untuk − c” 0”lainnya”
0, · · · , max {mc } − 1
c∈C
Semua matriks dan vektor didefenisikan lebih luas dengan adanya konstanta tiap-tiap contoh. Pemecahan masalah yakni dengan perpindahan tiap-tiap komponen sampai keseluruh lengkap. Matriks B memiliki n kolom dan |C| baris, untuk nilai bci adalah 0 dan 1. bci =
1”mobil − pada − posisi − i − untuk − komponen − c” 0”lainnya”
∀c ∈ C, ∀i ∈ {0, ..., n − 1} Tiap-tiap mobil harus dicat tepat satu warna. Olehkarena itu jumlah keseluruhan warna pada entri-entrinya harus samadengan 1 untuk setiap mobil. X
bf i = 1
∀i ∈ {0, ..., n − 1}
f ∈F
Sejumlah komponen harus sama banyaknya dengan komponen pemakaian.
Nice Rejoice Refisis : Metode Pencarian Langsung Untuk Menyelesaikan Problema Car Sequencing, 2009 USU Repository © 2008
25
n−1 X
bci = dc
∀c ∈ C
i=0
Saat ini tidak dijamin pemenuhan bentuk yang memuaskan. Untuk alasan inilah, beberapa perhitungan ekstra diperlukan dan matriks P dengan dimensi |K|xn . Jika konfigurasi kadalah produksi pada posisi i, koresponden entri untuk pki adalah 1 dan 0 untuk lainnya. Nilai pada pki hanya 1 jika semua entri untuk ack bernilai sama dengan bci (∀c ∈ C). Jika entri untuk ack dan bci adalah 1, maka ack bci hasilnya 1. Kasus lainnya, menunjukkan nilai sama dengan 0. Jika dua entri tersebut bernilai 0, yakni (1 − ack ). (1 − bci ) hasilnya 1. Kemudian untuk setiap kasus lainnya hasilnya 0. Penjumlahan pada ack .bci + (1 − ack ). (1 − bci ) adalah 1 jika kedua entri adalah sama. Berikut observasi pertidaksamaan : pki ≤ ack .bci + (1 − ack ). (1 − bci ) ∀k ∈ K, ∀c ∈ C, ∀i {0, ..., n − 1} pki ≥ n−1 P
0 ∀k ∈ K, ∀i {0, ..., n − 1}
pki = δk ∀k ∈ K
i=0
Karena hanya satu konfigurasi pada manufaktur mobil di tiap-tiap posisi sepanjang jalur produksi, jumlah tiap-tiap kolom pada matriks P harus 1. P
pki = 1 ∀i ∈ {0, ..., n − 1}
k∈K
Perincian analisis ini sesuai kendala yang terbengkalai, meninjau bentuk kendala diatas. Karena semua konfigurasi pada pasangan berbeda dimana paling banyak satu entri dalam matriks P berarti nilainya sama dengan 1. Dimana
Nice Rejoice Refisis : Metode Pencarian Langsung Untuk Menyelesaikan Problema Car Sequencing, 2009 USU Repository © 2008
26
jumlah berlebih setiap entri pada matriks P sama dengan n. Tiap kolom dalam entri P berjumlah diatas 1. Dengan keterangan sebagai berikut: bci =
P
ack .pki ∀i ∈ {0, ..., n − 1} , ∀c ∈ C
k∈K
Kenyataannya, tiap bentuk k ditandai untuk posisi i pada kompenen c ∈ C diperlukan oleh konfigurasi k ke posisi i juga. Pada saat tidak terlaksana perhitungan untuk menghitung pelanggaran pada kendala kerja atau perubahan warna. Dengan maksud matriks Q dihadirkan. Entri-entrinya mengindikasi kuantitas mobil pada permintaan komponen c dalam subsequence dengan panjang mc dikurang kuota lc untuk komponen ini. Olehkarena defenisi ini, hanya nilai integer masuk bagian walaupun entri-entri tidak perlu integer. qc0 = bc0 +
m c −2 X
(ecj − lc )∀c ∈ C
j=0
qci =
qc(i−1) + bci − ec(mc −i−1) ∀i ∈ {1, ..., mc − 1} ∀c ∈ C qc(i−1) + bci − bc(i−mc ) ∀i ∈ {mc , ..., n − 1}
Catatan bahwa kendala dibatasi oleh proses pengecatan yakni
s s+1
, yakni
banyak s mobil dapat dicat dengan warna yang sama. Jika banyaknya s mobil dicat dengan warna yang sama dalam subsequence pada s + 1 mobil, dimana harus sedikitnya satu mobil berganti warna. Dengan tidak ada pelanggaran terjadi pada kendala saat proses pengecatan. Kerena ekuivalensi ini dibatasi oleh proses pengerjaan dan proses pengecatan, hal ini sangat mudah untuk dimasukkan sebagai formula ILP. Kendala disini merupakan kendala yang sulit yang mana maksudnya tidak diperbolehkan pelanggaran ada, berikut pertidaksamaan dimu-
Nice Rejoice Refisis : Metode Pencarian Langsung Untuk Menyelesaikan Problema Car Sequencing, 2009 USU Repository © 2008
27
at. qf i ≤ 0
∀f ∈ F, ∀i ∈ {0, ..., n − 1}
Untuk perhitungan aktual banyaknya pelanggaran, hanya entri-entri matriks Q dengan nilai terbesar dari pada 0 adalah relevant. Hanya entri-entri untuk komponen harus dipertimbangkan, karena tidak ada pelanggaran diijinkan terjadi pada kendala proses pengecatan. Matriks G dengan dimensi |C\F |xn terdiri atas nilai non negative (integer). qci ≥ 0
∀i ∈ {0, ..., n − 1} , ∀c ∈ C\F
gci ≥ qci
∀i ∈ {0, ..., n − 1} , ∀c ∈ C\F
Dikarenakan formula ini untuk menghitung banyaknya pelanggaran yakni 2 · |C| · n variabel, matrikQ dan G direduksi untuk menjadi satu matrik saja. Lebih mudah diperoleh dengan penyelesaian recursion dalam matrik Q dan menunjukkan penjumlahan eksplisit. Matrik G didefenisikan berikut, yakni gci ≥ 0 gci ≥
i X
bcj +
mX c −i−2
j=0
ecj − lc
∀i ∈ {0, ..., n − 2} , ∀c ∈ C\F
j=0 i X
gci ≥
∀i ∈ {0, ..., n − 1} , ∀c ∈ C\F
bcj − lc
∀i ∈ {m, −1, ..., n − 1} , ∀c ∈ C\F
j=i−mc +1
Formula ini menggunakan banyak |C| · variabel, tetapi pengerjaannya kembali untuk kendala proses pengecatan. i X
bf j +
j=0
s−1−i X
ef j ≤ s
∀i ∈ {0, ..., s − 1} , ∀f ∈ F
j=0 i X
bf j ≤ s
∀i ∈ {s, ..., n − 1} , ∀f ∈ F
j=i−s
Nice Rejoice Refisis : Metode Pencarian Langsung Untuk Menyelesaikan Problema Car Sequencing, 2009 USU Repository © 2008
28
Hanya berganti warna, dapat dihitung. Maksudnya adalah matrik W dengan |F | × n entri. Wf i bernilai 1 jika pergantian warna f terjadi pada posisi idan 0 untuk lainnya.
wf 0 ≥ 0
∀f ∈ F
wf 0 ≥ bf 0 − ef 0 wf i ≥ 0
∀f ∈ F
∀i ∈ {1, ..., n − 1} , ∀f ∈ F
wf i ≥ bf i − bf (i−1)∀i ∈ {1, ..., n − 1} , ∀f ∈ F Berikut pendefenisian fungsi objektif yang mana harus minimum. ! ! n−1 n−1 X X X X cos tf . cos tc . wf i + gci i=0
f ∈F
i=0
c∈C\F
4.3.1 Formula ILP Kesimpulan atas sejumlah formula diatas, dihadirkan sebagai berikut :
fungsi objektif min
X
cos tf .
n−1 X
wf i
i=0
f ∈F
!
+
X
cos tc .
c∈C\F
n−1 X
gci
! (4.1)
i=0
kendala 0 ≤ bci ≤ 1
∀c ∈ C, ∀i ∈ {0, ..., n − 1}
X
∀i ∈ {0, ..., n − 1}
bf i = 1
(4.2) (4.3)
f ∈F n−1 X
bci = dc
∀c ∈ C
(4.4)
∀k ∈ K, ∀i ∈ {0, ..., n − 1}
(4.5)
i=0
0 ≤ pki ≤ 1
Nice Rejoice Refisis : Metode Pencarian Langsung Untuk Menyelesaikan Problema Car Sequencing, 2009 USU Repository © 2008
29
pki ≤ ack .bci + (1 − ack ). (1 − bci )
∀k ∈ K, ∀c ∈ C, ∀i {0, ..., n − 1} (4.6)
n−1 X
pki = δk
∀k ∈ Kbci =
i=0
X
ack .pki
∀i ∈ {0, ..., n − 1} , ∀c ∈ C ∀i ∈ {0, ..., n − 1} , ∀c ∈ C\F
0 ≤ gci gci ≥
i X
bcj +
mX c −i−2
j=0
ecj − lc
∀i ∈ {0, ..., mc − 2} , ∀c ∈ C\F
(4.8) (4.9) (4.10)
j=0 i X
gci ≥
(4.7)
k∈K
bcj − lc
∀i ∈ {mc − 1, ..., n − 1} , ∀c ∈ C\F
(4.11)
∀i ∈ {0, ..., s − 1} , ∀f ∈ F
(4.12)
j=i−mc +1 i X j=0
bf j +
s−1−i X
ef j ≤ s
j=0 i X
bf j ≤ s
∀i ∈ {s, ..., n − 1} , ∀f ∈ F
(4.13)
0 ≤ wf i ≤ 1
∀i ∈ {0, ..., n − 1} , ∀f ∈ F
(4.14)
j=i−s
wf 0 ≥ bf 0 − ef 0 wf i ≥ bf i − bf (i−1) Bci , pki integer
∀i ∈ {1, ..., n − 1} , ∀f ∈ F
∀c ∈ C, ∀k ∈ K, ∀i ∈ {0, ..., n − 1}
(4.15) (4.16) (4.17)
4.4 Penggunaan Metode Pencarian Langsung Algoritma dari metode Setelah menyelesaikan problema relaksasi dengan metode yang diajukan untuk program stokastik linier, prosedur pencarian penyelesaian cacah dapat dideskripsikan sebagai berikut : Andaikan x = [x] + f, 0 ≤ f < 1
Nice Rejoice Refisis : Metode Pencarian Langsung Untuk Menyelesaikan Problema Car Sequencing, 2009 USU Repository © 2008
30
penyelesian kontinu dari problem relaksasi, dengan langkah-langkah berikut:
1 Pilih basis i∗ infisiklitas cacah terkecil, sehingga δi∗ = min{fi , 1 − fi } 2 Lakukan operasi pricing, yaitu hitung viT∗ = `Ti∗ B −1 3 Hitung σij =
T vi∗
n o aj dengan j berkaitan pada minj σ`iji
I. Untuk non basis j dibatas bawah Jika σij < 0 dan δi∗ = f i hitung ∆ =
(1−δi∗ ) −σij
Jika σij > 0 dan δi∗ = 1 − f i hitung ∆ = Jika σij < 0 dan δ = 1 − f i hitung ∆ = Jika σij > 0 dan δi∗ = f i hitung ∆ =
(1−δi∗ ) σij
δi∗ −σij
δi∗ σij
II. Untuk tak basis j di batas atas Jika σij < 0 dan δi∗ = 1 − f i hitung ∆ = Jika σij > 0 dan δi∗ = f i hitung ∆ =
(1−δi∗ ) σij
Jika σij > 0 dan δi∗ = 1 − f i hitung ∆ = Jika σij < 0 dan δi∗ = f i hitung ∆ =
(1−δi∗ ) −σij
δi∗ σij
δi∗ −σij
Jika tidak pergi ke non basis atas superbasis j berikutnya (jika ada). Jadi kolom j ∗ dinaikkan dari batas bawahnya atau diturunkan dari batas atasnya. Jika tidak ada pergi ke i∗ berikutnya. 4 Hitung αj ∗ = B −1 aj ∗ yaitu, selesaikan Bαj ∗ = aj ∗ untuk αj ∗ 5 Uji kelayakan terdapat 3 kemungkinan untuk peubah basis tetap layak karena pelepatan peubah nonbasis j ∗ dari batasnya.
Nice Rejoice Refisis : Metode Pencarian Langsung Untuk Menyelesaikan Problema Car Sequencing, 2009 USU Repository © 2008
31
→ jika j ∗ dibatas bawah Ambil A= B=
Min
nx
Min
na
i0 6=i∗|αij∗ >0
Bi0 −`i0
αij∗
o
i0 −xBi0
i0 6=i∗|αij∗ <0
−αij∗
o
C=∆ ∗
Gerak maksimum dari j tergantung pada θ∗ = min(A, B, C) → jika j ∗ dibatas atas Ambil 0
A = B0 =
Min
nx
Min
n a 0 −x
i0 6=i∗|αij∗ >0
Bi0 −`i0
−αij∗ i
i0 6=i∗|αij∗ <0
Bi0
αij∗
o o
0
C =∆ Gerak maksimum dari j ∗ tergantung pada θ∗ = min(A0, B 0, C 0) 6 Pertahanan basis untuk ke 3 kemungkinan 1. jika A atau A i. xBi menjadi nonbasis dibatas bawah `i0 ii. xj ∗ menjadi basis (menggantikan xBi ) iii. xi∗ tetap basis (tak cacah). 2. jika B atau B i. xBi menjadi nonbasis dibatas atas ai0 ii. xj ∗ menjadi basis (menggantikan xBi0 ) iii. xi∗ tetap basis (tak cacah). 3. jika C atau C i. xj ∗ menjadi basis (menggantikan ) ii. xi∗ menjadi superbasis bernilai cacah.
Nice Rejoice Refisis : Metode Pencarian Langsung Untuk Menyelesaikan Problema Car Sequencing, 2009 USU Repository © 2008
32
Ulangi dari langkah 1 4.5 Contoh Untuk Formula
Komp#1 Komp#2 Warna#1 Warna#2 Permintaan
H 1 0 1 0 3
Tabel 4.2 : Sebuah Uji Coba M M + Kendala Biaya 0 1 1/3 1 1 1 2/3 10 0 0 4/5 100 1 1 4/5 100 3 2 -
Keterangan : ∗). Mobil ditandai dengan + mengindikasi bahwa mobil perlu komponen. Contoh sederhana tabel 4.3.2 diatas menunjukkan nilai suatu uji tes. Ada tiga perbedaaan tiap-tiap konfigurasi terdiri dari dua komponen yang mungkin dan salah satu dari dua warna. Spesifikasi terbentuk untuk matriks A dan D, juga menghadirkan matrix E. Karena , hanya terakhir 5-1=4 mobil berproduksi sehari sebelumnya dibutuhkan perhitungan dengan adanya pelanggaran. 1 0 1 5 0 1 1 1 0 1 1 5 1 1 0 0 A = 1 0 0 D = 3 E = 0 0 1 1 0 1 1 5 1 1 0 0 Berikut sequence mobil sepanjang jalur produksi : (M, M +, H, H, H, M, M, M+) Perolehan matriks sebagai berikut :
0 1 B = 0 1
1 1 0 1
1 0 1 0
1 0 1 0
1 0 1 0
0 1 0 1
0 1 0 1
1 1 0 1
Nice Rejoice Refisis : Metode Pencarian Langsung Untuk Menyelesaikan Problema Car Sequencing, 2009 USU Repository © 2008
33
0 0 1 2 2 1 0 0 1 1 0 −1 −2 −1 0 1 Q = −3 −3 −3 −2 −1 −1 −1 −2 −1 0 0 −1 −2 −2 −2 −1
G =
0 0 1 2 2 1 0 0 1 1 0 0 0 0 0 1
H = ( 0 0 1 0 0 1 0 0 ) Matriks G dan vektor H relevant untuk evaluasi. Karena penjumlahan baris satu dalam matriks G adalah 6 dan baris kedua adalah 3, kesalahan kendala diperoleh pada jumlah produksi yakni (6.1)+(3.10)=36. Vektor H bernilai 2 yang mana maksudnya bahwa terjadi 2 pergantian warna. Dengan satu warna berubah nilainya 100, fungsi objektif diperoleh totalnya 236.
Nice Rejoice Refisis : Metode Pencarian Langsung Untuk Menyelesaikan Problema Car Sequencing, 2009 USU Repository © 2008
BAB 5 KESIMPULAN DAN SARAN
5.1 Kesimpulan Problema car sequencing (CarSP) ialah menentukan urutan memasangkan satu unit mobil pada suatu pabrik pembuatan mobil yang terdiri dari tiga urutan proses, yakni: proses fabrikasi bodi, proses pengecatan dan proses perakitan. Program Integer Linier (ILP) menghadirkan sebuah formula matematika untuk permasalahan optimisasi. Fungsi objektif linier ini meminimumkan atau memaksimumkan subjek pada kendala linier. Variabel keputusan harus integer dan penyelesaian harus memenuhi semua kendala. Formula ILP akan selalu menghasilkan solusi optimal untuk problema car sequencing. Kevalidan penyelesaian jika tepat satu mobil di tiap-tiap posisi yang mungkin, maksudnya ialah bahwa tepat satu konfigurasi menandai untuk setiap posisi. Metode Pencarian Langsung baik dipakai untuk menyelesaikan problema car sequencing (CarSP) yang dimodelkan sebagai program integer linier berskala besar, tepat dikembangkan karena pengerjaannya praktis. Terdapat pengaturan yang optimal dari kendaraan yang beroperasi disepanjang jalur produksi, meminimalkan kesalahan proses pengerjaan dan pergantian warna.
34
Nice Rejoice Refisis : Metode Pencarian Langsung Untuk Menyelesaikan Problema Car Sequencing, 2009 USU Repository © 2008
35
5.2 Saran Untuk kedepannya agar mencapai hasil yang lebih baik lagi, kepada peneliti lainnya hendaknya pemakaian metode pencarian langsung khususnya pada bagian kendala proses pengecatan, sangat diperlukan penambahan perbaikan untuk metode pencarian langsung ini.
Nice Rejoice Refisis : Metode Pencarian Langsung Untuk Menyelesaikan Problema Car Sequencing, 2009 USU Repository © 2008
DAFTAR PUSTAKA
Dincbas, M., Simonis, H., and Van Hentenryck, P. 1988, Solving the Car-Sequencing Problem in Constraint Logic Programming. In: Kodratoff Y (ed), Proc. Eur , Minich, Germany, Pitmann Publishing, London, pp29295. Duran, M., and Grossmann, I. E. 1986, A Mixed- Integer Nonlinear Programming Al-gorithm for Process Systems Synthesis,Amer. Inst. Eng , 32:592-606. Gent, I. P. April 1998, Two Result on Car-Sequencing Problems, Technical report, APES Department of Computer Science, University of Strathclyde, UK. Gottlieb, J., Puchta, M., and Solnon, C. 2003, A Study of Greedy, Local Search, and Ant Colony Optimization Approaches for Car Sequencing Problems. Proc Appl , volume 2611 of LNCS, halaman 246-257, Springer- Verlag Berlin Heidelberg. Gravel, M., Gagne, C., and Price, W. L. November 2005, Review and Comparison of Three Methods for the solution of the Car Sequencing problem, Journal of the Oper. Res. Soc, 56(11):1287-1295. Hu, B. 2004, Interaktive Reihenfolgeplanung fur die Automobiliidustrie, Masters thEsis, Vienna University of Technology, Vienna, Austria. Kis, T. 2004, On the Complexity of the Car Sequencing problem Oper. Res , 32(4):331-335. Lopez, P., dan Robellat, F. 2001, Ordonancement De La Production, Hermes Science Publications: Paris. Mawengkang, H. 1997, An Improved Search Algorithm for Solving Mixed Integer Nonlinear Programming Problem, Proc. Math. , Sydney, Australia. Mawengkang, H. 1985, Solving Non Linear Integer Programs with Large-Scale Optimization Software, Ann. Oper. Res, Vol. 5, pp. 425-437. Murtagh, B. A. 1981,Advance Linear Programming, Mc Graw-Hill Inc, New York. Prandstetter., M, and Raidl, G. R. 2005,Exact and Heuristic Methods for Solving the Car Sequencing Problem, Masters thesis, Vienna Universityof Technology, Vienna, Austria. Renker Gerrit. 2005,Modeling the Car Sequencing Problem, The Robert Gordon University Aberdeen.
36
Nice Rejoice Refisis : Metode Pencarian Langsung Untuk Menyelesaikan Problema Car Sequencing, 2009 USU Repository © 2008