ENUMERASI PARSIAL UNTUK SUATU MASALAH OPTIMISASI KOMBINATORIAL

ENUMERASI PARSIAL UNTUK SUATU MASALAH OPTIMISASI KOMBINATORIAL

TESIS

Oleh

RAFFLES NABABAN 067021024/MT

SEKOLAH PASCASARJANA UNIVERSITAS SUMATERA UTARA MEDAN 2008

Raffles Nababan: Enumerasi Parsial Untuk Suatu Masalah Optimisasi kombinatorial, 2008. USU e-Repository © 2008

ENUMERASI PARSIAL UNTUK SUATU MASALAH OPTIMISASI KOMBINATORIAL

TESIS

Untuk Memperoleh Gelar Magister Sains dalam Program Studi Magister Matematika pada Sekolah Pascasarjana Universitas Sumatera Utara

Oleh

RAFFLES NABABAN 067021024/MT

SEKOLAH PASCASARJANA UNIVERSITAS SUMATERA UTARA MEDAN 2008


Judul Tesis Nama Mahasiswa Nomor Pokok Program Studi

: ENUMERASI PARSIAL UNTUK SUATU MASALAH OPTIMISASI KOMBINATORIAL : Raffles Nababan : 067021024 : Magister Matematika

Menyetujui, Komisi Pembimbing

(Dr. Saib Suwilo, M.Sc) Ketua

(Prof. Dr. Herman Mawengkang) Anggota

Ketua Program Studi

Direktur

(Prof. Dr. Herman Mawengkang)

(Prof. Dr. Ir. T.Chairun Nisa. B,M.Sc)

Tanggal lulus: 4 Juni 2008


Telah diuji pada Tanggal 4 Juni 2008

PANITIA PENGUJI TESIS

Ketua

:

Dr. Saib Suwilo, M.Sc

Anggota

:

Prof. Dr. Herman Mawengkang Dr. Sutarman, M.Sc Dra. Mardiningsih, M.Si


ABSTRAK Di dalam tesis ini, Enumerasi parsial dipresentasikan untuk menyelesaikan masalah optimisasi kombinatorial menggunakan beberapa pendekatan seperti algoritma branch and bound. Salah satu masalah optimisasi kombinatorial yang dibahas adalah penemuan solusi optimal penjadwalan preemptive dari prosesor paralel tidak berelasi yang diformulasikan dan diselesaikan sebagaimana masalah program linier. Pada formulasi program linier batas atas (upper bounds) diperoleh pada bilangan preemption yang diperlukan untuk jadwal optimal. Kata kunci : Optimisasi kombinatorial, penjadwalan preemptive, prosesor paralel, program linier

i Raffles Nababan: Enumerasi Parsial Untuk Suatu Masalah Optimisasi kombinatorial, 2008. USU e-Repository © 2008

ABSTRACT In this thesis, presented a partial enumeration in solving the combinatorial optimization problem adopting some approaches such as branch and bound algorithm. One of combinatorial optimization problems discussed is the finding optimal solution to preemptive scheduling of parallel processor unrelated in formulation and solved as a linear programming problem. In formulation to the upper bounds linear program is obtained on a preemption numeral required for an optimal schedule. Keyword : Combinatorial optimization, scheduling preemptive, parallel processor, linear programming

ii Raffles Nababan: Enumerasi Parsial Untuk Suatu Masalah Optimisasi kombinatorial, 2008. USU e-Repository © 2008

KATA PENGANTAR Puji syukur penulis ucapkan kepada Tuhan Yang Maha Esa yang telah memberikan begitu banyak rahmat dan nikmat sehingga tesis ini dapat terselesaikan. Dalam menyelesaikan pendidikan di Sekolah Pasca Sarjana USU ini, penulis banyak mendapat dukungan dari berbagai pihak, maka pada kesempatan ini penulis mengucapkan terima kasih dan penghargaan yang sebesar-besarnya kepada:

Prof.dr. Chairuddin P. Lubis, DTM&H, Sp.Ak selaku Rektor Universitas Sumatera Utara. Prof. Dr. Ir. T. Chairun Nisa. B. M.Sc selaku Direktur Sekolah Pasca Sarjana Universitas Sumatera Utara yang telah memberikan kesempatan kepada penulis untuk mengikuti Program Studi Magister Matematika di Sekolah Pascasarjana Universitas Sumatera Utara. Prof. Dr. Herman Mawengkang selaku Ketua Program Studi Magister Matematika dan Dosen Pembimbing II yang telah banyak memberikan bimbingan dan bantuan serta motivasi kepada penulis sehingga penulisan tesis selesai dengan baik. Dr. Saib Suwilo, M.Sc selaku Sekretaris Program Studi Magister Matematika SPs USU dan Dosen Pembimbing I, yang telah banyak memberikan bimbingan dan bantuan serta motivasi kepada penulis sehingga penulisan tesis selesai dengan baik.

iii Raffles Nababan: Enumerasi Parsial Untuk Suatu Masalah Optimisasi kombinatorial, 2008. USU e-Repository © 2008

Seluruh Staff Pengajar pada Program Studi Magister Matematika P.Ps USU, yang telah membekali ilmu pengetahuan kepada penulis selama perkuliahan hingga selesai. Dra. Yurmaini Siregar selaku Kepala Sekolah SMA Negeri 18 Medan yang telah memberikan kesempatan dan dukungan kepada penulis untuk mengikuti Program Studi Magister Matematika di Sekolah Pascasarjana Universitas Sumatera Utara. Rekan-rekan seperjuangan, mahasiswa angkatan kedua yang telah turut membantu baik langsung maupun tidak langsung yang penulis dapatkan selama ini, semoga tesis ini dapat bermanfaat bagi pembaca. Saudara Mis, selaku Staf Administrasi Program Studi Matematika PPs. Universitas Sumatera Utara yang dengan penuh kesabaran memberikan pelayanan terbaik di Program Studi Matematikan PPs USU. Secara khusus penulis ingin menyampaikan terima kasih dan sayang yang mendalam kepada kedua orang tua penulis Ayahanda tercinta Alm. H. Nababan dan Ibunda tercinta N. br. Siahaan, istri tercinta Lindawaty Simangunsong, ananda tersayang Silvia Veronika Nababan dan Gabriel Rivaldo Nababan serta abang, kakak dan adikku yang senantiasa memberikan dorongan dengan penuh kesabaran dan pengorbanan serta selalu mendoakan keberhasilan penulis dalam menyelesaikan studi.

iv Raffles Nababan: Enumerasi Parsial Untuk Suatu Masalah Optimisasi kombinatorial, 2008. USU e-Repository © 2008

Hanya syukur dan terima kasih yang penulis dapat ucapkan kepada semua pihak untuk dukungan, doa dan arahan yang penulis dapatkan. Semoga tesis ini bermanfaat bagi pembaca dan pihak-pihak yang memerlukannya.

Medan, 23 Juni 2008 Penulis,

Raffles Nababan

v Raffles Nababan: Enumerasi Parsial Untuk Suatu Masalah Optimisasi kombinatorial, 2008. USU e-Repository © 2008

RIWAYAT HIDUP Raffles Nababan, lahir di Tornauli pada tanggal 16 Juli 1967 dan anak keempat dari 5 bersaudara dari ayah alm.H. Nababan dan Ibu N. br Siahaan. Menamatkan Sekolah Dasar (SD) negeri No. 173278 Pohantonga, Kec. Siborongborong pada tahun 1981, Sekolah Menengah Pertama (SMP) Negeri 1 Siborongborong pada tahun 1984, Sekolah Menengah Atas (SMA) Swasta Cahaya Medan pada tahun 1987. Pada tahun 1987 masuk Perguruan tinggi FMIPA USU (Diploma Tiga ) jurusan Pendidikan matematika dan memperoleh gelar AMD (Ahli Madya) pada tahun 1990. Pada Januari 1991 Penulis dianggkat menjadi Guru SMA Negeri Simpang Kanan, Kabupaten Aceh Selatan. Pada tahun 1997 penulis pindah tugas dari SMA Negeri Simpang kanan ke SMA Negeri 18 Medan. Kemudian Pada tahun 1999 masuk Universitas Negeri Medan , Fakultas Matematika dan Ilmu Pengetahuan Alam jurusan Pendidikan Matematika dan memperoleh gelar Sarjana Pendidikan (S.Pd) pada tahun 2001. Pada tahun 1996 menikah dan dikarunia anak satu putri dan satu putra. Pada tahun 2007 mengikuti pendidikan Program Studi Magister Matematika di Sekolah Pascasarjana Universitas Sumatera Utara.

vi Raffles Nababan: Enumerasi Parsial Untuk Suatu Masalah Optimisasi kombinatorial, 2008. USU e-Repository © 2008

DAFTAR ISI Halaman ABSTRAK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

i

ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

ii

KATA PENGANTAR . . . . . . . . . . . . . . . . . . . . . . . . .

iii

RIWAYAT HIDUP . . . . . . . . . . . . . . . . . . . . . . . . . .

vi

DAFTAR ISI . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

vii

BAB 1 PENDAHULUAN . . . . . . . . . . . . . . . . . . . . . . .

1

1.1 Latar Belakang . . . . . . . . . . . . . . . . . . . . . .

1

1.2 Perumusan Masalah . . . . . . . . . . . . . . . . . . . .

4

1.3 Tujuan Penelitian . . . . . . . . . . . . . . . . . . . . .

4

1.4 Kontribusi Penelitian . . . . . . . . . . . . . . . . . . .

5

1.5 Metodologi . . . . . . . . . . . . . . . . . . . . . . . .

5

1.6 Pembatasan Masalah . . . . . . . . . . . . . . . . . . .

5

BAB 2 TINJAUAN PUSTAKA . . . . . . . . . . . . . . . . . . . .

6

2.1 Enumerasi Parsial . . . . . . . . . . . . . . . . . . . . .

8

2.2 Pendekatan Polyhedral . . . . . . . . . . . . . . . . . .

10

2.3 Algoritma Branch and Bound . . . . . . . . . . . . . . .

11

BAB 3 ENUMERASI PARSIAL DAN MASALAH OPTIMISASI KOMBINATORIAL . . . . . . . . . . . . . . . . . . . . . . . .

12

3.1 Optimisasi Kombinatorial . . . . . . . . . . . . . . . . .

12

3.2 Model Masalah Optimisasi Kombinatorial . . . . . . . . .

13

3.2.1 Model-Model Masalah . . . . . . . . . . . . . . . .

16

vii Raffles Nababan: Enumerasi Parsial Untuk Suatu Masalah Optimisasi kombinatorial, 2008. USU e-Repository © 2008

3.2.2 Penemuan Solusi . . . . . . . . . . . . . . . . . .

17

3.2.3 Program Integer

. . . . . . . . . . . . . . . . . .

19

3.3 Heuristik . . . . . . . . . . . . . . . . . . . . . . . . .

19

3.4 Heuristik Enumerasi Parsial Objektif Ganda . . . . . . . .

23

3.5 Algoritma Exact

. . . . . . . . . . . . . . . . . . . . .

26

3.6 Enumerasi Branch dan-Cut Algoritma . . . . . . . . . . .

28

3.7 Dasar Heuristik pada Enumerasi Parsial . . . . . . . . . .

29

3.7.1 Notasi . . . . . . . . . . . . . . . . . . . . . . .

30

3.7.2 Masalah R//Cmax . . . . . . . . . . . . . . . . . .

31

3.7.3 NP-hardness dan State of the art . . . . . . . . . .

32

3.8 Branch and Bound . . . . . . . . . . . . . . . . . . . .

