Penggunaan Algoritme Genetika dalam Penyelesaian Job Shop Scheduling Problem

Abstract

Job Shop Scheduling Problem (JSSP) merupakan sebuah masalah dengan sekumpulan pekerjaan yang harus diproses pada sekumpulan mesin yang bertujuan untuk memperoleh jadwal pekerjaan dengan makespan seminimal mungkin. Makespan merupakan total waktu yang diperlukan untuk menyelesaikan semua pekerjaan. Pada karya ilmiah ini, dijelaskan bagaimana algoritme genetika dalam menyelesaikan JSSP dengan beberapa ukuran kasus. Terdapat lima kasus yang digolongkan menjadi 3 jenis kasus, yaitu kasus kecil untuk I dan II, kasus sedang untuk III dan kasus besar untuk IV dan V. Jadwal pada kasus JSSP direpresentasikan sebagai kromosom yang berisikan sekumpulan gen. Hasil percobaan numerik menunjukkan adanya perbaikan nilai makespan jika jumlah iterasi dan ukuran populasi mengalami peningkatan. Hasil nilai makespan terbaik yang diperoleh untuk kasus I, II, III, IV, dan V secara berurutan adalah sebesar 318, 388, 328, 830, dan 1370 satuan waktu, dengan waktu komputasi masingmasing adalah 0.0441, 0.0586, 0.6358, 94.8995, dan 237.7296 detik.

Job Shop Scheduling Problems (JSSP) are the problems of processing a set of jobs on a set of machines in order to obtain a job schedule with a minimum makespan (the total time required to complete all the work). In this paper, it is described how genetic algorithm is used to solving JSSPs with several case sizes. There are five case sizes which are classified into 3 categories, namely the small case (case I and II), the moderate case (case III) and the large case (case IV and V). A schedule in JSSP case is represented as a chromosome containing a set of genes. The research result shows that makespan is improved if the iteration number or the population size is increased. The best makespan values obtained from the experiments for cases I, II, III, IV, and V respectively are 318, 388, 328, 830, and 1370 units of time, with computational times of 0.0441, 0.0586, 0.6358, 94.8995 and 237.7296 seconds respectively.