Review Paper: Cross Entropy-Genetic Algorithm Untuk Permasalahan Pernjadwalan Job-Shop Tanpa Waktu Tunggu Pada Banyak Mesin

Cross Ethorpy merupakan salah satu metode metahuristik untuk mendapatkan pendekatan penyelesaian permasalahan dalam penjadwalan job shop tanda waktu tunggu (no wait job shop scheduling - NWJSS). Metode ini sudah diaplikasikan pada permasalahan optimasi kombinatorial, optimasi multi eksternal, serta rare event simulation, dengan hasil penyelesaian yang cukup optimal dengan waktu yang relative singkat. Pada permasalahan penjadwalan job shop NWJSS mesin ini mengimplementasikan metode cross entropy yang dihibridasi dengan algoritma genetika (cross entropy – genetic algorithm (CEGA)), selain itu membandingkan kelebihan dan kekurangan antara metode  CEGA dengan metode lain pada permasalahan yang sama. Permasalahan NJWSS merupakan permasalahan yang tergolong non-polynomial hard (NP-Hard), terutama pada permasalahan banyak mesin (m-machine NWJSS). Pada permasalahan job shop secara umum urutan pengerjaan operasi pada masing-masing job tidak sama, sehingga ketidaktepatan penjadwalan dapat mengakibatkan bertambahnya waktu penyelesaian keseluruhan job (makespan). Selain itu batasan no-wait (tanpa waktu tunggu) – misalnya pada beberapa perusahaan pengecoran logam, plastic, dan makanan – membuat permasalahan menjadi rumit, dimana ketidaktepatan penjadwalan dapat mengakibatkan mundurnya makespan yang lebih signifikan. Hal ini karena keberlangsungan operasi kerja dalam satu job harus dijaga untuk menghindari pengerjaan ulang operasi (operation rework) maupun pengerjaan ulang job kembali dari operasi permulaan (job redo).

Beberapa penelitian untuk mendapatkan penyelesaian NWJSS tersebut telah dilakukan, misalnya dengan Genetic-Algorithm-Simulated Annealing (Schuster,  2003)  dan  Tabu  Search Hibrida  (Bożejko, 2009). Beberapa dari metode tersebut mendapatkan hasil makespan yang kurang optimal, namun ada pula yang mendapatkan hasil makespan yang optimal namun dengan waktu komputasi yang relatif lama. Penggunaan pendekatan  cross entropy-genetic algorithm  untuk mengembangkan algoritma dalam menyelesaikan permasalahan  NWJSS  diharapkan menjadi alternatif untuk menghasilkan jadwal dengan makespan yang optimal. Kaidah  cross entropy  digunakan sebagai kaidah dasar dalam algoritma, sedangkan kaidah algoritma genetika hanya terbatas penggunaannya pada proses pembangkitan sampel. Metode  cross entropy  sendiri diilhami oleh sebuah konsep pada teori informasi modern, yakni konsep jarak Kullback-Leibler atau yang dikenal juga dengan nama yang sama: konsep jarak cross entropy (Rubinstein, 2004). Konsep ini dikembangkan oleh Solomon Kullback dan Richard Leibler, untuk mengukur perbedaan selisih jarak antara sebuah distribusi referensi ideal  p  dengan distribusi teraplikasi  q. Sedangkan metode algoritma genetika sendiri  diilhamii dari proses evolusi biologis yang terjadi di alam, yang meliputi unsur-unsur pewarisan gen, seleksi alam, pindah silang atau rekombinasi, dan mutasi. 

Pengujian dari algoritma CEGA dibagi untuk kasus-kasus yang berbeda. Kasus-kasus tersebut seperti kasus ukuran kecil dan kasus ukuran besar. Pada hasil pengujian algoritma kasus kecil performansi dari CEGA relative baik, sedangkan pada kasus berukuran besar cenderung menurun. Dapat dilihat pada tabel berikut. 

Jika dibandingkan dengan algoritma yang lain seperti Genetic-Simulated Annealing (GASA) dan Hybird Tabu Search (HTS) performasi CEGA berdasarkan makespan terbaik terdapat pada CEGA, dibandingkan dengan GASA. Sedangkan dibandingkan dengan HTS, CEGA relative sama dengan HTS.  Dapat dilihat pada tabel berikut.

url: scholar.google.com  berjudul Pendekatan Cross Entropy-Genetic Algorithm Untuk Permasalahan Pernjadwalan Job-Shop Tanpa Waktu Tunggu Pada Banyak Mesin