33

3.8.1 Strategi Pencabangan (Branching) . . . . . . . . . .

34

3.8.2 Batas Bawah (Lower Bounds) . . . . . . . . . . . .

34

BAB 4 ENUMERASI PARSIAL UNTUK PENJADWALAN PREEMPTIVE PADA PROSESOR PARALEL TIDAK BERELASI . . .

36

4.1 Formulasi Program Linear dari Masalah Cmax . . . . . . .

38

4.2 Membentuk Solusi yang Mungkin . . . . . . . . . . . . .

39

4.3 Batas Bilangan Preemptions . . . . . . . . . . . . . . . .

43

BAB 5 KESIMPULAN DAN SARAN . . . . . . . . . . . . . . . . .

48

5.1 Kesimpulan . . . . . . . . . . . . . . . . . . . . . . . .

48

5.2 Saran . . . . . . . . . . . . . . . . . . . . . . . . . . .

48

DAFTAR PUSTAKA . . . . . . . . . . . . . . . . . . . . . . . . .

49

viii Raffles Nababan: Enumerasi Parsial Untuk Suatu Masalah Optimisasi kombinatorial, 2008. USU e-Repository © 2008

BAB 1 PENDAHULUAN

1.1 Latar Belakang Optimisasi kombinatorial adalah bagian dari optimisasi pada matematika terapan dan komputer sains dan berkaitan dengan operasi riset, teori algoritma dan teori perhitungan kompleksitas. Karla dkk. (2000) Optimisasi kombinanatorial merupakan proses penemuan satu atau lebih solusi optimum pada ruang masalah diskrit. Seperti masalah yang terjadi pada bidang manajemen (misalnya keuangan, pemasaran, produksi, penjadwalan, kontrol inventaris, fasilitas dan tata ruang, data-base manajemen), dan pada bidang teknik seperti rancangan optimum jalan atau jembatan, rancangan dan analisis jaringan data, solid waste manajemen, masalah dalam crystallography. Masalah optimisasi kombinatorial berhubungan dengan alokasi tepat-guna dari sumber-sumber yang memenuhi fungsi objektif. Sumber-variabel yang terbatas seperti tenaga kerja, persediaan atau modal adalah alternatif yang benarbenar dipertimbangkan. Karen dan Stan (1997) Knapsack Problem : Andaikan N = {1, 2, . . . n} dari items, setiap item memiliki bobot aj dan nilai cj , sebuah knapsack dipenuhi bersama himpunan bagian item, sedemikian sehingga bobot kumulatif item-item tidak melebihi ambang batas yang diberikan dan nilai kumulatif adalah maksimum. Knapsack polytope terjadi sebagai substruktur dalam kapasitas masalah

1 Raffles Nababan: Enumerasi Parsial Untuk Suatu Masalah Optimisasi kombinatorial, 2008. USU e-Repository © 2008

2 optimisasi kombinatorial. Masalah Knapsack diformulasikan sebagai: max

X

s.t.

X

Cj xj

j∈N

aj xj ≤ b

j∈N

xj ∈ {0, 1} untuk semua j ∈ N dimana a, c adalah vektor dan b rasional, xk merupakan himpunan penyele saian yang mungkin pada masalah knapsack. Himpunan cover atau himpunan lepas, P P aj > b. Sebuah cover minimal jika j∈S aj ≤ b yang berkaitan dengan N jika j∈C

untuk semua S ⊂ C.

Beberapa Aplikasi Optimisasi Kombinatorial

1. Jaringan dan Masalah Graph Sebagian besar masalah-masalah optimisasi kombinatorial dapat dijelaskan oleh suatu jaringan (graph). Suatu graph ditunjukkan oleh nodes dan oleh arcs terhubung dengan nodes itu. Beberapa masalah-masalah praktis timbul disekitar jaringan yang berkaitan dengan alam misalnya jalan di kota, jalan tol, sistem kereta api, jaringan komunikasi). 2. Masalah Penjadwalan dengan Aturan-Dasar. Beberapa masalah penjadwalan yang tidak mungkin untuk mencatat semua pembatas secara ilmu pasti (mathematically). Seperti masalah-masalah yang timbul pada penjadwalan dimana terdapat beribu-ribu pembatas misalnya tenaga kerja, pilihan penjadwalan perusahaan dan aturan-aturan lain yang berkaitan dengan aturan-aturan yang mungkin. Masalah penjad-


3 walan dapat diselesaikan dengan membenuk semua atau beberapa himpunan bagian yang layak dari jadwal yang mungkin untuk setiap pekerja.

Beberapa Pendekatan untuk Optimisasi Kombinatorial Ada beberapa pendekatan untuk menyelesaikan masalah optimisasi kombinatorial yaitu:

1. Polyhedral (Baiou, 2007) 2. Branch and Bound ( Pedroso, 2004) 3. Neural Network ( Wang dkk, 2004) 4. Metode Heuristic ( Pedroso, 2004).

Metode Enumerasi Parsial Peiyi dan Markus (2005) Diberikan himpunan item-item sering I = i1, i2, . . . , in dengan urutan naik. Algoritma FP-pertumbuhan pada dasarnya berusaha menemukan semua itemsets sering yang memuat i1, kemudian yang i2 tetapi tidak memuat i1, itemset yang memuat i3 tetapi bukan i1i2 dan seterusnya.

Un-

tuk menemukan itemset sering yang memuat i1, algoritma ini mengembangkan database bersyarat atas i1 dan menggunakan algoritma yang sama secara rekursif. Pola yang sering meningkat dengan semakin dalamnya kunjungan rekursif. Dengan demikian, himpunan itemsets sering dapat ditentukan tanpa menghitung kandidat-kandidat.


4 Dengan mengunakan perpartisan k-prefix untuk mempartisi ruang pencarian dan mendapat tugas yang lebih paralel untuk penyeimbang beban yang lebih baik. Dalam percobaan ini ditemukan algoritma FP-pertumbuhan paralel yang dijalankan prosesor tunggal yang lebih cepat dari pada algoritma FP-pertumbuhan semula. Ketika mempartisi ruang pencarian untuk tugas-tugas yang paralel, sebenarnya menghitung prefix masing-masing pola sering yang mungkin dan kemudian mengoperasikan algoritma FP-pertumbuhan untuk mencari sisanya. Tingkat penghitungan ini dikontrol oleh parameter 1 ≤ k < n. Karena k < n , ini disebut enumerasi parsial.

1.2 Perumusan Masalah Model optimisasi kombinatorial merupakan suatu model yang tercakup dalam problem Non Polynomial ( -Hard problem). Teknik secara enumerasi sangat tidak efisien. Sebagai metode analitik ada yang masih terbatas untuk skala kecil dan ada pula yang berlaku untuk kelas tertentu dari masalah-masalah ini. Perlu dilakukan penelitian, bagaimana enumerasi parsial dapat digunakan untuk menyelesaikan suatu masalah optimisasi kombinatorial.

1.3 Tujuan Penelitian Adapun tujuan dari penelitian ini adalah untuk menyelesaikan suatu masalah optimisasi kombinatorial menggunakan pendekatan enumerasi parsial.


5 1.4 Kontribusi Penelitian Penyelesaian masalah optimisasi kombinatorial dengan pendekatan enumerasi parsial dapat bermanfaat bagi perkembangan ilmu pengetahuan dan bahan kajian bagi Peneliti tentang masalah optimisasi kombinatorial.

1.5 Metodologi Penelitian ini adalah penelitian literatur dan dalam penelitian ini dibahas masalah optimisasi kombinatorial, metode-metode yang digunakan untuk menyelesaikan suatu masalah optimisasi kombinatorial seperti metode branch and bound, heuristik dan polyhedral. Pada penelitian ini akan dipilih satu masalah optimisasi kombinatorial. Selanjutnya dibahas pendekatan enumerasi parsial untuk menyelesaikan suatu masalah optimisasi kombinatorial.

1.6 Pembatasan Masalah Masalah yang berkaitan dengan optimisasi kombinatorial sangat banyak, oleh karena itu masalah yang diteliti dalam penelitian ini dibatasi hanya pada penjadwalan preemptive prosesor paralel yang tidak berelasi.


BAB 2 TINJAUAN PUSTAKA

Menyelesaikan masalah optimisasi kombinatorial merupakan tugas yang sulit. Kesulitan itu timbul dari fakta bahwa program linear berbeda, sebagai contoh, kemungkinan daerah solusi adalah himpunan konveks, pada masalah-masalah kombinatorial, satu keharusan mencari pola-pola geometri dari titik-titik yang mungkin untuk menemukan solusi optimum. Jadi, program linear berbeda, seharusnya konveksitas dari masalah itu dieksploitasi fakta bahwa suatu daerah penyelesian adalah optimum global. Masalah program integer mempunyai daerah optimum dan penemuan optimum global dengan memerlukan satu masalah untuk membuktikan bahwa fakta-fakta penyelasaian yang didominasi semua titiktitik yang mungkin dengan argumen dari pada pendekatan berdasarkan kalkulusturunan dari program konveks. Ada tiga pendekatan yang berbeda untuk menyelesaikan masalah program integer murni, walaupun ketiga pendekatan itu sering digabung pada prosedur penyelesaian ”hybrid” dalam perhitungan praktis. Ketiga pendekatan itu adalah:

1. relaksasi dan teknik dekomposit 2. cutting planes approaches based on polyhedral combinatoric 3. pendekatan enumerasi

Pendekatan enumerasi : pendekatan paling sederhana untuk menyelesaikan masalah program integer murni adalah mengenumerasi semua yang mungkin un6 Raffles Nababan: Enumerasi Parsial Untuk Suatu Masalah Optimisasi kombinatorial, 2008. USU e-Repository © 2008

7 tuk memperoleh solusi. Bagaimanapun, seharusnya ”combinatorial explotion” dihasilkan dari ”ukuran” parameter, hanya hal paling kecil yang dapat diselesaikan dengan pendekatan seperti itu. Pendekatan masalah ini adalah bilangan solusi diteliti pertambahan perhitungan eksponen bersama ukuran masalah tersebut. Sebagai contoh, menyelesaikan masalah jadwal dengan hanya 210 tempat (10 staf, 7 hari dan 3 shif) mempunyai beberapa solusi yang mungkin. Pengaruh ini disebut combinatorial explosion. Disamping menggunakan enumerasi implisit biasanya digunakan pendekatan enumerative yang disebut branch and bound, dimana ”branching” menunjukkan enumerasi sebagian dari teknik penyelesaian dan ”bounding” menunjukkan ukuran dari penyelesaian yang mungkin dengan perbandingan untuk mengetahui batas atas dan batas bawah pada nilai penyelesaian (Land dan Doig, 1960). Relaksasi lagrangian dan teknik dekomposit: Pendekatan pelonggaran semua pembatas tidak hanya pada pelonggaran masalah. Suatu pendekatan alternatif untuk solusi pada masalah program integer adalah mengambil sebuah himpunan pembatas yang sulit ke dalam fungsi objektif pada model lagrangian. Pendekatan ini dikenal sebagai relaksasi lagrangian.Dengan mengambil himpunan pembatas yang mempersulit kendala dari himpunan kendala dihasilkan submasalah yang sering kali lebih mudah untuk diselesaikan. Terakhir adalah melakukan pendekatan yang berlaku karena submasalah harus diselesaikan dengan berulangulang hingga diperoleh nilai optimum. Cutting Plane algorithms based on polyhedral combinatorics : kemajuan perhitungan yang signifikan mengambil bagian dalam optimisasi yang tepat. Ide yang mendasari polyhedral combinatorics adalah menempatkan kembali himpunan


