Heuristik untuk Masalah Urutan Optimal Komposisi Fungsi-Fungsi

MUHAMMAD IHSAN, Dr-Ing, MHD. Reza M.I. Pulungan, M.Sc.

2020 | Skripsi | S1 ILMU KOMPUTER

Berawal dari masalah penjadwalan bergantung pada waktu yang secara umum adalah permasalahn NP dan telah banyak penelitian dengan heuristik untuk pencarian nilai optimalnya. Terdapat penelitian oleh Kawase et al. (2016) bahwa masalah penjadwalan bergantung pada waktu dapat dibawa ke permasalahan urutan optimal komposisi fungsi-fungsi. Beberapa kelas fungsi dapat diselesaikan dalam waktu polinomial, salah satunya fungsi linear naik. Pada penelitian ini, dilakukan pendekatan heuristik untuk kelas fungsi linear naik dengan menambahkan sebuah fungsi monoton naik tak linear di mana kelas fungsi ini masuk pada permasalahan NP. Beberapa algoritma heuristik akan dilakukan, yaitu greedy, berbasis relasi urut, dan pemrograman dinamis. Dibandingkan nilai optimal yang didapatkan dari masing-masing algoritma dan running time. Didapat bahwa heuristik berbasis relasi urut adalah yang terbaik dengan 96.25% kasus uji mendapatkan nilai terbaik. Runnig time dari heuristik berbasis relasi urut juga yang terbaik dengan kompleksitas waktu O(n^2).

Time-dependent scheduling are generally NP problem. There are many research uses heuristic to find the optimal value. Kawase et al. (2016) stated in their research that time-dependent scheduling problems are related to optimal ordering of composition problems. Some classes of functions can be solved in polynomial time, such as class of increasing linear functions. In this research, a heuristic approach for the class of increasing linear functions is done by adding a nonlinear monotone increasing function, which is an NP problem. Some heuristic algorithms will be done, such as greedy algorithm, ordered relation-based algorithm, and dynamic programming. The optimal values from those algorithms and their running time are compared. It can be concluded that ordered relation-based heuristic algorithm is the best one where 96.25\% of the test cases get the best value. The running time of ordered relation-based heuristic algorithm is also the best one, whose time complexity is O(n^2).

Kata Kunci : heuristik, penjadwalan bergantung pada waktu, komposisi fungsi, fungsi monoton naik