APLIKASI RELAKSASI LAGRANGE BERDASARKAN METODE BRANCH AND BOUND DALAM PENJADWALAN

AFNIRIA PAKPAHAN, Dr. Irwan Endrayanto, M.Sc

2016 | Tesis | S2 Matematika

Penelitian ini membahas tentang penjadwalan yang merupakan salah satu contoh masalah NP-Hard yang menggunakan relaksasi Lagrange berdasarkan metode \emph{branch and bound}. Pada tahap awal penelitian penjadwalan ini menggunakan metode \emph{branch and bound}, kemudian untuk membantu mempermudah masalah penjadwalan ini digunakan \emph{dominance properties} sehingga mengurangi ruang solusi. Selanjutnya, relaksasi Lagrange adalah metode dalam masalah optimisasi kombinatorik untuk menentukan \emph{Lower bound}. Pada akhir pembahasan akan diberi contoh penjadwalan dengan menggunakan mesin tunggal dengan metode relaksasi Lagrange.

The research examine about scheduling that one of the NP-Hard Problem, using Lagrangean relaxation based branch and bound methode. The first, branch and bound use in single machine scheduling, then dominance properties will be proposed to reduce the number of nodes. Lagrangean relaxation can be used in combinatorial optimization problem determine lower bound. The last examine will be applied Lagrangean relaxation in single machine scheduling.

Kata Kunci : NP-hard, Branch and bound, Dominance Properties, Lagrangean relaxation