8 kendala dari sebuah masalah program integer dengan suatu alternatif konveksifikasi dari titik-titik yang mungkin dan sinar ekstrim dari masalah.

2.1 Enumerasi Parsial Mayne dkk. (2000) Sebagian besar implementasi MPC (Model Predictive Control) yang berhubungan dengan industri lebih cepat dari usaha pemecahan offline yang rumit dan menyimpan seluruh control umpan balik aturan u(x) untuk penyelesaian online yang rumit control open-loop optimum, diberikan keterangan keadaan awal x pada waktu diberikan satu sampel. Peneliti mengembangkan metode-metode yang menarik untuk menyelesaikan dan melengkapi aturan umpan balik closed-loop, dipertimbangkan model-model yang bekerja baik untuk masalah berdimensi rendah. Masalah-masalah kecil dapat diselesaikan dengan baik melalui metode online dan metode offline. Tetapi, dengan semakin meningkatnya ukuran masalah, pada akhirnya pendekatan penghitungan MPC baik online maupun offline tidak bisa memberikan kontrol pada waktu sampel tersedia. Gabriele dkk.(2007) Mengkaji kelas dari masalah besar yang tidak bisa ditangani dengan metode saat ini dengan mengajukan teknik enumerasi parsial (EP). EP menghindari kontrol optimal untuk suatu yang mungkin sedikit suboptimal, tetapi yang tetap dapat ditangani untuk implementasi nyata pada masalahmasalah besar. Pendekatan ini memadukan metode optimisasi dan penyimpanan online untuk mencapai hasil tersebut. Mengikuti ciri-ciri kontrol masalah haruslah ada agar pendekatan ini efektif : (i) Hal penting gangguan deterministik besar dan setpoint memberi tanda isyarat merubah dengan lambat bersama waktu. (ii) Gangguan stokastik, yang cepat berubah bersama waktu, hal penting memi-


9 liki kelayakan yang kecil. Sebagaimana namanya enumerasi parsial mengusulkan, himpunan pembatas aktif yang kelihatan ditetapkan bersama frekuensi tertinggi, diberikan himpunan yang layak dari gangguan dan merubah setpoint. Solusi optimum untuk himpunan pembatas aktif sering dihitung secara offline dan disimpan di dalam tabel. Tabel ini dicari secara online untuk kontrol terbaik. Selama operasi online, solusi optimal diharapkan pada yang lepas dari beberapa sampel waktu karena bilangan perserta masuk dalam tabel adalah perbandingan kecil pada bilangan himpuna aktif optimum yang mungkin. Akan tetapi, tabel disesuaikan secara online dengan himpunan aktif baru perusahan begitu timbul kebutuhan akan tabel tersebut. Bila penyelesaian optimal tidak ditemukan pada sampel waktu, digunakan strategi suboptimal yang lebih sederhana untuk kontrol saat ini, tetapi penyelesaian optimal juga ditemukan dan dimasukkan dalam tabel. Pada sebagian besar titik sampel, penyelesaian ditemukan dalam tabel (yang memberikan kontrol optimum), tetapi tanpa menegakkan optimalitas yang ketat pada setiap sampel, kontrol bisa dihitung dengan cepat bahkan untuk masalah besar. Dari sudut pandang teoritis murni, strategi penghitungan total yang dijelaskan di atas tidak menarik, karena strategi tersebut menggantikan metode waktu-polinomial untuk penyelesaian setiap submasalah MPC (yaitu, metode titik-interior) dengan metode yang jelas-jelas bukan metode polinomial. Dari segi praktisnya, penghitungan offline-identifikasi semua daerah di dalam ruang (bs , w0) mungkin cocok untuk masalah SISO ( single input single output) dengan horizon kontrol N yang relatif pendek, tetapi ini cepat menjadi resistan sesuai dengan peningkatan dimensi (m, n) dan horizon kontrol N.


10 Tujuan strategi enumerasi parsial adalah untuk menjadikan penghitungan online cepat, menghasilkan input yang optimum, dalam waktu yang dimungkinkan sistem. Tujuannya adalah untuk mengekspansikan ukuran dan kompleksitas sistem yang mana MPC mungkin tetap berlaku, dengan membatasi himpunan aktif a yang mungkin dinilai dalam penghitungan online pada himpunan aktif yang paling sering muncul pada titik-titik keputusan. Pada pokoknya, riwayat sistem digunakan untuk meningkatkan efisiensi praktis penghitungan kontrol. Pengamatan atas banyaknya masalah praktis yang berukuran besar mengindikasikan bahwa parameter (bs , w0) yang ditemukan pada titik-titik keputusan selama Jendela waktu termasuk daerah dalam jumlah relatif kecil yang didefinisikan oleh ketaksamaan atas semua himpunan aktif a yang mungkin. Karenanya, akan tampak jelas bahwa penghitungan offline yang dilaksanakan dengan penghitungan total, yang melibatkan pempartisan komprehensif dari ruang, sebagian besar percuma.

2.2 Pendekatan Polyhedral Untuk menyelesaikan masalah optimisasi kombinatorial dapat digunakan pendekatan polyhedral (Baiou, 2007). Diberikan sebuah himpunan berhinga E = {e1, e2, . . . , en }. Misalkan F keluarga dari beberapa keterangan-keterangan himpunan bagian E (solusi yang mungkin), dan misalkan c fungsi biaya, sebuah pemetaan c : E → R. Problem (P ) : minimize {c(f ) =

X

c(e) : f ∈ F }

e∈F

disebut problem optimisasi kombinatorial.


11

2.3 Algoritma Branch and Bound Penjadwalan pekerjaan pada mesin paralel yang tidak berelasi adalah masalah yang umum, sekumpulan mesin memproses suatu pekerjaan secara simultan. Masalah pada mesin paralel yang tidak berelasi adalah generalisasi dari mesin paralel yang seragam dan identik. Ketika beberapa mesin identik, pemrosesan suatu pekerjaan tertentu memerlukan waktu yang sama. Dalam hal ini mesin-mesin disebut seragam, kecepatan suatu mesin memproses suatu pekerjaaan adalah proporsional dengan mesin lainnya berdasarkan faktor kecepatan. Pada kasus mesin tidak berelasi yang umum, waktu pemrosesan suatu pekerjaan pada suatu mesin tidak bergantung dengan waktu pemrosesan yang dibutuhkan oleh mesin lain. Algoritma Branch and Bound menemukan solusi optimum pada masalah mesin paralel tidak berelasi dengan batasan faktor kelayakan mesin. Tujuan utama dari algoritma ini adalah meminimisasi waktu penyelesaian maksimum. Ketika batasan kelayakan mesin diperhitungkan, beberapa pekerjaan hanya dapat diproses pada mesin dengan batasan kelayakan tertentu.


BAB 3 ENUMERASI PARSIAL DAN MASALAH OPTIMISASI KOMBINATORIAL

3.1 Optimisasi Kombinatorial Banyak model umum dari masalah optimisasi dan satu dapat dipakai pada sebagian besar model lembar penjabaran (spreadsheet) adalah masalah optimisasi kombinatorial. Beberapa model spreadsheet berisi variabel-variabel dan mengukur keefektipan penghitungan. Pemakai spreadsheet sering mengganti variabelvariabel dalam suatu cara tak berstruktur untuk mencari solusi yang menghasilkan ukuran paling besar atau paling kecil dari pengukuran. Dalam operasi riset (OR), analisa pencarian solusi optimisasi suatu fungsi tujuan, mengukur keefektipan. Kombinatorik adalah cabang dari pelajaran matematik enumerasi, Kombinasi dan permutasi elemen-elemen dari himpunan dan hubungan matematika yang menggambarkan sifat-sifatnya. Optimisasi kombinatorial tidak hanya mengenumerasi himpunan-himpunan, tetapi mempunyai tujuan untuk menemukan anggota dari himpunam yang optimisasi suatu fungsi objektif. Untuk OR, optimisasi kombinatorial menjadi metode yang berarti untuk menemukan optimum dari masalah-masalah pada ruang solusi diskrit. Model-model untuk beberapa masalah optimisasi kombinatorial yang betul-betul dipertimbangkan menurut penelitian OR termasuk minimal spanning tree, shortest path tree, traveling salesman, quadratic assigment, pekerjaan mengatur dan menentukan arah kendaraan. Program linear juga merupakan masalah optimisasi kombinatorial meskipun nilai optimum dapat diperoleh hanya pada 12 Raffles Nababan: Enumerasi Parsial Untuk Suatu Masalah Optimisasi kombinatorial, 2008. USU e-Repository © 2008

13 titik ekstrem. Program non linear adalah sebuah masalah optimisasi kombinatorial yang mempertimbangkan penemuan optimum global dari suatu daerah optima. Setiap model spreadsheet bersama objek tunggal dan terbatas dapat di pandang sebagai masalah optimisasi kombinatorial. Model adalah membentuk dan metode pemecahan yang diimplementasikan dalam optimisasi dan combinatoric add-ins. Optimize add-in adalah paling umum dan menghasilkan pemecahan untuk beberapa golongan dari masalah. Combinatorics add-in mengambil keuntungan dengan ciri khas dari masalah kasus khusus untuk menghasilkan solusi tercepat. Contoh aplikasi add-in, seperti Facility Layout, digunakan metode pemecahan masalah optimisasi kombinatorial untuk meperoleh solusi terbaik.

3.2 Model Masalah Optimisasi Kombinatorial Selanjutnya diberikan model umum masalah optimisasi kombinatorial (MOK). Suatu masalah dapat dinyatakan maksimum atau minimum. Bentuk model ini diimplementasikan dalam optimize add-in. Gambaran model selanjutnya digunakan Program integer-linear( PI ). Masalah Optimisasi Kombinatorial : MOK Z = min f (x) x∈X∩G

X = (x1 , . . . , xn ) : Solosi, sebuah n dari integer f (x) : Fungsi objektif, nilai tunggal fungsi real dari x X : Himpunan dari solusi dalam ruang solusi G : himpunan dari solusi yang mungkin.


14 Tempat model ini sangat sedikit pembatasan pada komponen model. Kemudian prinsip metode dari solusi memerlukan enumerasi dimana tidak perlu memberi batas fungsi yang diperlukan. Kasus khusus dari model akan ditambahkan pembatasan, dan metode-metode pemecahan untuk kasus khusus terikat pada pembatasan ini. Sebuah solusi dari x adalah sebuah vektor dari integer. Untuk pemakaian spreadsheet, komponen solusi individual bisa di petak dimana saja pada lembar kerja, biasanya disusun untuk kemudahan hubungan pada pemakaian. Sebuah solusi adalah anggota dari ruang solusi X. Solusi diskrit daerah X adalah menetapkan digunakan hubungan tepat anggota-anggota dari himpunan yang harus memenuhi. Bilangan dari solusi dalam ruang solusi adalah berhingga. Suatu contoh dibawah dimana vektor solusi terbatas pada integer antara batas bawah dan batas atas. Pembatasan ini untuk Program Integer ( PI ). X = {x|lj ≤ xi ≤ uj dan integer untuk j = 1, . . . , p} Definisi dari X sangat penting untuk model-model ini, karena itu akan berbeda untuk kelas berbeda dari suatu masalah. Untuk masalah permutasi, X adalah himpunan dari semua permutasi n integer. Untuk masalah perjalanan salesman adalah himpunan semua perjalanan melalui n kota. Rancangan himpunan X menetapkan bilangan dari solusi yang harus dienumerasi atau dengan enumerasi parsial dalam pencarian sampai optimum. Fungsi objektif, f(x), adalah bilangan real tunggal dan pengukurannya dengan membandingkan solusi alternatif. Fungsi ini akan dievaluasi dalam sel lembar kerja tunggal, tetapi bisa dihasilkan dengan melakukan perhitungan dalam beberapa sel dan menyamakan pada beberapa lembar kerja dalam sebuah buku


