Algoritma Penjadwalan Job Shop Alternatif Routing Menggunakan Greedy Randomized Adaptive Search Procedure With Fixed Threshold Untuk Minimisasi Makespan

Sari

Penelitian ini membahas algortima penjadwalan job shop dengan alternatif routing menggunakan greedy randomized adaptive search procedure with fixed threshold dengan fungsi tujuan minimisasi makespan. GRASP with fixed threshold adalah metode metaheuristik dua tahap untuk menyelesaikan masalah-masalah optimasi kombinatorial. Tahap pertama adalah tahap konstruksi jadwal inisial. Tahap kedua adalah tahap local search untuk memperbaiki jadwal inisial. Performansi algoritma usulan diuji melalui 2 skenario dengan menggunakan set data dari literatur. Hasil pengujian kedua skenario menunjukkan bahwa algoritma usulan memberikan solusi yang kompetitif jika dibandingkan dengan penelitian-penelitian sebelumnya.

Kata Kunci: Penjadwalan Job Shop, Alternatif Routing, GRASP, Threshold Accepting

ABSTRACT

In this paper we present algorithms job shop scheduling with alternative routing using a greedy randomized adaptive search procedu with a fixed threshold with makespan minimization objective function. GRASP with fixed threshold is a two-phase metaheuristic methods for solving combinatorial optimization problems. The first stage is the initial stage of construction. The second stage is the stage of local search to improve the initial schedule. Performance of the proposed algorithm was tested through two scenarios using data sets from the literature. Theresults indicate that the proposed algorithm provides a competitive solution when compared with previous studies.

Key words: Job Shop Scheduling, Alternative Routing, GRASP, Threshold Accepting