TABU SEARCH SEBAGAI LOCAL SEARCH PADA ALGORITMA ANT COLONY UNTUK PENJADWALAN FLOWSHOP

Abstract

Ant colony optimization (ACO) is one of the meta-heuristic methods developed for finding solutions to optimization problems such as scheduling. Local search method is one part of the ACO which determines the quality of the resulting solution. In this paper, Tabu Search was proposed as a method of local search in ACO to solve the problem of flowshop scheduling. The purpose of this scheduling was to minimize the makespan. Makespan and computation time of the proposed method were compared to the ACO that implemented Job-Index as local search method. Using proposed algorithm, makespan values obtained were not significantly different than solutions of ACO using Job-Index method, and had computation time shorter. Abstract in Bahasa Indonesia: Ant colony optimization (ACO) adalah salah satu metode meta-heuristic yang dikembangkan untuk mencari solusi bagi permasalahan optimasi seperti penjadwalan. Metode local search merupakan salah satu bagian dari ACO yang menentukan kualitas solusi yang dihasilkan. Dalam makalah ini Tabu Search diusulkan sebagai metode local search dalam algoritma ACO untuk menyelesaikan masalah penjadwalan flowshop. Tujuan dari penjadwalan ini adalah untuk meminimalkan makespan. Hasil makespan dan computation time dari metode usulan ini akan dibandingkan dengan algoritma ACO yang menggunakan Job-Index sebagai metode local search. Dengan menggunakan algoritma Tabu Search sebagai local search didapat nilai makespan yang tidak berbeda secara signifikan dibandingkan yang menggunakan metode Job-Index, dengan kelebihan computation time yang lebih singkat. Kata kunci: Tabu Search, Ant Colony Algorithm, Local Search, Penjadwalan Flowshop.