15 kerja. Fungsi harus dapat dihitung untuk semua x dalam ruang solusi. Untuk PI, fungsi objektif adalah sebuah fungsi linear. f (x) =

n X

cj xj

j=1

G adalah himpunan solusi yang mungkin. Beberapa aplikasi mempunyai beberapa perbedaan hubungan logika yang semua harus dipenuhi (dengan logika benar) jika solusi adalah mungkin. Hubungan logika mudah diperlihatkan pada spreadsheet. Pernyataan diperlukan dalam G harus dapat dihitung untuk semua solusi dalam X. G = {x : φ(x) ∧ · · · ∧ φm (x)} φi (x) : pernyataan logika yang bernilai benar atau salah, untuk i = l . . . m ∧ : Operator DAN dari aljabar Boolean G adalah himpunan dari semua solusi untuk semua φi (x) adalah benar. Dipertimbangkan lagi suatu PI, komponen-komponen G berasal dari pembatas linear. Ditunjukkan dengan mengikuti perkembangan pembatas ”lebih kecil atau sama”. Perkembangan yang sama diikuti untuk pembatas persamaan dan lebih besar atau sama.


16 Untuk i = l . . . m m X

aij xj ≤ bi : pembatas linear

j=1

S1 = bi −

m X j=1

φ(x) =

aij xj : variabel slack    Benar jika si ≥ 0   Salah

jika si < 0

Solusi optimum adalah solusi yang merupakan minimisasi (maksimumisasi) dari fungsi objektif sepanjang semua solusi yang mungkin dalam ruang solusi. Walaupun batas himpunan kedua X dan G ditemukan solusi optimum, metode solusi X adalah sangat penting. Mencari solusi tidak terbatas oleh X, tetapi hanya dipertimbangkan untuk mengoptimumkan solusi-solusi yang mungkin, anggota G. Proses pembangkit solusi dari himpunan X adalah dicakup dalam algoritma solusi untuk setiap model khusus dari masalah , juga hanya dari anggota-anggota pembangkit X.

3.2.1 Model-Model Masalah Mengenali sebuah model masalah dengan keputusan-keptutusan dan ruang keputusan-keputusan dapat digambarkan. Untuk setiap solusi diberikan oleh sebuah vektor dari variabel integer. x = (x1 , x2, . . . , xn ) Dipertimbangkan mengenali empat model, masing-masing pada ruang- solusinya yaitu: Range X = {x : lj ≤ xi ≤ uj } dan integer untuk j = 1, . . . , n


17 xi : Penugasan integer pada posisi ke-i dari permutasi Permutasi X = {x : x adalah permutasi dari i . . . n} xi : kota mengikuti kota i pada perjalanan. Adalah (i, xi) pada perjalanan.

TSP X = {x : x menentukan perjalanan } xi : node yang sebelumnya node i dalam tree. Adalah (xi , i) dalam tree. Tree X = {x : xlangsung ditentukan akar pohon pada node 1 }

3.2.2 Penemuan Solusi Tujuan umum adalah menemukan solusi umum fungsi objektif dalam X maksimum atau minimum. Beberapa masalah seperti minimal spanning tree, shortest path tree dan yang lain algoritma sangat efisien untuk menemukan solusi optimum. Ada beberapa paper menguraikan algoritma-algoritma yang sangat cepat untuk menyelesaikan masalah-masalah ini. Masalah ini disebut masalah yang mudah, misalnya masalah traveling salesman. Masalah yang sulit tidak dapat diselesaikan pada hari hkecepatan komputer dan tidak mungkin diselesaikan. Ini disebut masalah yang sukar. Masalah sukar biasanya diselesaikan dengan enumerasi dari ruang penyelesaian. Kebanyakan kasus, enumerasi sempurna dari semua pemecahan adalah


18 penting untuk menentukan nilai optimum. Walaupun dalam prakteknya untuk masalah kecil, metode ini menjadi tidak mungkin untuk masalah ukuran sedang. Untuk beberapa jenis masalah, dengan metode enumerasi implicit bisa diperoleh solusi optimum untuk masalah-masalah besar. Ini termasuk metode branch dan bound dari PI dan program diskrit dinamis. Enumerasi implicit mempertimbangkan semua solusi tetapi himpunan bagian yang besar hilang dengan uji numerikal yang menjamin optimum tidak terletak pada himpunan bagian yang hilang. Pendekatan yang diambil dalam add-ins adalah dasar utama pada salah satu yang sempurna atau enumerasi parsial. Penelitian enumerasi parsial berkenaan dengan perbandingan kecil dari ruang solusi menggunakan heuristik. Sebuah solusi diperoleh melalui heuristik yang sewaktu-waktu adalah solusi yang baik, tetapi itu tidak dinyatakan sebagai optimum. Heuristik digunakan dengan add-ins termasuk greedy heuristic, random solution generation dan perbaikan heuristik. Ini hanya sebagai pengantar pada sebuah bilangan besar dengan betul-betul mempertimbangkan metode heuristik dalam literatur termasuk tabu search, simulated annealing, genetic Algorithms dan yang lain. Heuristik digunakan dengan add-ins termasuk greedy heuristic, random solution generation dan perbaikan heuristik. Ini hanya sebagai pengantar pada sebuah bilangan besar dengan betul-betul mempertimbangkan metode heuristik dalam literatur termasuk tabu search, simulated annealing, genetic Algorithms dan yang lain.


19 3.2.3 Program Integer Bentuk umum model Program Integer (PI). Model Program Integer : z = min

n X

cj xj

j=1

Kendala n X

aij xj ≤ bi untuk i = 1, . . . , m

j=1

0 ≤ xj ≤ uj dan integer untuk j = 1, . . . , n Pada model program integer seperti masalah optimisasi kombinatorial menghasilkan pernyataan eksplisit untuk komponen-komponen dari masalah optimisasi kombinatorial. Model Program Integer : z = min f (x) =

n X

cj xj

j=1

X = {x : lj ≤ xj ≤ uj dan integer untuk j = 1 . . . n} n P aij xj variabel slack si = bi − j=1   Benar jika si ≥ 0 φ(x) =   Salah jika si < 0 3.3 Heuristik Analisis operasi riset telah mempertimbangkan secara rutin pemakaian heuristik untuk memperoleh solusi yang baik dalam berbagai masalah yang dianggap


20 terlalu kompleks untuk memperoleh solusi optimal. Selanjutnya, heuristik memberikan dua tujuan yang sangat penting : Memberikan solusi-solusi yang baik terhadap berbagai masalah dimana algoritma terbaru tidak mampu memberikan optimalitas dalam waktu yang tepat dan untuk membantu meningkatkan algoritma efisien yang tepat. Penelitian heuristik dimulai dengan konsep pencarian lokal dengan jalan membentuk sebuah solusi yang mungkin dan memperbaiki solusi tersebut dengan melakukan pergerakan lokal atau swaps. Algoritma dibentuk untuk mencari solusi yang mungkin dan berusaha membuat solusi yang baik, yakni, melakukan pergerakan tunggal terbaik tanpa melihat terlebih dahulu, mempertimbangkan dampak dari pergantian variabel tertentu dalam solusi program linear. Demikian juga, memperbaiki heuristik dapat mempertimbangkan kedekatan dari solusi terbaru, atau dapat mempertimbangkan gerakan-gerakan yang lebih rumit. Algoritma annealing yang disimulasikan didasarkan pada sifat-sifat mekanik statistik, proses annealing memerlukan pendinginan logam yang lambat untuk memperbaiki kekuatannya. Analogi tersebut adalah bahwa seseorang akan beralih secara lambat pada solusi yang mungkin dengan memasukkan komponen pengacakan. Dengan probabilitas tertentu, algoritma memungkinkan pergerakan yang menghasilkan solusi. Meskipun demikian, ketika algoritma berlanjut, probabilitas gerakan-gerakan tersebut akan diambil berkurang. Demikian juga, algoritma genetik atau evolusioner didasarkan pada sifat-sifat mutasi alami. Analogi disini adalah lebih jelas, dimana setiap solusi yang mungkin pada masalah optimisasi kombinatorial adalah ekuivalen dengan string DNA dan setiap string tersebut diberikan nilai. Kemudian seseorang memilih untuk membentuk gene-


21 rasi yang akan datang dari populasi dengan sifat-sifat yang baik. Kemungkinan bahwa dua individu (orang tua) kawin tergantung pada nilai objektif mereka dan perkawinan dari dua individu menciptakan solusi baru yang sifat-sifatnya adalah kombinasi dari sifat dari setiap orang tua. Meskipun demikian, keturunan juga dapat mengandung sebuah mutasi-yakni, sifat yang tidak dimiliki oleh setiap orang tua. Seseorang kurang memungkinkan menghasilkan solusi lokal yang sama karena proses pemaduan tidak terpusat seluruhnya pada solusi terbaru yang terbaik.Akhirnya, jaringan neural didasarkan pada model-model fungsi otak. Algoritma jaringan neural artifisial harus, sebagai tujuan esensialnya, mengenal pola-pola dan mempelajari respon yang baik pada pola tertentu. Pada dasarnya, jaringan neural terdiri dari serangkaian nodes (neuron) yang mampu menerima informasi dari nodes yang berdekatan dan kemudian merespon yang berdekatan tersebut. Karena setiap nodes ini memproses informasi yang diterimanya secara serentak, maka dikatakan bahwa nodes ini berfungsi sebagai prosesor informasi paralel. Pada akhirnya, Jaringan-jaringan neural belajar mengidentifikasikan sifat-sifat yang baik dan buruk. Banyak pendekatan alternatif untuk penentuan strategi pembelajaran-ada peta pengorganisasian diri, jaringan-jaringan elastis, algoritma yang menyebar kebelakang, algoritma feed-forward, dan sebagainya. Juga, Program linear dan algoritma penurunan paling curam digunakan untuk membantu melatih nodes dalam jaringan secara lebih cepat. Pada waktu sekarang ini, jaringan-jaringan neural tidak diperlihatkan menjadi kompeitif dengan heuristik lainnya. Meskipun demikian, evolusi yang cepat dari teknologi jaringn neural dapat membuat algoritma ini efektif dimasa yang akan data. Glover dan Laguna (1992) telah mengeneralisasikan banyak sifat dari metodemetode ini ke dalam sebuah metode yang disebut tabu-search. Tabu-search adalah


22 meta-heuristik yang mengklasifikasikan atribut yang diinginkan seseorang dalam sebuah algoritma. Untuk menghindari kembali pada solusi lokal yang diketahui terlalu sering, algoritma membuat daftar gerakan terbaru dan membuat gerakangerakan tersebut dilarang selama periode waktu tertentu. Selanjutnya pada setiap langkah, algoritma harus memilih gerakan yang memberikan solusi jika tidak ada perbaikan gerakan yang memungkinkan.

Konsep-konsep lain yang diba-

