Analisa Panjang Tabu List pada Permasalahan Penjadwalan Job Shop

Abstract

Permasalahan penjadwalan job shop adalah permasalahan penjadwalan tentang urutan proses sejumlah pekerjaan yang dikerjakan pada sejumlah mesin supaya meminimalkan mesin yang idle dan waktu tunggu sehingga diperoleh total waktu pengerjaan atau makespan yang minimal. Permasalahan penjadwalan job shop termasuk ke dalam permasalahan NP-hard karena pencarian solusinya akan naik secara eksponensial seiring dengan naiknya ukuran permasalahan secara linear. Tabu search merupakan salah satu metode meta heuristik yang mampu menyelesaikan permasalahan ini karena memiliki kemampuan untuk mengarahkan metode lain untuk keluar atau menghindari dari solusi optimal yang bersifat lokal dengan memanfaatkan struktur memori yang mencatat jejak proses pencarian yang telah dilakukan yakni tabu list. Dalam teknik tabu search diketahui bahwa panjang tabu list mempengaruhi performa dari tabu search. Ukuran tabu list yang terlalu kecil menyebabkan terjadinya local optimum dan ukuran yang terlalu besar menyebabkan algoritma tidak bekerja dengan efektif dan semakin lambat dalam mencari solusi yang terbaik. Pada penelitian ini dilakukan analisa pengaruh panjang tabu list terhadap kinerja algoritma tabu search pada permasalahan penjadwalan job shop. Ukuran tabu list yang diperoleh dengan mencari nilai tengah dari ukuran minimum tabu list dan ukuran tabu list yang diperoleh dari metode tabu search sebesar √N dimana N adalah jumlah seluruh operasi , dibandingkan dengan ukuran tabu list yang konstan yakni 2, 4, 6, 8, 10, dan juga √N. Hasil percobaan diperoleh bahwa ukuran tabu list yang diperoleh dengan mencari nilai tengah tersebut ideal untuk ukuran job baik skala kecil maupun besar (100x20).

Job shop scheduling problem is a scheduling problem about the sequence of processes a number of work done on a number of machines in order to minimize idle engine and waiting time so as to obtain the minimum time of work. The job shop scheduling problem is included in the NP-hard problem because the search for the solution will increase exponentially as linearly increasing the size of problem. Tabu search is one of the meta-heuristics methods that can solve this problem because it has the ability to direct other methods to exit or avoid from local optimal solutions by utilizing the memory structure that records the trace of the search process that has been done that called tabu list. In tabu search technique is noted that the length of tabu list affects the performance of tabu search. The size of tabu list is too small causes the local optimum and the size is too large causes the algorithm does not work effectively and will be slower for finding the best solution. In this research, the authors analyse the influence of the length of tabu list on the performance of tabu search algorithm on job shop scheduling problem. The size of tabu list is obtained by finding the median value of the minimum tabu list and the size of tabu list that obtained from the method of tabu search of √N where N is the sum of all operations, is compared with the constant length of tabu list of 2, 4, 6, 8, 10 and also √N. The result of experiment shows that the length of tabu list that obtained by finding the median value is ideal for the small and large (100x20) size job.