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

OpenMP, MPI, dan CUDA Algoritma Paralel

Pada ilmu computer, algoritma parallel atau algoritma konkuren, ini merupakan kebalikan dari algoritma tradisional sekuensial (serial). Algoritma parallel merupakan algoritma yang dapat dieksekusi dalam satu waktu pada banyak perangkat processing yang berbeda, dan pada akhirnya akan digabungkan kembali untuk mendapatkan hasil yang benar. Beberapa algoritma mudah untuk dibagi ke dalam cara ini. Contohnya, memisahkan pekerjaan dengan mengcek semua nomor dari satu sampat 100ribu untuk melihat pernyataan mana yang akan dijadikan landasan untuk menetapkan subset dari nomor setiap prosesor yang ada, dan kemudian menaruh data dengan hasil yang akan dkembalikan bersama-sama. Algoritma ini juga telah diterapkan untuk algoritma seperti rubik kubus dan dekripsi hash. Untuk penjelasan lebih lanjut dari algoritma parallel ini, perlu diketahui terdapat beberapa platform yang biasa digunakan dalam pemrograman parallel, yaitu OpenMp, MPI, CUDA, dan lain sebagainya. Di bawah ini akan dijelaskan mengenai platform tersebut, penjelasan singkat adalah sebagai berikut: 

1. OpenMP

OpenMP yaitu API yang mendukung multiplatform untuk pemrograman multiprocessing shared memory pada C, C++, dan Fortran, di semua arsitektur prosesor dan OS termasuk platform Solaris, AIX, HP-UX, GNU/Linux. Max OS X, dan Windows. Ini terdiri dari kumpulan compiler directive, library routines, dan environment variable yang akan membuat run time pada semua keadaan. OpenMP merupakan suatu teknologi nonprofit yang diatur oleh OpenMP Architecture Review Board (or OpenMP ARB) termasuk didalamnyaa vendor hardware dan software yaitu AMD, IBM, Intel, Cray, HP, Fujitsu, Nvidia, NEC, Microsoft, Texas Instruments, Oracle Corporation, dan masih banyak lagi.   

2. MPI (Message Passing Interface)
MPI (Message Passing Interface) yaitu suatu standard dan message passing interface partabel system yang didesain oleh grup penelitian dari akademi dan industry untuk mengembangkan fungsi dan macam-macam dari computer parallel. Standar ini mendifinisikan sintaks dan semantic dari core library routine yang berguna untuk memperbesar jangkauan kepada user menulis portable program message passing pada Fortran 77 dan bahasa C. Bebedapa keebaikan dirasakan dan implementasi efisien dari  MPI termasuk beberapa free da nada pada domain public. Ini dipupuk kedalam pengembangan dalam parallel industry software, dan kemajuan portable development, dan kemampuan skala lebih besari aplikasi parallel. 

3. CUDA (Compute Unified Device Architecture)

CUDA (Compute Unified Device Architecture) merupakan platform parallel computing dan model pemrograman yang telah dibuat oleh NVIDIDA dan diimplementasikan oleh GPU(Graphic Processing Unit). CUDA memberikan akses pengembangan untuk kumpulan visual instruction dan ingatan dari parallel computasional elemen CUDA GPU. 

http://www.mcs.anl.gov/~itf/dbpp/
http://en.wikipedia.org/wiki/OpenMP
http://en.wikipedia.org/wiki/Parallel_algorithm
http://en.wikipedia.org/wiki/CUDA