ngun ke dalam tabu-search, meliputi diversifikasi (sama dengan mutasi, gerakan ini memaksa algoritma ke dalam bagian-bagian yang berbeda dari daerah yang memungkinkan), memori jangka panjang (pemberian label pada gerakan-gerakan sehingga seseorang mencegah terjadi- nya pengulangan seri gerakan yang sama) dan aturan-atuan aspirasi (yang menentukan kapan seseorang dapat mengabaikan kriteria tabu karena, misalnya, solusi yang dihasilkan diharuskan lebih baik dari pada solusi apapun yang terlihat sejauh ini). Pengacakan algoritma termasuk pengacakan aturan-aturan tabu itu sendiri-digabungkan dengan mudah ke dalam kerangka ini, adalah pemasukan subalgoritma yang sangat baik. Sebuah pendekatan untuk memperoleh solusi yang baik dari masalah optimisasi kombinatorial yang sering digunakan untuk masalah-masalah penjadwalan yang sulit-telah terbentuk dalam komunitas ilmu komputer. Program pembatasan adalah bahasa yang dibangun sekitar tiga konsep pencarian dan implikasi logika. Berbagai alat diberikan untuk memungkinkan pemakai menentukan urutan variabelvariabel diberikan nilai khusus dan urutan variabel-variabel tersebut ditentukan. Apabila mempertimbangkan pendekatan-pendekatan yang tepat untuk penyelesaian umum masalah program integer campuran, seseorang ingin memiliki heuris-


23 tik yang menggunakan pendekatan-pendekatan yang digunakan untuk bagianbagian lain dari algoritma. Selanjutnya, heuristik dapat mengeksploitasi beberapa atau semua informasi yang diperoleh pada relaksasi program linear dari masalah secara lebih luas. Seseorang dapat melihat cara mengambil banyak konsep yang telah dijelaskan diatas, dan menggunakannya pada heuristik tersebut. Pendekatan yang paling sederhana adalah mempertimbangkan dive dan fix heuraistic, dengan menetapkan beberapa himpunan bagian dari variabel-variabel bilangan bulat untuk nilai bilangan bulat tetap, melaksanakan semua penentuan dan pemrosesan awal yang telah diimplikasikan, dan sekali lagi menyelesaikan soal program linear yang dihasilkan. Proses itu terus berlanjut hingga program linear kembali dengan solusi bilangan bulat yang mungkin (dianggap sebuah keberhasilan ) atau berhenti karena tidak ada solusi yang mungkin untuk relaksasi program linear terbaru. Jika yang terakhir ini terjadi, seseorang dapat menghentikan algoritma dan berharap menemukan sebuah solusi pada beberapa iterasi lain, atau seseorang dapat menelusuri kembali (tidak menetapkan variabel-variabel tetap teraru dan menetapkannya pada batas lain). Demikian juga, begitu subbagian kecil dari variabel-variabel masih tidak tetap, seseorang dapat menyebutkan satu demi satu subbagian tersebut sehingga lebih memungkinkan menemukan solusi yang mungkin.

3.4 Heuristik Enumerasi Parsial Objektif Ganda Suatu heuristik enumerasi parsial untuk masalah penjadwalan Flowshop objektif ganda dengan n pekerjaan tersedia untuk pemrosesan pada waktu t = 0 dan dibutuhkan operasi tunggal pada tiap m order dan tersedia mesin terus-menerus.


24 Tiap pekerjaan i dihubungkan dengan waktu pemrosesan mesin, pij , pada tiap mesin j dan tanggal seharusnya di . Urutan pemrosesan pekerjaan adalah sama untuk semua mesin. Untuk jadwal biasa, misalnya ci merupakan waktu penyelesaian dari pekerjaan i, dan Ti = max{ci − d, 0} kelambanan dari pekerjaan i. Kriteria meminimisasi dari bagian makespan, cmax = max{ci }, maksimum kelamP P banan, Tmax = max{Ti }, total kelambanan T = i Ti dan flowtime F i = i Ci . Definisi diberikan sebuah fungsi vektor dari r komponen f = (f1, . . . , fr ) terdefinisi pada himpunan bagian Ω, ditetapkan problem optimisasi objektif ganda. Minimisasi fungsi tujuan f (x) = (f1 (x) = z1 , . . . , fr (x) = zr ), x ∈ Ω. Sebuah titik z mempengaruhi z jika zj = fj (x) ≤ z j = fj (x), ∀ j dan zj < z j untuk paling sedikit satu j. Sebuah solusi x∗ ∈ Ω adalah optimal Pareto (atau efisien) jika disana tidak ada x ∈ Ω sedemikian sehingga z = f(x) mempengaruhi z ∗ = f (x∗ ). Pengajuan heuristik enumerasi parsial objektif ganda (MOPE) untuk problem flowshop adalah dasar penggunaan konsep tentang langkah penempatan pekerjaan dari pengaruh Pareto ketika perbandingan parsial jadwal yang lengkap. Heuristik memiliki r tahap yang berbeda dengan urutan awal yang terikat pada vektor dari fungsi f = (f1, . . . , fr ) menjadi minimisasi. Dalam setiap tahap, digunakan urutan yang sesuai untuk meminimisasi setiap fungsi fi , i = 1, . . . , r. Pada akhir tahap r, diperoleh r himpunan solusi nondominsasi dan dari gabungan seperti menentukan himpunan ND dari solusi nondominasi, dimana terdapat perkiraan oleh himpunan Pareto optimal:

1. untuk l = 1 ke r lakukan a. Order pekerjaan sesuai dengan aturan pengiriman dan menghasilkan


25 urutan sl1 = (j1 , j2, . . . , jn ). b. Himpunan sl1 = (j1 ). sl1 = {sl1} : Himpunan dari urutan parsial bersama satu pekerjaan. Untuk k = 1 ke n lakukan 2. Untuk setiap urutan sl ∈ sk−1l lakukan a. Untuk i = 1 ke k lakukan Sisipkan pekerjaan ke-i dari slj urutan pembangkit slj dengan k pekerjaan. Hitung f(sli ) = (f1(sl1 ), . . . , fr (sli )) b. Susun himpunan slk oleh urutan tidak menguasai dari urutan pembangkit parsial k. |slk−1 | generated partial sequences. 3. Tahap terakhir l. Himpunan sln berisi urutan lengkap tidak menguasai 4. Bentuk himpunan ∪ri=1 sin dan membentuk himpunan ND dari solusi tidak menguasai, suatu perkiraan dari himpunan Pareto optimal.

Berikutnya dijelaskan aturan-aturan pengiriman yang digunakan untuk mendapatkan urutan awal untuk meminimisasi kombinasi dari objektif nonnegatif berikut: (Cmax , Tmax), (Cmax , T ), (Cmax, F ) dan (Cmax , Tmax, F ): Longest processing time (LTP): Pekerjaan disusun dalam order menurun dari total P waktu pengolahan pada mesin, j pij . Shortest processing time (SPT) : Pekerjaan disusun dalam order meningkat dari P total waktu pengolahan pada mesin, j pij . Tardiness lower bound (TLB) : Pekerjaan disusun dalam order menurun dari batas P bawah kelambanan dari pekerjaan i, di − j pij .


26 Dapat juga dihubungkan dengan aturan-aturan penyelesaian minimisasi kelambanan dengan cepat, mengubah tanggal pasti (modified due date) dan tanggal pasti paling cepat (earliest due dat). Bagaimanapun, akan dicapai hasil terbaik dengan aturan TLB. Ada beberapa aturan pengiriman untuk penjadwalan toko (shop scheduling) dan tidak mengklaim bahwa aturan yang digunakan ini paling baik. Penggabungan dua atau lebih aturan bisa menghasilkan hasil terbaik. Tujuannya adalah menunjukkan bahwa menggunakan aturan yang sesuai dianggap susunan suatu enumerasi dan menggunakan konsep Pareto dengan menuju penguasaan yang baik. Dalam kasus ini, bilangan dari nilai evaluasi adalah −1 + n(n + 1)/2. Dalam MOPE heuristik, semua pemecahan nondominan parsial diperluas pada level k yang diberikan. Itu mungkin untuk urutan awal yang diberikan, heuristic memiliki kasus terburuk 2! + 3! + · · · + n! urutan nilai, yang diberikan naik pada waktu eksponensial kompleksitas. Percobaban penghitungan menunjukkan bahwa untuk menguji contoh bilangan disini dengan urutan pembangkit memiliki kompleksitas O(n2 ) dan O(n3 ) untuk dua atau tiga objektif berturut-turut.

3.5 Algoritma Exact Penjadwalan dan perencanaan berperan penting untuk menyelesaikan proyek tepat waktu dan yang anggaran. The critical path method (CPM) digunakan untuk perencanaan dan mengontrol jadwal proyek. Dasar teori CPM menganggap sumber daya tak terbatas untuk sebuah proyek. Anggapan tidak valid dalam keadaan praktis , dalam hal ini banyak batas dari sumber daya yang tersedia, terutama bila sumber daya dibagi dengan berbagai kegiatan atau beberapa proyek


