ALGORITMA PENJADWALAN NO-WAIT JOB SHOP MENGGUNAKAN GREEDY RANDOMIZED ADAPTIVE SEARCH PROCEDURE WITH FIXED THRESHOLD DENGAN KRITERIA MINIMISASI MAKESPAN

Sari

Pada kenyataannya, beberapa perusahaan industri tidak mengijinkan adanya kondisi no-wait. Kondisi no-wait, yaitu kondisi yang tidak memperkenankan adanya delay, dimana saat selesai operasi dari suatu job di suatu mesin harus sama dengan saat mulai operasi dari job tersebut pada mesin berikutnya. Penelitian ini membahas tentang metode metaheuristik untuk menyelesaikan masalah no-wait job shop. Algoritma yang digunakan yaitu greedy randomized adaptive search procedure (GRASP) with fixed threshold dengan kriteria minimasi makespan. Algoritma ini mempunyai dua tahap. Tahap pertama merupakan tahap konstruksi yang menghasilkan solusi inisial. Tahap kedua merupakan tahap local search untuk memperbaiki jadwal inisial dengan melakukan proses insert dan exchange. Nilai fixed threshold ditambahkan untuk membuka batas makespan yang diijinkan, sehingga kemungkinan untuk mendapatkan makespan dengan nilai lebih kecil akan lebih besar. Algoritma usulan diuji menggunakan set data dari literatur. Hasil yang didapat menunjukkan hasil yang sama baiknya dengan penelitian yang sebelumnya.

Kata kunci: Penjadwalan, No-Wait Job Shop, GRASP, Fixed Threshold

 

ABSTRACT

In the fact, some industrial companies doesn’t allow no-wait condition. it’s a condition that doesn’t allow of any delay, which completed the operation from a job in a machine should be the same with the start of operations of the job on the next machine. This research discusses about metaheuristic method to resolve no-wait job shop problem. It’s used greedy randomized adaptive search procedure (GRASP) with fixed threshold with mekespan minimization criteria. It’s has two stages. First stage is construction stage which generates initial solution. Second stage is local search stage to fixing initial solution by doing insert and exchange process. Fixed threshold value added to open makespan permitted, so that a chances of getting an makespan with a smaller value will be greater. Porposed algorithm is tested using data sets form literature. The result obtained showed the same result as good as previous research.

Keywords: Scheduling, No-Wait Job Shop, GRASP, Fixed Threshold