27 normal. Kekurangan ini berakibat penjadwalan CPM tidak realistis dalam praktek, terutama ketika CPM tak layak digunakan. Di atas kekurangan, teknik alokasi sumber daya di atas memiliki kemajuan dari metode CPM yang asli. Tujuan algoritma ini menentukan durasi terpendek jadwal CPM dibawah pembatas sumber daya yang diberikan. Metode heuristik bermaksud meniru bagaimana pembuat jadwal membuat keputusan pada situasi kegiatan akan dipilih untuk alokasi sumberdaya terbatas ketika permintaan melebihi persediaan. Kadang-kadang menentukan solusi optimal, tetapi lebih sering solusi dalam baik atau diterima. Keuntungan utama dari aturan-aturan heuristik adalah karena suatu solusi yang cocok dapat diperoleh tanpa membutuhkan algoritma dan penghitungan yang kompleks. Bagaimanapun, pilihan aturan heuristik bisa menjadi rumit karena set yang berbeda dari aturan yang boleh berlaku pada situasi yang berbeda. Dalam hal ini tidak ada set bersama dari aturan-aturan yang sesuai untuk keperluan proyek yang berbeda dan selalu menuju solusi yang baik. Dalam prakteknya, seorang pembuat jadwal harus menyesuaikan aturan atau percobaan lengkap meskipun set berbeda dari aturan-aturan hingga diperoleh solusi yang memuaskan. Yang lain, mencoba pendekatan penyelesaian yang tepat untuk menentukan solusi optimal (misalnya durasi terpendek) dari masalah penjadwalan dengan pemecahan sebuah model matematika. Metode program integer, terutama metode 0-1, pada percobaan awal tidak berhasil karena sifat kombinatorial dari masalah yang memiliki ukuran sangat terbatas (Paterson ,1984). Enumerasi branch and bound berkembang dengan enumerasi parsial sesuai penyelesaian masalah penjadwalan (Dorndorf dkk.(2000). Pencarian branching baru pada tinggkat solusi


28 yang mungkin dan bounding menghapus solusi yang terburuk. Patterson ( 1984) mengumpulkan 110 ciri-ciri khas jaringan penjadwalan dan digunakan untuk menguji kinerja dari tiga prosedur populer branch and bound. Teknik heuristik digunakan secara luas untuk perencanaan proyek dan penjadwalan dalam pendirian industri , tetapi tidak ada laporan pada beberapa pendekatan exact. Suatu algoritma exact disebut enumerasi branch and cut algoritma (EBAC) untuk penjadwalan pendirian proyek. Algoritma excat dengan durasi terpendek dijamin pengunaannya untuk beberapa proyek yang mempunyai sumberdaya terbatas. Model dasar itu dapat digabungkan bersama beberapa penyusunan penjadwalan, misalnya perencanaan proyek primavera, untuk penyelesaian dan optimisasi sesuai masalah penjadwalan.

3.6 Enumerasi Branch dan-Cut Algoritma Prinsip dasar dari algoritma EBAC terletak dalam penyusunan suatu pohon enumerasi. Selama penyusunan pohon, alternatif baru yang mungkin ditambah cabang tetapi alternatif yang lebih buruk dihapus, oleh karena itu, cabang baru menggambarkan perhitungan alternatif yang mungkin terbaik. Suatu pohon enumerasi terdiri dari banyak nodes (daun). Node pertama adalah akar dari pohon. Percabangan awal adalah cabang keluar dari akar menyerupai alternatif awal yang mungkin dari masalah jadwal dan setiap panah menjelaskan satu alternatf awal. Node terakhir dari sebuah panah menjelaskan tahap keputusan baru yang bisa dibentuk cabang baru. Kemudian disana alternastif bisa lebih dari satu, lebih dari satu pencabangan bisa dicabangkan keluar dari beberapa node i. Oleh karena itu, node i ( atau orang tua) bisa terdiri lebih dari satu nodes pengganti (atau anak),


29 tetapi node seorang anak hanya dapat memiliki satu node lebih tinggi (atau orang tua) karena setiap node anak adalah dicabangkan keluar dari satu lebih tinggi dari node dekat. Dari beberapa node dalam pohon, disana sebuah path unik yang terhubung node ini pada akar node. Path diletakkan sebuah jadwal parsial pada waktu dipakai pada node ini. Sebuah jadwal parsial termasuk kegiatan terakhir, pada kegiatan keberangkatan, jadwal kegiatan adil, kegiatan tidak terjadwal. Jika pohon mempunyai jangkauan menggali keputusan (misalnya kegiatan terminal), waktu terakhir adalah waktu terakhir proyek. Jumlah path yang berisi kegiatan menjelaskan jumlah total dari final alternatif jadwal yang mungkin dari proyek.

3.7 Dasar Heuristik pada Enumerasi Parsial Mokotof dan Jimeno ( 2002) Masalah klasik pemrosesan penjadwalan yang tidak berhubungan paralel dengan n jobs independent dan non-preemtive dan m prosesor tidak berelasi. Semua pekerjaan harus diproses. Sebuah pekerjaan bisa diproses pada satu dari m prosesor tetapi waktu proses terikat pada prosesor dimana pekerjaan itu dikerjakan. Masalah penemuan jadwal mimisasi waktu maksimum penyelesaian pekerjaan betul-betul dipertimbangkan. Mengikuti standar tiga-klasifikasi dijelaskan oleh Graham dkk.( 1979), masalah dinotasikan dengan R/Cmax , pertama menetapkan keadaan lingkungan sekitar prosesor; kedua karakteristik pekerjaan-pekerjaan; dan ketiga menunjukkan pilihan kriteria dengan optimal. Jadi, R berarti prosesor tidak berelasi, pekerjaan-pekerjaan tidak dianggap menjadi pembatas dan fungsi objekif adalah untuk menghasilkan sebuah penjadwalan dengan panjang minimum.


30 Untuk menentukan masalah-masalah nyata yang dapat dimodelkan oleh R//Cmax . Contoh, pada pembuatan garis-garis biasanya lebih dari satu prosesor yang dapat dibawa keluar pembuat tugas-tugas, sistem galangan kapal untuk kapal-kapal, bagian-sistem waktu dan komputer multi prosesor dll. Diberikan formulasi sesuai dengan program linear integer campuran (MILP) bersama keputusan variabel-variabel biner, diusulksan beberapa dasar algoritma baru heuristik pada enumerasi parsial. Dimulai bersama solusi relaksasi program linear, pendekatan ini dicoba untuk menentukan solusi optimum.

Definisi Masalah dan Hasil-Hasil Sebelumnya

3.7.1 Notasi Notasi yang akan digunakan sebagai berikut: Ji : pekerjaan i, i ∈ N = {1, . . . , n} Pj : prosesor j, j ∈ P = {1, . . . , m} pij : waktu pemrosesan pekerjaan Ji ketika diproses oleh prosesor pij Ci : waktu penyelesaian pekerjaan j − i, Cmax : maksimum waktu penyelesaian semua pekerjaan Ji Cmax = max{C1 , . . . , Cn } xij : variabel penugasan


31 3.7.2 Masalah R//Cmax Dipertimbangkan sebuah himpunan n independen dan pekerjaan non-preemtive ji , i = 1, 2, . . . , m untuk diproses pada m prosesor tidak berelasi Pj , j = 1, 2, . . . , m. Setiap pekerjaan bisa dibawa keluar oleh beberapa m prosesor tetapi berhubungan dengan waktu pemrosesan pij dan pekerjaan Ji terikat pada prosesor yang sedang membawa keluar pekerjaan. Tujuan (objektif) adalah menentukan suatu tempat yang tepat untuk pekerjaanpekerjaan J , pada prosesor dari himpunan P , kegunaan kriteria yang optimisasi. Kriteria dalam minimisasi waktu penyelasaian maksimum, disebut makespan. Misalnya xij ada 0/1 variabel penugasan, sama dengan 1 (berturut-turut 0) jika pekerjaan Ji ditetapkan (ditetapkan tidak berturut-turut) pada prosesor Pj . Formulasi masalah MILP sebagai berikut: min y kendala m X

xij = 1,

1 ≤ i ≤ n (3.7.2.1)

j=1

y−

m X

pij xij = 1 ≥ 0,

1 ≤ i ≤ m (3.7.2.2)

j=1

x ∈ {0, 1}n×m y ∈ R+ Pembatasan dalam (3.7.2.1 ) dihubungkan dengan pekerjaan Ji dengan sederhana berarti bahwa Ji harus lengkap. Pembatasan dalam (3.7.2.2) dihubungkan dengan prosesor Pj berarti makespan sekurang-kurangnya menetapkan muatan pada Pj . Formulasi ini memiliki m + n pembatas dan mn + 1 variabel. Ke-


32 mudian nilai yang sesuai x0ij dari variabel yang diberikan, nilai minimum dari Pn y maxj∈{1,...,m} i=1 pij x0ij variabel y tidak dibatasi pada suatu integer. Cukup untuk mengetahui tepat penugasan optimum, karena Cmax akan sama untuk beberapa pengurutan pekerjaaan yang ditetapkan pada prosesor, kecuali bila waktu tidak bekerja.

3.7.3 NP-hardness dan State of the art Masalah R//Cmax diketahui pada NP-lengkap sejak mengubah partisi polynomial pada kasus khusus P 2//Cmax dimana pij = pi dan m = 2. Selain itu Lenstra dkk.(1990), membuktikan bahwa jika P = N P , algoritma pendekatan tidak polynomial dengan perbandingan lebih dari 3/2 didapat untuk masalah R//Cmax . Hanya sedikit masalah penjadwalan ditunjukkan dapat diselesaikan pada polynomial. Dua seperti baik-diketahui masalah P/pmtn/Cmax dimana tugasP tugas bisa dimiliki lebih dahulu (preempted), dan P// ni=1 Ci , dimana jumlah waktu penyelesaian dari semua tugas-tugas menjadi minimisasi. Untuk masalahmasalah yang sukar, penelitian fokus untuk memperoleh solusi optimum dengan metode enumerasi atau pada pengembangan pendekatan algoritma. Sebagian besar masalah-masalah penjadwalan dengan prosesor tidak-sama (non-identical) adalah juga NP-sukar (NP-hard). Banyak paper yang berhubungan dengan masalah sejenisnya, bisa disebut mengikuti referensi mengenai minimisasi dari makespan.


33 3.8 Branch and Bound Membahas masalah n buah pekerjaan diproses dengan menggunakan m mesin tak berelasi. Setelah sekumpulan pekerjaan diserahkan pada mesin, pencarian urutan pekerjaan tidak diperlukan lagi dalam mesin tersebut, karena yang menjadi tujuan utama adalah untuk meminimisasi Cmax (Cmax adalah waktu maksimum yang dibutuhkan untuk melakukan suatu proses kerja) dan tidak tergantung dengan waktu pengurutan. Oleh karena itu, algoritma branch and bound dikembangkan untuk menentukan penyerahan pekerjaan secara optimal kepada mesin. Branch and Bound adalah suatu prosedur yang paling umum untuk mencari solusi optimal pada masalah optimisasi kombinatorial seperti penjadwalan. Di dalam algoritma Branch and Bound, terdapat tiga buah bagian utama yaitu ekspresi batas bawah (Lower Bound (LB)), strategi pencarian dan pencabangan (Branching). Di dalam prosedur ini, suatu masalah dipecah menjadi beberapa submasalah yang merepresentasikan pembagian kerja secara parsial. Simpulsimpul terus bercabang lebih jauh sampai diperoleh solusi lengkap. Jika LB tidak digunakan, maka segala kemungkinan penyelesaian harus dienumerasikan satu per satu. Oleh karena itu, LB dikalkulasikan pada setiap simpul. Jika nilai LB yang dikalkulasikan lebih besar dari nilai solusi lengkap terbaik, eliminasi simpul tersebut. Prosedur ini terus diulang sampai pencarian pada pohon berakhir dan solusi optimal ditemukan.


34 3.8.1 Strategi Pencabangan (Branching) Pencarian dimulai dengan jadwal kosong Q0, tidak ada pekerjaan yang harus dilakukan. Untuk masalah dengan n buah pekerjaan (j1 , j2 , . . . , jn ) dan m buah mesin (k1 , k2 , . . . , km ), diperoleh suatu urutan [k1 , k1 , k2 , k1 , . . . , kk ], yang berarti pekerjaan (j1 , j2 , j4 ) dilakukan oleh mesin k1 , pekerjaan j3 dikerjakan oleh mesin k2 , dan pekerjaan jn dikerjakan oleh mesin kk . Pada tingkat (aras) pertama dari pohon dibuat mn buah cabang. Pada tingkat L dari pohon ini, setiap simpul mengandung L buah pekerjaan, dan dapat bercabang menjadi m(n − L) buah simpul. Saat tingkat terakhir dicapai, jumlah cabang yang diperoleh adalah nol karena n = L. Jika prosedur ini dilakukan sepenuhnya, n! buah simpul akan dihasilkan pada pohon tingkat n. Jika pada kenyataannya hal ini yang terjadi, berarti enumerasi total telah dilakukan. Oleh karena itu, prosedur pembatas (bounding procedure) dibutuhkan untuk mengurangi jumlah simpul yang ada didalam pohon.

3.8.2 Batas Bawah (Lower Bounds) LB yang digunakan dalam algoritma branch and bound ini ditentukan oleh: 1 X min(Pjk ), k = 1, . . . , m m j=1 n

LB =

(3.1)

Untuk pembuktian yang lebih sederhana, pembuktian yang dituliskan di bawah ini tidak menyinggung kelayakan mesin. Akan tetapi pembuktian ini tidak tetap berlaku jika kelayakan mesin diperhitungkan. Asumsikan, tanpa kehilangan hal yang sudah umum, bahwa tidak ada pekerjaan yang sudah dijadwalkan, waktu


35 penyelesaian untuk pekerjaan terakhir pada mesin k diberikan oleh: Ck =

Nk X

Pjk ,1,k

(3.2)

i=1

Nk adalah jumlah pekerjaan yang dijadwalkan pada mesin k, Pjk adalah waktu pemrosesan pekerjaan j pada mesin k dan jk,j adalah pekerjaan ke i yang dijadwalkan pada mesin k. Untuk total m buah mesin, fungsi ini ditujukan untuk meminimalisasi Cmax , seperti yang didefinisikan pada: Cmax = max{C1, . . . , Cm }

(3.3)

Jika vektor c ∈ Rm didefinisikan dengan komponen Ck maka fungsi ini dapat dituliskan sebagai: Cmax = kCk∞


(3.4)

BAB 4 ENUMERASI PARSIAL UNTUK PENJADWALAN PREEMPTIVE PADA PROSESOR PARALEL TIDAK BERELASI

Masalah yang ingin dibahas dalam tesis ini adalah penemuan jadwal preemptive optimal untuk pekerjaan-pekerjaan independen pada prosesor paralel tidak berelasi. Ditunjukkan bahwa masalah-masalah penjadwalan tertentu dari jenis ini, misalnya minimisasi makespan, dapat dirumuskan dan diselesaikan sebagaimana masalah-masalah program linear. Juga ditunjukkan bahwa formulasi program linear menghasilkan cara untuk membuktikan batas atas (upper bound) bilangan dari preemption yang diperlukan untuk sebuah jadwal optimal. Sebagaimana perumusan umum masalah, bahwa ada m prosesor, indeks i = 1, 2, . . . , m dan n pekerjaan, indeks j = 1, 2, . . . , n. Sebuah prosesor dapat bekerja hanya untuk satu pekerjaan pada suatu saat, dan sebuah pekerjaan dapat dikerjakan oleh hanya satu prosesor pada suatu saat. Pengolahan sebuah pekerjaan bisa dihentikan pada suatu waktu dan mulai lagi pada waktu kemudian, oleh prosesor yang sama atau sebuah prosesor berbeda. Tidak ada nilai dan kerugian waktu jika dihubungkan dengan suatu interupsi atau preemption. Dianggap bahwa data yang dimasukkan untuk sebuah contoh masalah termasuk mn bilangan positif pij , dimana pij menjelaskan total waktu pengolahan yang diperlukan untuk pekerjaan j lengkap, jika pekerjaan hanya dikerjakan oleh prosesor i. Biasanya, jika prosesor i bekerja pada pekerjaan j dengan total waktu tij , maka yang diperlukan adalah: m X tij =1 p i=1 ij


37 di dalam order pekerjaan menjadi lengkap. Dianggap tidak ada relasi khusus antara nilai-nilai pij . Sehingga, prosesorprosesor tidak berelasi. Ini membedakan untuk lebih dua kasus spesial, sebagai berikut. Jika, untuk semua i, j, k, pij = pkj maka prosesor adalah sama. Jika setiap pij dapat dinyatakan dalam bentuk pij = qi pj dimana qi (sebuah faktor kelambanan) dan pj adalah parameter yang dihubungkan dengan mesin i dan pekerjaan j, maka mesin-mesin disebut sama. Diberikan suatu jadwal yang mungkin, titik akhir waktu pekerjaan j diproses menghasilkan waktu Cj . Banyak masalah penting dipertimbangkan bahwa penemuan suatu jadwal yang mungkin untuk makespan atau menghasilkan waktu maksimum, Cmax = max{Cj } j

adalah minimisasi. Ditunjukkan bahwa ada sebuah batas polynomial yang diturunkan dari masalah ke masalah program linear. Secara khusus, akan dirumuskan masalah program linear dengan mn+1 variabel dan 2n+m pembatas (persamaan dan pertidaksamaan). Maka akan ditunjukkan bahwa satu dapat menghasilkan suatu jadwal optimal (melalui teori ruang terbuka) dari sebuah solusi optimal untuk masalah program linear. Dari sebuah produk analisa dibuktikan bahwa ada jadwal optimal Cmax dengan preemptive tidak lebih dari O(m2 ). Hasil-hasil ini adalah perbedaan situasi untuk prosesor-prosesor yang sama. Untuk prosesor-prosesor yang sama, sebuah algoritma sederhana O(n), menghasilkan jadwal optimal Cmax dengan tidak lebih dari preemtion m − 1. Lebih lanjut sebuah algoritma kompleks O(n + m log m) untuk kasus dari prosesorprosesor yang sama dan ditunjukkan bahwa tidak lebih dari 2(m − 1) preemption


38 diperlukan untuk suatu solusi optimum. Tidak dikenal algoritma polynomial-terbatas untuk masalah program linear yang umum, maupun masalah yang ditunjukkan oleh NP-complete. Diikuti oleh penyelesaian oleh masalah Cmax untuk prosesor-prosesor tidak berelasi tidak menyelesaikan masalah dari suatu masalah juga NP-complete atau batas polynomial. Bagaimanapun akan ditunjukkan bahwa untuk bilangan tetap dari m prosesor ada sebuah algoritma polynomial-terbatas. Dipertimbangkan perluasan metode program linear untuk solusi fungsi objektif lebih umum dari Cmax . Terutama dipertimbangkan masalah minimisasi: Lmax = max{Lj } j

dimana Lj = Cj − dj . Berarti menunjukkan kelambanan dari pekerjaan j dengan respek pada tanggal seharusnya dj yang diberikan. Batas atas dihasilkan bilangan dari preemption yang diperlukan untuk jadwal optimum.

4.1 Formulasi Program Linear dari Masalah Cmax Andaikan semua pekerjaan tersedia untuk diproses pada waktu t = 0. Dipertimbangkan beberapa jadwal yang mungkin dari pekerjaan n pada m prosesor tidak berelasi , yang berkenaan dengan jadwal ini. tij = total jumlah waktu prosesor bekerja pada pekerjaan j


39 Jelas bahwa nilai dari Cmax dan tij untuk solusi yang mungkin terdapat jadwal pada masalah program linear: Minimisasi

Cmax

Kendala m P

tij pij

i=1 n P i=1 m P

= 1,

j = 1, 2, . . . , m

(4.1)

tij ≤ Cmax ,

j = 1, 2, . . . , n

(4.2)

tij ≤ Cmax,

j = 1, 2, . . . , m

(4.3)

i=1

tij ≥ 0

Dinyatakan bahwa kebalikannya juga benar. Bahwa untuk beberapa solusi yang mungkin pada masalah program linear, ada sebuah jadwal yang mungkin untuk nilai-nilai yang sama dari tij dan Cmax.

4.2 Membentuk Solusi yang Mungkin Andaikan diberikan matriks non negatif T = (tij ) berordo m × n dan nilai Cmax , dimana

(

Cmax = max max i

(

X j

tij

) ( ,

X

tij

))

(4.4)

i

Ditunjukkan bahwa itu mungkin untuk membentuk jadwal yang mungkin dengan memberikan nilai Cmax. Berhubungan dengan anggapan sebagai berikut. Prosesor i bekerja pada pekerjaan j untuk total jumlah waktu ij . Sebuah prosesor bekerja hanya untuk satu pekerjaan pada suatu saat dan sebuah pekerjaan dapat dikerjakan oleh hanya satu prosesor pada suatu saat. Tidak ada pembatasan order pekerjaan yang diberikan dapat dikerjakan oleh prosesor yang berbeda, atau


40 pada order prosesor yang diberikan dapat bekerja pada pekerjaan-pekerjaan. (sebab itu bentuk ”ruang terbuka”). Tidak ada nilai pada saat waktu interupsi atau preemption dari pekerjaan-pekerjaan. Semua pekerjaan tersedia untuk diproses pada waktu t = 0. Misalkan baris i (kolom j) ketat (tight) dari matriks T , jika P P j tij = Cmax ( i tij = Cmax ) selain itu diperlonggar (slack). Andaikan dapat ditemukan himpunan bagian dari elemen-elemen positif dengan ketat (strictly) dari T , dengan tepat satu elemen dari himpunan bagian dalam setiap baris dan kolom yang ketat dan tidak lebih dari satu elemen dalam beberapa baris slack atau kolom slack. Himpunan bagian (subset) dari elemen-elemen himpunan pengurang (decrementing set) dan digunakan untuk membentuk sebuah jadwal parsial dengan lamanya δ, untuk beberapa pilihan yang sesuai δ > 0. Dalam jadwal bagian ini prosesor i bekerja pada pekerjaan j untuk min{tij , δ} unit waktu, untuk setiap elemen tij dalam pengurangan himpunan. Penempatan kembali tij oleh max{0, tij − δ} untuk setiap elemen dalam pengurangan himpunan, dengan cara 0 − δ. itu diperoleh sebuah matriks T 0 yang baru, untuk Cmax = Cmax

Contoh, andaikan Cmax = 11 dan  T =



 3 4 0 4  11    4 0 6 0  10     4 0 0 6 10 11 4 6 10

Dengan jumlah baris dan kolom menunjukkan batas dari matriks. Pengurangan himpunan yang mungkin ditunjukkan oleh elemen-elemen yang dilingkari. 0 = 7 dan matriks T 0 dibawah ini, jadwal parsial Misalkan δ = 4, maka Cmax

ditunjukkan disebelah kanan:


41

Pengurangan himpunan dari T 0 ditunjukkan oleh elemen yang dilingkari. Ada bermacam-macam pembatas yang harus dipenuhi oleh δ dalam order 0 −δ. Jika tij adalah elemen dari pengurangan himpunan dalam untuk Cmax = Cmax

baris ketat atau kolom ketat , dengan jelas yang diperlukan δ ≤ tij , yang lain ada jumlah baris atau kolom T 0 dengan ketat dimana lebih besar dari. Demikian pula, jika elemen dari pengurangan himpunan dalam baris slack (kolom slack), maka ! X X δ ≤ tij + Cmax − tik tkj δ ≤ tij + Cmax − k

k

Dan jika baris (kolom j) tidak mempunyai elemen dari himpunan pengurangan (dan oleh karena itu diperlukan slack), maka δ ≤ Cmax −

X

tij

δ ≤ Cmax −

X

j

tij

!

i

Jadi untuk contoh diatas diperoleh

δ ≤ t34 + Cmax −

X

t3k

δ ≤ t12 = 4 δ ≤ t21 = 4, X = 7, δ ≤ t34 + Cmax − t34 = 7

k

k

δ ≤ Cmax −

X

tk3 = 5

k

Andaikan terpilih δ kendala menjadi maksimum dengan kondisi yang ditunjukkan diatas. Maka tiap T 0 akan memuat paling sedikit satu kurang dari elemen positif yang ketat dari T atau yang lain T 0 akan memuat paling kecil satu lebih besar


42 dari kolom ketat atau baris ketat dari T . Jadi tidak lebih dari r + m + n iterasi, dimana r adalah elemen positif dengan ketat dalam T , perlu membentuk jadwal yang mungkin dengan panjang Cmax . Sebagai ilustasi, selanjutnya dengan contoh. Misalkan δ = 3 didapat dari T 0 matriks T 00, dengan menunjukkan perbanyakan jadwal parsial ke kanan

(simbol φ waktu diam). Hasil terakhir pengurangan himpunan mengikuti jadwal lengkap: Untuk melengkapi pembuktian, perlu menggunakan lemma.

Lemma 1 Untuk beberapa matriks T tidak negatif dan Cmax keadaan memenuhi (4.2.1), disana ada himpunan pengurangan a yang tetap.

Bukti. Dari matriks T berordo m×n disusun matriks U berordo (m+n)×(m+n) sebagai berikut: U=

T Dm Dn T t

Di sini T 0 adalah transpose dari matriks T . Dm dan Dn berordo m × m dan n × n. Matriks diagonal dari slack tidak negetif, ditetapkan dalam suatu cara bahwa setiap jumlah baris dan jumlah kolom dari U adalah sama dengan Cmax. Berikutnya bahwa (1/Cmax )U adalah sebuah pasangan matriks stokastik.


Pasangan

43 matriks stokastik adalah kombinasi konveks dari matriks permutasi. Itu mudah disamakan bahwa ada satu dari matriks permutasi dalam kombinasi konveks adalah sama dengan himpunan pengurangan dari T . Ada beberapa cara yang mungkin untuk membentuk sebuah himpunan pengurangan. Bahwa satu dapat dibentuk matriks U dari T kemudian penyelesaian masalah penugasan tentang U , dapat dilakukan dalam waktu polynomial. Pengamatan ini, bersama-sama dengan pengamatan yang tidak lebih dari sebuah bilangan polynomial dari setiap masalah penugasan memerlukan penyelesaian, cukup untuk membentuk sebuah batas polynomial dari prosedur pembentukan jadwal.

4.3 Batas Bilangan Preemptions Untuk mencari sebuah batas atas dibutuhkan bilangan preemptions untuk sebuah jadwal optimal Cmax pada prosesor paralel yang tidak berelasi. Untuk lebih tepat dikatakan bahwa pekerjaan adalah preempted pada waktu t jika eksekusi dari pekerjaan ditunda pada sebuah prosesor pada waktu t sebelum prosesor menghasilkan. Jika prosesor mulai atau melanjutkan eksekusi dari sebuah pekerjaan pada waktu t0 dan prosesnya berlanjut sampai waktu t,ketika pekerjaan yang satu lengkap atau preempted, maka [t0, t] disebut periode aktif pekerjaan. Total bilangan preemptions dalam sebuah jadwal adalah sama untuk total bilangan dari periode aktif dalam jumlah melampaui batas dari n. Mempertimbangkan formulasi program linear pada bagian 2. Masalah ini mempunyai n persamaan yang terbatas (4.2.1), m pertidaksamaan yang terbatas (4.2.2) dan m petidaksamaan yang terbatas (4.2.3). Formula itu mengikuti teori


44 dasar program linear dimana ada sebuah penyelesaian dasar yang optimal dengan tidak lebih dari n+r2 +r3 variabel-variabel positif, dimana r2 dan r3 menunjukkan bilangan dari pembatas pertidaksamaan (4.2.2) dan (4.2.3) dengan persamaan yang ada. Jelas 0 ≤ r3 ≤ m. Jika n > m, 0 ≤ r2 ≤ m − 1. Dan jika n ≤ m, paling banyak berisi m − 1 (4.2.2) adalah tidak berlebihan. Kemudian ada penyelesaian optimal dengan paling banyak n+2m−1 variabel-variabel positif, satu diantaranya adalah Cmax. Jadi ada sebuah solusi yang optimal untuk masalah program linear dengan tidak lebih dari n + 2(m − 1) nilai tij yang positif. Jika kita dapat membentuk sebuah jadwal ( dengan memberi nilai dari Cmax ) dengan tepat satu periode aktif untuk setiap nilai positif tij , akan didapat batas atas dari 2(m − 1) pada bilangan preemptions yang diperlukan untuk jadwal optimal Cmax . Bagaimanapun, prosedur menyusun jadwal biasanya memperkenalkan penjumlahan preemptions. Diajukan sebuah variasi dari prosedur penyusunan jadwal, dengan tujuan dari penurunan bilangan preemptions dalam menghasilkan jadwal. Pertanyaannya apa yang dilakukan untuk menggantikan semua pekerjaan yang diwakili oleh sebuah nilai positif tij oleh m model pekerjaan. Untuk menjawab pertanyaan tersebut maka digunakan prosedur penyusunan jadwal untuk menemukan jadwal yang mungkin dengan model-model pekerjaan. Akhirnya akan terbentuk sebuah jadwal untuk himpunan bilangan asli dari perkejaan oleh periode aktif penugasan kembali untuk model-model pekerjaan dengan menempatkan kembali pekerjaan itu.


45 Contoh dari bagian sebelumnya dimana Cmax = 11 dan

Misalkan dihilangkan kolom-kolom yang memuat dengan tepat satu nilai poitif tij dan jumlah kolom kosong, untuk menghasilkan matriks T 0:

Indeks dari pekerjaan-pekerjaan dikenalkan dengan dua kolom pertama dari T 0 adalah 1 dan 4. Misalkan 1, 2, 3 untuk model pekerjaan. Diberikan nilai model pekerjaan tij kemudian semua baris dari T 0 adalah ketat. Aplikasi prosedur penyusunan jadwal pada T 0 seperti sebuah jadwal

Pengisian periode aktif untuk model pekerjaan dimana ditempatkan kembali, plus waktu tidak jalan menghasilkan jadwal yang sama sebagaimana hasil yang diperoleh dengan prosedur original.


46

Contoh, sebuah jadwal telah disusun dimana tidak ada preemptions dari model pekerjaan. Sebab itu kemungkinan membuat jadwal untuk himpunan original dari pekerjaan dimana tidak ada preeemptions dari beberapa pekerjaan ini yang ditempatkan kembali model pekerjaan. Pada umumnya bilangan preemptions diperlukan untuk himpunan original dari pekerjaan adalah batas dari bilangan preemptions dalam penyusunan jadwal untuk matriks T 0. Matriks T 0 mempunyai lebih dari m + r2 + r3 − 1 kolom dan lebih dari m + 2(r2 + r3 − 1) elemen positif yang ketat. Setiap pengulangan dari presedur penyusunan jadwal adalah penurunan sebuah elemen dari matriks T 0 ke nol atau karena penjumlahan kolom menjadi ketat. Dengan tepat n elemen menjadi nol pada pengurangan terakhir. Sebab itu ada lebih dari 2(r2 + r3 ) − 1 pengurangan dari jenis pertama. Ada m−r2 pengurangan dari jenis ke dua, dan sebab itu tidak lebih dari m + r2 + 2r3 − 1 pengurangan untuk semuanya. Setiap pengurangan lebih dari m periode aktif sampai menghasilkan jadwal, ada lebih dari m(m + r2 + 2r3 − 1) periode aktif untuk semuanya. Bilangan untuk periode aktif lebih dari m + r2 + r3 − 1 dan sebab itu bilangan dari preemptions, adalah batas dari m(m + r22r3 − 1) − (m + r2 + r3 − 1). Diambil r2 = m − 1, r3 = m, dengan mengikuti teorema. Teorema 1. Suatu batas atas pada bilangan preemptions dibutuhkan untuk jadwal optimal Cmax pada prosesor yang tidak berhubungan adalah 4m2 − 5m + 2.


47 Penunjukan batas oleh teorema pasti tidak ketat, seperti diketahui bahwa tidak lebih dari 2 preemptions diperlukan untuk kasus m = 2. Selain itu tidak dapat dibuat O(m2 ) preemptions tetapi boleh dibuat untuk jadwal optimal, atau lebih dari 2(m − 1) boleh diperlukan.


BAB 5 KESIMPULAN DAN SARAN

5.1 Kesimpulan Penyelesaian masalah penjadwalan preemptive pada prosesor paralel tidak berelasi untuk memperoleh jadwal optimal dapat menggunakan pendekatan enumerasi parsial yaitu dengan menetapkan waktu maksimum yang dibutuhkan prosesor paralel yang tidak berelasi untuk memproses suatu pekerjaan (Cmax) sebagai batas atas (upper bound) dari suatu program linear.

5.2 Saran Banyak masalah optimisassi kombinatorial yang dapat diselesaikan menggunakan enumerasi parsial belum dibahas dalam penelitian ini. Oleh karena itu disarankan dilakukan penelitian untuk pengembangan ilmu pengetahuan.


DAFTAR PUSTAKA Arroyo, J.E.C. and Armentano,V.A. 2004. A Partial Enumeration Heuristic for Multi Objective Flowshop Scheduling Problems Journal of the Operational Research Sociaty(2004)55,1000-1007. Universidade Campines, Campinas, Brazil. Baiou, M.2007. Polyhedral Approach to Solve Combinatorial Optimization Problems. Laboratoire LIMOS, Universete Clermont Dorndorf, U., Pesch, E., and Phan-Huy, T. 2000. A branch and bound Algorithm for the resource-constrained project scheduling problem. Math. Methods Oper. Res, 52, 413-439. Fisher,M.L.1981. The Lagrangian Method for Solving Interger programming Problem, Management Science, 27,1-18. Gabrielle,P., James B.Rawling and Stephen J.Wright.2007. Fast, Large Scale Model Predictive Control By Partial Enumeration, Department of Chemical Engeneering, Industrial Chemistry and Science of Material, Univ of Pisa, Via Diotisalvi, Italy. Genmou,J. and Jonathan,S. 2005. Exact Algarithm for Solving Project Scheduling Problems under Multiple Resource Constraints. Journal of construction Engineering and Management, ASCE. Glover, F., and M.Laguna.1992. Tabu search, a Chapter in Modern Heuristic Technique for Combinatorial Optimization. Gomory,R.E.1990. Outline of An Algorithm for Integer Solution to Linear Programming. Bulletin American Mathematical Sicoety, 64, 275-278. Karen , A., And Stan, V. Hoesel .1997.Polyhedral Techniques in Combinatorial Optimization I : Theory, Department of Computer Science, Utrech University P.O Box 80089,3508 TB Utrech the Netherlands. Karla, H., And Manfred.P. 2000. Combinatorial and Integer Optimization, George Mason University. Land, A.H., and Doig,A.G.1960. An Automatic Method for Solving Discrete programming problems. Econometrica, 28,97;520. Lawler, E.L., and Labetoull , J. 1978. On preemptive scheduling of unrelated parallel processors by linear programming, Journal of the ACM 25(1978) 612-618. Lenstra, J.K., Shmoys, D.B., and E.Tardos. 1990. Approximation algorithms scheduling unrelated parallel processor, Mathematical Programming 46, 259271. Lipo, W.,Sa LI, Fuyu ,T.and Xiuju Fu.2004. A Noisy Chaotic Neural Net work for Solving Combinatorial Optimization Problem : Stocastic Chaotic Simulated Annealing, IEEA TRANSACTION ON SYSTEM, MAH, AND CYBERNETIC-PART B; CYBERNETICS, VOL 34. 49 Raffles Nababan: Enumerasi Parsial Untuk Suatu Masalah Optimisasi kombinatorial, 2008. USU e-Repository © 2008

50 Mokotoff, E., and Jimeno, J.L.2002. Heuristic Based on Partial Enumeration for the Unrelated Parallel Processor Scheduling Problem. Annals of operations Research 117,133-150. Mayne, D.Q.; Rawling, J.B.; Rao, C.V., and Scokaert,P.O.M.2000. Constrai ned model predictiv control Stability and optimality Automatica.36(6). 789-814. Patterson, J.H.1984. A comparison of exact procedures for solving the multiple constrained resource project scheduling problem. Manage.Sci. 30(7), 854-867. Pedroso, J.P.2004. Hybrid Enumeration Partial Strategies for Mixed Integer Programming , DCC-FC & LIACC, Universidade do Porto, R. Do Campo Alegre 823, 4150-180 Porto, Portugal. Peiyi Tang, Markus P.Turkia.2005. Mining Frequent Item Sets With Partial Enumeration, Department of Computer science, University of Arkansas at Little. Weyl,H.1935. Elementari Theorie der Konvexen Polyheder, Comm.Math.Helv, 290 . Translated in Contributions to the Theory of Games,1,3,1950.


ENUMERASI PARSIAL UNTUK SUATU MASALAH OPTIMISASI KOMBINATORIAL

Recommend Documents