\documentclass{template-jurnal} %Bagian ini diedit oleh editor Jurnal Matematika UNAND \usepackage{multirow} \hyphenation{di-tulis-kan di-terang-kan} %Perhatikan aturan penulisan dan ukuran huruf yang digunakan \begin{document} \markboth{Paranditus dkk} %Jika lebih dari dua penulis, tuliskan sebagai Nama Penulis Pertama dkk. {Penerapan Algoritma \textit{Cross Entropy–Genetic Algorithm} Untuk Optimasi Makespan Pada Penjadwalan \textit{Flow Shop}} %%%%%%%%%%%%%%%%%%%%% Publisher's Area please ignore %%%%%%%%%%%%%%% % \catchline{}{}{}{}{} % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{PENERAPAN ALGORITMA \textit{CROSS ENTROPY–GENETIC ALGORITHM} UNTUK OPTIMASI MAKESPAN PADA PENJADWALAN \textit{FLOW SHOP}} \author {PARANDITUS,EVI NOVIANI\footnote{penulis korespondensi} , YUDHI} \address{Program Studi S1 Matematika,\\ Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Tanjungpura, Pontianak\\ email : \email{evi\_noviani@math.untan.ac.id}} \maketitle \setcounter{page}{1} %bagian ini diedit oleh editor Jurnal Matematika UNAND \begin{abstract} \begin{center} Diterima ..... \quad Direvisi ..... \quad Dipublikasikan ..... %tanggal-tanggal tersebut \textbf{dikosongkan} saja \end{center} \bigskip \textbf{Abstrak}. %Dalam bahasa Indonesia Penjadwalan \textit{flow shop} merupakan jenis penjadwalan produksi dimana setiap pekerjaan yang diproses seluruhnya mengalir pada proses yang sama, dengan tujuan untuk mencari urutan pekerjaan yang dapat mengoptimalkan nilai \textit{makespan}. Penelitian ini bertujuan untuk mencari kombinasi urutan pekerjaan dengan nilai \textit{makespan} yang optimal pada CV Bestone Indonesia. Permasalahan penjadwalan \textit{flow shop} dapat diselesaikan dengan menggunakan \textit{Cross Entropy–Genetic Algorithm} (CEGA). Algoritma CEGA bekerja dengan cara membangkitkan sampel awal $(N)$ secara acak, kemudian sampel selanjutnya diperoleh dari hasil proses \textit{crossover} dan mutasi dengan parameter berupa parameter kejarangan $(\rho)$, koefisien penghalusan $(\alpha)$, parameter \textit{crossover} $(P_c)$ dan parameter pemberhentian $(\beta)$. Berdasarkan pengolahan data yang telah dilakukan menggunakan Algoritma CEGA, diperoleh urutan pekerjaan 3, pekerjaan 1, pekerjaan 4, pekerjaan 2 dan urutan pekerjaan 3, pekerjaan 4, pekerjaan 1, pekerjaan 2 serta nilai makespan sebesar 389116,52 detik. \bigskip \keywords{Penjadwalan \textit{flow shop}, \textit{Makespan}, \textit{Cross Entropy–Genetic Algorithm}} \end{abstract} \section{Pendahuluan} Permasalahan dalam penyusunan jadwal produksi adalah sulitnya menentukan jadwal pekerjaan sehingga pekerjaan tersebut dapat selesai sesuai dengan batas waktu penyelesaian. Penjadwalan merupakan proses pengurutan pengerjaan setiap produk yang dikerjakan pada beberapa buah mesin. Proses pengurutan pengerjaan (\textit{sequencing}) setiap produk melibatkan pengerjaan sejumlah elemen-elemen dasar yang disebut dengan operasi. Tiap operasi memerlukan alokasi sumber daya tertentu selama periode waktu tertentu yang sering disebut waktu proses, yaitu waktu pengerjaan yang diperlukan untuk melakukan operasi \cite{A1}. Berdasarkan pola alirannya, terdapat 2 jenis penjadwalan produksi yaitu penjadwalan \textit{flow shop} dan penjadwalan \textit{job shop}. Pada penjadwalan \textit{flow shop} setiap pekerjaan diproses di setiap mesin dengan urutan proses yang sama. Sedangkan, pada penjadwalan \textit{job shop} setiap pekerjaan memiliki urutan proses yang berbeda \cite{A2}. Dalam penjadwalan \textit{flow shop} terdapat beberapa pekerjaan $(n)$ yang dijadwalkan pada beberapa mesin $(m)$ dan waktu proses per unit pekerjaan ke-$j$ pada mesin ke-$i$, dinotasikan sebagai $t_{ij}$ (dengan $i=1, \cdots ,m ; j=1, \cdots ,n$). Setiap pekerjaan memiliki urutan pemrosesan yang sama di setiap mesin, tujuan penjadwalannya adalah mencari urutan pemrosesan pekerjaan yang dapat meminimumkan total waktu yang diperlukan untuk menyelesaikan seluruh pekerjaan yang kemudian disebut \textit{Makespan} \cite{A3}. CV Bestone Indonesia merupakan perusahaan yang bergerak di bidang hiasan dinding dengan bahan baku batu alam. Terletak di Kota Magelang, Provinsi Jawa Tengah. Jenis produk yang diproduksi adalah produk BEST 20 SH, produk BEST 47 A, produk BEST 47 dan produk BEST 50 SH. Dalam melakukan produksi, CV Bestone Indonesia menggunakan penjadwalan \textit{flow shop} \cite{A4}. Akan tetapi, perusahaan ini menerapkan metode intuisi atau perkiraan untuk menentukan produk mana yang akan dikerjakan terlebih dahulu. Metode intuisi tidak mempertimbangkan nilai \textit{makespan}, keterlambatan penyelesaian pekerjaan, dan batas waktu pesanan. Sehingga, perusahaan kesulitan dalam membuat jadwal produksi ketika banyaknya permintaan dengan jenis produk yang beragam. Oleh karena itu, diperlukan metode yang efektif untuk dapat mengoptimalkan nilai \textit{makespan} sehingga proses produksi dapat meningkat dan permintaan produk dapat terpenuhi \cite{A4}. Masalah penjadwalan produksi seperti pada CV Bestone Indonesia, dapat diselesaikan dengan menggunakan beberapa metode diantaranya adalah Algoritma \textit{Cross Entropy} (CE) dan \textit{Genentic Algorithm} (GA). Algoritma CE pertama kali diperkenalkan pada tahun 1997 oleh Rubinstein yang bertujuan untuk mendapatkan urutan pekerjaan yang optimal dengan cepat melalui proses iterasi \cite{A5, A11}. Sedangkan, GA merupakan metode pencarian yang memanfaatkan mekanisme operasi genetika dan seleksi alam \cite{A7, A12, A13, A15}. penggabungan Algoritma CE dengan GA yang kemudian disebut Algoritma \textit{Cross Entropy-Genetic Algorithm} (CEGA) telah diterapkan pada penjadwalan \textit{flow shop} dengan menentukan nilai \textit{makespan} yang terkecil \cite{A5, A9, A10}. Algoritma CEGA juga dapat diterapkan pada permasalahan penjadwalan pekerjaan dengan beberapa fungsi tujuan, seperti mengoptimalkan nilai \textit{makespan} dan total \textit{weighted tardiness} (TWT)\cite{A6, A14}. Pada penelitian ini, penjadwalan \textit{flow shop} pada CV Bestone Indonesia menggunakan Algoritma CEGA untuk menentukan urutan pekerjaan dan nilai \textit{makespan} yang optimal. Proses penjadwalan \textit{flow shop} dimulai dengan inisialisasi parameter dan membangkitkan sampel awal dengan bilangan acak. Setiap sampel kemudian dievaluasi dengan menghitung nilai \textit{makespan}. Sampel selanjutnya diperoleh dari proses \textit{crossover} dan mutasi. Setelah diperoleh sampel baru dari proses mutasi, kemudian dilakukan perhitungan fungsi tujuan (\textit{makespan}) sampel baru hingga diperoleh urutan pekerjaan dengan nilai \textit{makespan} yang paling mininum. \section{Algoritma \textit{Cross Entropy–Genetic Algorithm} (CEGA)} Algoritma CE bekerja dengan cara mengambil sampel awal secara acak dari ruang lingkup permasalahan. Sampel yang diperoleh kemudian dievaluasi dengan menghitung nilai fungsi tujuan. Selanjutnya, parameter diperbaharui berdasarkan sampel terbaik, dengan tujuan untuk memperoleh solusi yang lebih baik pada iterasi selanjutnya. Proses ini dilakukan secara berulang hingga diperoleh sampel yang optimal \cite{A6}. Sedangkan, Genetic Algorithm (GA) bekerja dengan membangkitkan sekumpulan kromosom secara acak untuk generasi awal. Selanjutnya, setiap kromosom akan dievaluasi berdasarkan nilai \textit{fitness} dari masing-masing kromosom yang telah diperoleh, kemudian dipilih kromosom dengan nilai \textit{fitness} terbaik. Kromosom yang terpilih (kromosom induk) selanjutnya ditukar dengan kromosom yang lain untuk membentuk kromosom baru melalui operasi genetika (\textit{Crossover} dan Mutasi) yang bertujuan untuk mendapatkan kromosom yang lebih baik pada iterasi selanjutnya \cite{A7}. Pada penelitian ini kromosom merupakan urutan pekerjaan yang membentuk \textit{string}. Sedangkan, gen merupakan pekerjaan yang terdapat di dalam kromosom. Penggabungan Algoritma CE dan GA bertujuan untuk memperluas pencarian solusi pada sampel elit pada Algoritma CE dengan menambahkan mekanisme GA, yaitu \textit{crossover} dan mutasi. Mekanisme GA berfungsi untuk menghindari pencarian solusi yang terjebak di area lokal optimal, karena \textit{crossover} dan mutasi dapat menghasilkan kromosom baru yang memiliki sifat tetap menjaga kromosom pada populasi awalnya. Berikut tahapan-tahapan Algoritma CEGA \cite{A5}: \begin{enumerate} \item [1).] Inisialisasi parameter. Beberapa parameter yang akan ditentukan nilainya antara lain: Jumlah sampel $(N)$ yang akan dibangkitkan. Parameter kejarangan $(\rho)$, nilai $\rho$ yang umum digunakan berkisar antara $1\%-10\%$. Koefisien penghalusan $(\alpha)$, nilai $0,4 < \alpha < 0,9$ merupakan nilai yang paling optimal \cite{A8}. Parameter crossover $(P_c)$, memiliki nilai antara $0\leq P_{c}\leq 1$. Parameter pemberhentian $(\beta)$. \item [2.)] Pembangkitan sampel. Sampel yang dibangkitkan pada iterasi pertama merupakan sampel yang dibangkitkan secara acak dengan membangkitkan bilangan acak sebanyak $N$. Kemudian, bilangan acak tersebut akan digunakan untuk menentukan pekerjaan yang akan dipilih. Sedangkan, sampel iterasi selanjutnya diperoleh dari mekanisme \textit{crossover} dan mutasi. Jumlah sampel yang dibangkitkan sebanyak $N$ sampel yaitu $X(1),\cdots,X(N)$ yang telah ditentukan pada langkah 1. Sampel yang dibangkitkan merupakan urutan pekerjaan sepanjang $N$. \item[3).] Perhitungan fungsi tujuan. Fungsi tujuan dihitung dengan meminimumkan nilai \textit{makespan}. Nilai \textit{makespan} diperoleh dari pekerjaan yang memiliki nilai \textit{flow time} paling maksimum. \textit{Flow time} $(F_j)$ adalah rentang waktu pada saat pekerjaan siap untuk diproses sampai ketika pekerjaan selesai diproses. Jadi, \textit{flow time} sama dengan penjumlahan waktu proses dengan waktu mulai produksi. Waktu proses $(WP_{i,j})$ adalah perkiraan waktu yang diperlukan untuk memproses suatu pekerjaan. Sedangkan, waktu mulai $(WM_{i,j})$ adalah waktu yang menunjukkan saat pekerjaan siap untuk dikerjakan \cite{A1}. Persamaan berikut untuk menghitung nilai \textit{makespan} pada tiap sampel yang dibangkitkan \cite{A5}: \begin{equation}\label{P1} Z=\text{maks}_{1\leq j \leq n}\left(F_{j}\right) \end{equation} dengan $F_j$ adalah \textit{flow time} pekerjaan urutan ke-$j$, \textit{flow time} sama dengan waktu selesai pekerjaan pada mesin terakhir maka $F_j={WS}_{m,j}$, dengan $j=1\cdots,n$, $m$ merupakan mesin ke-$m$ dan ${WS}_{m,j}={WP}_{m,j}+{WM}_{m,j}$. Nilai waktu mulai pada proses perhitungan fungsi tujuan menggunakan syarat sebagai berikut: \begin{itemize} \item [i).] Jika tidak terdapat pekerjaan pendahulu dan mesin pendahulu, maka waktu mulai pekerjaan = 0. \begin{equation}\label{P2} {WM}_{i,j}=0 \end{equation} \item [ii).] Jika tidak terdapat pekerjaan pendahulu namun terdapat mesin pendahulu, maka waktu mulai pekerjaan = waktu selesai pekerjaan di mesin pendahulu. \begin{equation}\label{P3} {WM}_{i,j}={WS}_{i-1,j} \end{equation} \item [iii).] Jika terdapat pekerjaan pendahulu namun tidak terdapat mesin pendahulu, maka waktu mulai pekerjaan = waktu selesai pekerjaan pendahulu. \begin{equation}\label{P4} {WM}_{i,j}={WS}_{i,j-1} \end{equation} \item [iv).]Jika terdapat pekerjaan pendahulu dan terdapat mesin pendahulu, maka waktu mulai pekerjaan = waktu terlama di antara waktu selesai pekerjaan pendahulu dengan waktu selesai pekerjaan di mesin pendahulu. \begin{equation}\label{P5} WM_{i,j}=\text{maks}\lbrace WS_{i,j-1},WS_{i-1,j}\rbrace \end{equation} \end{itemize} Persamaan berikut untuk menentukan waktu selesai pekerjaan ke-$j$ pada mesin ke-$i$. \begin{equation*} {WS}_{i,j}={WP}_{i,j}+{WM}_{i,j}\, \text{dengan }\, i=1,\cdots,m \,j=1,\cdots,n. \end{equation*} Keterangan: \begin{enumerate} \item [1.] ${WS}_{i,j}$ adalah waktu selesai pekerjaan urutan ke-$j$ pada mesin ke-$i$. \item [2.] ${WP}_{i,j}$ adalah waktu proses pekerjaan urutan ke-$j$ pada mesin ke-$i$. \item [3.] ${WM}_{i,j}$ adalah waktu mulai pekerjaan urutan ke-$j$ pada mesin ke-$i$. \end{enumerate} \item [4).] Mengecek iterasi maksimal. Pengecekkan iterasi maksimal mengunakan $\varepsilon=|P_c (k)-P_c (k-1)|$. Nilai $P_c (k)$ merupakan parameter \textit{crossover} pada iterasi ke-$k$. Apabila nilai $\varepsilon>\beta$ maka kriteria pemberhentian belum tercapai dan lanjut kelangkah 5. Namun, apabila nilai $\varepsilon\leq\beta$ maka kriteria pemberhentian tercapai dan iterasi selesai. \item [5).] Penentuan sampel elit. Jumlah sampel elit ditentukan oleh $\lceil\rho\times N\rceil$. Kemudian, diambil sampel elit dari sampel yang telah diurutkan yang memiliki nilai \textit{makespan} terkecil sebanyak $\lceil\rho\times N\rceil$ \cite{A6}. \item [6).] Pembobotan sampel. Nilai pembobotan sampel elit diperoleh dari evaluasi terhadap sampel yang memiliki nilai \textit{fitness} tertinggi pada iterasi sebelumnya. Bobot sampel elit yang diperoleh dijadikan sebagai dasar penentuan sampel yang dielitisme \cite{A6}. \item [7).] Perhitungan \textit{linier fitness rangking} (LFR). Nilai LFR digunakan untuk pemilihan induk pada proses \textit{crossover}. Persamaan berikut untuk menentukan nilai LFR, \begin{equation}\label{P6} \text{LFR}(i)=Fmaks-(Fmaks-Fmin)\times\left(\frac{i-1}{N-1}\right) \end{equation} dengan $i=1,\cdots,N$, $Fmaks = 1/X(1)$, $Fmin = 1/X(N)$ dan $\text{LFR}(i)$ adalah nilai LFR sampel ke-$i$. \item [8).] Update parameter \textit{crossover}. Proses ini dilakukan untuk mendapatkan nilai parameter baru. Parameter tersebut digunakan untuk evaluasi kriteria pemberhentian dan menentukan kromosom yang di \textit{crossover}. Update parameter \textit{crossover} dilakukan di setiap iterasi. Persamaan berikut untuk update parameter \textit{crossover}, \begin{equation*} P_c (k)=(1-\alpha)\times u+\left(P_c (k-1)\times\alpha\right), \end{equation*} dengan $k$ merupakan iterasi ke-$k$ dan $u=\frac{\bar{Ze}}{2Z_{best}}$, $\bar{Ze}$ adalah rata-rata \textit{makespan} dari sampel elit dan $Z_{best}$ adalah \textit{makespan} terkecil tiap iterasi \cite{A6}. \item [9).] Elitisme bertujuan untuk mempertahankan sampel yang memiliki nilai fungsi tujuan terkecil atau nilai \textit{fitness} tertinggi agar terpilih kembali pada iterasi berikutnya. Jumlah sampel yang di elitisme sebanyak jumlah sampel elit \cite{A6}. \item [10).] Penentuan pemilihan induk \textit{crossover}. Proses ini dilakukan menggunakan mekanisme \textit{roulette wheel}, yaitu berdasarkan nilai \textit{fitness} setiap sampel. Prosedur pemilihan induk 1 dan induk 2 menggunakan \textit{roulette wheel} adalah sebagai berikut: \begin{enumerate} \item [a.] Pemilihan induk 1, diambil dari sampel elit yang memiliki nilai fungsi tujuan terkecil dari mekanisme elitisme. \item [b.] Pemilihan induk 2, dipilih berdasarkan nilai evaluasi dari sampel keseluruhan, yaitu menggunakan nilai LFR dari sampel yang sedang dievaluasi. Apabila nilai perbandingan kumulatif LFR dan total LFR lebih besar dari nilai acak yang dibangkitkan, maka sampel tersebut menjadi induk 2. \end{enumerate} \item [11).] \textit{Crossover} (pindah silang). Menurut \cite{A6} \textit{crossover} adalah tahap pembentukan sampel baru (\textit{offspring}) dari dua sampel induk yang terpilih (\textit{parent}). Metode \textit{crossover} yang digunakan adalah pindah silang dari dua titik (\textit{2-point order crossover}), yaitu menukarkan gen (pekerjaan) diantara dua titik pada masing-masing induk. Persamaan berikut untuk menentukan pekerjaan dari sampel induk yang akan di \textit{crossover} adalah: \begin{equation*} b_i=\lceil r_i\times n\rceil \, \text{maka}\, p_i \, \text{dengan}\, r_i \, \text{adalah bilangan acak}\, [0,1] \,\text{untuk}\, i=1,2 \end{equation*} Jika $b_1b_2$ maka $b_1$ menjadi $p_2$ dan $b_2$ menjadi $p_1$. \item [12).] Mutasi, bertujuan untuk menghasilkan sampel baru (\textit{offspring}) dengan cara menukarkan beberapa pekerjaan pada suatu sampel. Parameter mutasi $(P_m)$ digunakan untuk menentukan jumlah sampel yang mengalami mutasi \cite{A7}. Nilai parameter mutasi ditentukan dengan rumus sebagai berikut \cite{A5}, \begin{equation*} P_m=\frac{P_c}{2}, \end{equation*} Jumlah sampel yang dimutasi adalah $n= \lceil P_m\times N\rceil$. Persamaan untuk menentukan bagian sampel yang dimutasi ($I,J$) , yaitu: \begin{equation*} I=\lceil r_1\times n\rceil\, \text{dan}\, J=\lceil r_2\times \rceil. \end{equation*} Persamaan berikut untuk menentukan mekanisme mutasi ($K$) yaitu: \begin{equation*} K = \lceil r\times 3\rceil, \end{equation*} dengan $r$, $r_1$, dan $r_2$ adalah bilangan acak $[0,1]$. Apabila nilai $K=1$ maka dilakukan \textit{flip mutation} (membalik), jika $K=2$ dilakukan \textit{swap mutation} (menukar), dan jika $K=3$ maka dilakukan \textit{slide mutation} (menggeser). Setelah diperoleh sampel yang baru dari hasil mutasi maka kembali ke langkah 3 untuk melakukan perhitungan fungsi tujuan yang baru. \end{enumerate} \section{Pembahasan} Data yang digunakan dalam penelitian ini adalah data sekunder yang diambil dari \cite{A4}. Data tersebut merupakan data waktu standar proses lamanya pengerjaan bahan baku batu alam pada tiap mesin di perusahaan CV Bestone Indonesia. Adapun data waktu lamanya proses pekerjaan pada tiap mesin dapat dilihat pada Tabel \ref{T1} berikut. \begin{table}[!h] \caption{Data waktu lamanya proses pekerjaan pada tiap mesin}\label{T1} \centering \begin{tabular}{c c c c c c c} \hline \multirow{2}{*}{\textbf{No.}} & \multirow{2}{*}{\textbf{Jenis Produk}} & \multicolumn{5}{c}{\textbf{Waktu Proses (detik)}}\\ \cline {3-7} & & \textbf{M1} & \textbf{M2} & \textbf{M3} & \textbf{M4} & \textbf{M5}\\ \hline 1 & BEST 20 SH & 74,66 & 86400 & 221,88 & 43200 & 22,66\\ 2 & BEST 47 A & 61,71 & 86400 & 166,38 & 43200 & 23,25\\ 3 & BEST 47 & 62,62 & 86400 & 166,04 & 43200 & 25,22\\ 4 & BEST 50 SH & 64,42 & 86400 & 176,45 & 43200 & 23,99\\ \hline \end{tabular} \end{table} Pekerjaan 1 didefinisikan sebagai proses pengerjaan produk BEST 20 SH, pekerjaan 2 didefinisikan sebagai proses pengerjaan produk BEST 47 A, pekerjaan 3 didefinisikan sebagai proses pengerjaan produk BEST 47 dan pekerjaan 4 didefinisikan sebagai proses pengerjaan produk BEST 50 SH. Setiap pekerjaan dikerjakan diseluruh mesin yaitu pada proses pemotongan sebagai M1, proses pengeringan pertama sebagai M2, proses perakitan sebagai M3, proses pengeringan kedua sebagai M4 dan proses penyimpanan sebagai M5. Tahapan Algoritma CEGA pada penjadwlan \textit{flow shop} adalah inisialisasi parameter, yaitu jumlah sampel $(N)$ sebanyak 6, parameter kejarangan $(\rho)$ sebesar 0,01, koefisien penghalusan $(\alpha)$ sebesar 0,6, parameter \textit{crossover} $(P_c)$ sebesar 1, dan parameter pemberhentian $(\beta)$ sebesar 0,0000001. Tahap selanjutnya adalah membangkitkan sampel awal dengan membangkitkan bilangan acak diantara 0 dan 1 sebanyak 4. Berikut bilangan acak yang digunakan untuk membangkitkan urutan pekerjaan sampel $X(1)$ pada Tabel \ref{T2}, \begin{table}[!h] \caption{Bilangan acak pada sampel $X(1)$}\label{T2} \centering \begin{tabular}{c c c} \hline \textbf{Pekerjaan} & \textbf{Bilangan Acak} & \textbf{No. Urut}\\ \hline 1 & 0,6723 & 3\\ 2 & 0,7320 & 4\\ 3 & 0,2669 & 1\\ 4 & 0,4758 & 2\\ \hline \end{tabular} \end{table} Bilangan acak pada Tabel \ref{T2} diurutkan berdasarkan nilai terkecil. Bilangan acak terkecil adalah 0,2669 berada di pekerjaan 3, maka pekerjaan 3 menjadi pekerjaan urutan pertama. Proses ini berlanjut sampai pada bilangana acak terbesar yaitu 0,7320 berada di pekerjaan 2, sehingga pekerjaan 2 menjadi pekerjaan urutan ke-4. Urutan pekerjaan yang didapat dari proses tersebut yaitu $X(1)= 3-4-1-2$. Diperoleh sampel awal yaitu: \begin{center} \begin{tabular}{c c c} $X(1) = 3-4-1-2$ & $X(3) = 1-3-4-2$ & $X(5) = 4-2-1-3$ \\ $X(2) = 1-2-4-3$ & $X(4) = 2-1-3-4$ & $X(6) = 2-3-1-4$ \end{tabular} \end{center} Selanjutnya dilakukan penghitungan fungsi tujuan setiap sampel dengan menggunakan Persamaan (\ref{P1}). Berikut perhitungan nilai \textit{flow time} $X(1)$ pada pekerjaan urutan ke-1: $F_1 = WS_{5,1}$, pekerjaan urutan ke-1 adalah pekerjaan 3 Berdasarkan Persamaan (\ref{P2}) maka nilai $\left(WM_{1,1} = 0\right)$, karena pekerjaan urutan ke-1 pada mesin ke-1 tidak ada pekerjaan pendahulu dan tidak ada mesin pendahulu. \[ WS_{1,1} = WP_{1,1} + WM_{1,1} = 62,62+0 = 62,62.\] Berdasarkan Persamaan (\ref{P3}) maka nilai $\left(WM_{2,1}\right) = WS_{1,1} = 62,62$, karena pekerjaan urutan ke-1 pada mesin ke-2 memiliki mesin pendahulu yaitu mesin ke-1, namun tidak memiliki pekerjaan pendahulu. \[WS_{2,1} = WP_{2,1} + WM_{2,1} = 86400 + 62,62 = 86462,62.\] Berdasarkan Persamaan (\ref{P3}) maka nilai $\left(WM_{3,1}\right) = WS_{2,1} =86462,62$, karena pekerjaan urutan ke-1 pada mesin ke-3 memiliki mesin pendahulu yaitu mesin ke-2, namun tidak memiliki pekerjaan pendahulu. \[WS_{3,1} = WP_{3,1} + WM_{3,1} = 166,04+86462,62 = 86628,66.\] Berdasarkan Persamaan (\ref{P3}) maka nilai $\left(WM_{4,1}\right) = WS_{3,1} = 86628,66$, karena pekerjaan urutan ke-1 pada mesin ke-4 memiliki mesin pendahulu yaitu mesin ke-3, namun tidak memiliki pekerjaan pendahulu. \[WS_{4,1} = WP_{4,1} + WM_{4,1} = 43200+86628,66 = 129828,66.\] Berdasarkan Persamaan (\ref{P3}) maka nilai $\left(WM_{5,1} = WS_{4,1}\right) = 129828,66$, karena pekerjaan urutan ke-1 pada mesin ke-5 memiliki mesin pendahulu yaitu mesin ke-4, namun tidak memiliki pekerjaan pendahulu. \[WS_{5,1} = WP_{5,1} + WM_{5,1} = 25,22+129828,66 = 129853,88.\] Jadi, diperoleh nilai $F_1$ sebesar 129853,88. Perhitungan \textit{flow time} untuk pekerjaan urutan selanjutnya menggunakan proses yang sama pada pekerjaan urutan ke-1. Sehingga diperoleh \textit{flow time} setiap pekerjaan yaitu $F_1= 129853,88$; $F_2= 216263,06$; $F_3= 302707,16$ dan $F_4= 389052,52$. Berdasarkan nilai \textit{flow time} maka nilai makespan kromosom $X(1)$ adalah \[Z =\text{maks}\lbrace{F_1,F_2,F_3,F_4}\rbrace = 389052,52\] untuk menghitung makespan sampel lainnya, mengunakan langkah yang sama dengan sampel $X(1)$. Sehingga diperoleh \textit{makespan} tiap sampel pada Tabel \ref{T3} berikut, \begin{table}[!h] \caption{Nilai \textit{makespan} untuk 6 sampel}\label{T3} \centering \begin{tabular}{c c | c c} \hline \textbf{Sampel} & \textbf{\textit{Makespan}} & \textbf{Sampel} & \textbf{\textit{Makespan}}\\ \hline $X(1)$ & 389052,25 & $X(4)$ & 389062,15\\ $X(2)$ & 389065,92 & $X(5)$ & 389055,68\\ $X(3)$ & 389064,29 & $X(6)$ & 890620,15\\ \hline \end{tabular} \end{table} kemudian sampel pada tabel 3 diurutkan dari yang terkecil hingga terbesar berdasarkan nilai \textit{makespan}. Sehingga, sampel $X(1)$ tetap karena memiliki nilai \textit{makespan} terkecil, sampel $X(5)$ akan menjadi sampel $X(2)$ dengan urutan pekerjaan $4-2-1-3$, sampel $X(4)$ akan menjadi sampel $X(3)$ dengan urutan pekerjaan $2-1-3-4$, sampel $X(6)$ akan menjadi sampel $X(4)$ dengan urutan pekerjaan $2-3-1-4$, sampel X(3) akan menjadi sampel X(5) dengan urutan pekerjaan $1-3-4-2$ dan sampel $X(2)$ akan menjadi sampel $X(6)$ dengan urutan pekerjaan $1-2-4-3$. Pengurutan sampel ini akan digunakan untuk tahap selanjutnya. Nilai $\rho$ telah ditentukan sebesar 0,01 maka jumlah sampel elit adalah $\lceil \rho\times N\rceil=\lceil 0,01\times 6\rceil=1$. Kemudian, diambil satu sampel elit dari sampel yang telah diurutkan yang memiliki nilai \textit{makespan} paling kecil. Sehingga, diperoleh sampel elit yaitu sampel $X(1)$. Karena proses ini merupakan iterasi pertama dan hanya terdapat 1 sampel elit, maka bobot sampel elit tersebut sebesar 1. Selanjutnya, dilakukan perhitungan nilai LFR. Berikut perhitungan nilai LFR menggunakan Persamaan (\ref{P6}), \[Fmaks = 1/X(1) = 0,00000257035 \,\text{dan}\, Fmin = 1/X(6) = 0,00000257026.\] Maka nilai LFR untuk ke 6 sampel adalah LFR $(1) = 0,00000257035$, LFR $(2) = 0,00000257033$, LFR $(3) = 0,00000257031$, LFR $(4) = 0,00000257029$, LFR $(5) = 0,00000257028$, dan LFR $(6) = 0,00000257026$. Proses \textit{update} parameter \textit{crossover} dilakukan dengan menghitung nilai $u=389052,52/(2\times 389052,52)=0.5$ maka diperoleh $P_c (2)= 0,8$. Jumlah sampel yang di elitisme sebanyak jumlah sampel elit. Karena pembobotan sampel elit bernilai 1. Maka, jumlah sampel yang di elitisme adalah 1, berdasarkan nilai makespan sampel yang paling minimum yaitu sampel $X(1)$. Sehingga sampel $X(1)$ terpilih sebagai sampel yang di elitisme. Pemilihan induk \textit{crossover} dilakukan dengan mengunakan mekanisme \textit{roulette wheel} berdasarkan nilai \textit{fitness} sampel. Pemilihan induk 1 diambil dari sampel elit yang memiliki nilai fungsi tujuan terkecil, berdasarkan proses elitisme sampel $X(1)= 3-4-1-2$ terpilih sebagai induk 1. Pemilihan induk 2 menggunakan nilai LFR dari sampel yang sedang dievaluasi. Apabila nilai perbandingan kumulatif LFR dan total LFR lebih besar dari bilangan acak yang dibangkitkan, maka sampel tersebut menjadi induk 2. Total LFR adalah 0,00001542182. Kumulatif LFR total dari setiap sampel,yaitu $X(1)= 0,166669595$, $X(2)= 0,333338018$, $X(3)= 0,500000527$, $X(4)= 0,666671351$, $X(5)= 0,833336261$, dan $X(6)= 1$. Selanjutnya bilangan acak yang dibangkitkan adalah 0,4851, dengan demikian nilai kumulatif LFR total untuk sampel $X(1)$ dan $X(2)$ kurang dari bilangan acak yang dibangkitkan. Sedangkan, untuk sampel $X(3)$, $X(4)$, $X(5)$ dan $X(6)$ memiliki nilai kumulatif LFR total yang lebih besar dari bilangan acak yang dibangkitkan. Sehingga, diperoleh sampel $X(1)$ sebagai induk 1 dari sampel elit karena memiliki nilai fungsi tujuan terbaik dari mekanisme elistisme. Sedangkan, sampel $X(3)$, $X(4)$, $X(5)$ dan $X(6)$ terpilih sebagai induk 2. Proses \textit{crossover} menggunakan metode 2-\textit{point order crossover}. Untuk mengetahui sampel yang mengalami \textit{crossover} maka dibangkitkan bilangan acak $(R)$. Jika $RP_c$ maka tidak dilakukan \textit{crossover}. bilangan acak $(R)$ yang dibangkitkan disajikan dalam Tabel 4 berikut, \begin{table}[!h] \caption{Pembangkitan bilangan $R$ penentuan \textit{crossover}}\label{T4} \centering \begin{tabular}{c c | c c} \hline \textbf{Sampel} & $R$ & \textbf{Sampel} & $R$\\ \hline $X(1)$ & 0,86113 & $X(4)$ & 0,54866\\ $X(2)$ & 0,58979 & $X(5)$ & 0,47786\\ $X(3)$ & 0,11668 & $X(6)$ & 0,59866\\ \hline \end{tabular} \end{table} Proses \textit{crossover} dilakukan pada sampel $X(3)$, $X(4)$, $X(5)$, dan $X(6)$, karena nilai $R$ dari sampel tersebut lebih kecil dari $P_c=0,8$. Sedangkan, sampel $X(2)$ tidak dilakukan \textit{crossover} karena tidak terpilih sebagai induk 2. Selanjutnya untuk menentukan bagian dari sampel induk yang akan di \textit{crossover}, yaitu dengan membangkitkan dua bilangan acak. Berikut \textit{crossover} untuk sampel $X(1)$ dengan sampel $X(3)$. Diperoleh dua bilangan acak $r_1=0,4899$ dan bilangan $r_2=0,6789$, maka $b_1=\lceil 0,4899\times 4\rceil = \lceil 1,9596\rceil =2$ dan $b_2=\lceil 0,6789\times 4\rceil = \lceil 2,7156\rceil=3$ sehingga $p_1=2$ dan $p_2=3$. \begin{verse} sampel induk $X(1) = 3-4-1-2$\\ sampel induk $X(3) = 1-2-4-3$ \end{verse} Selanjutnya pekerjaan yang terpilih tersebut ditukar antar sampel induk seperti berikut: \begin{verse} sampel baru $1 = \cdots-\cdots-\textbf{4}-\cdots$\\ sampel baru $2 = \cdots-\cdots-\textbf{1}-\cdots$ \end{verse} untuk mengisi titik-titik pada sampel baru 1, maka diperiksa satu persatu pekerjaan pada sampel $X(1)$. Jika terdapat pekerjaan pada sampel $X(1)$ yang belum tercantum pada sampel baru 1, maka pekerjaan tersebut akan mengisi titik-titik yang kosong. Hal tersebut dilakukan secara berurutan, sehingga sampel hasil crossover menjadi: \begin{verse} sampel baru $1 = 3-1-4-2$ mengantikan sampel $X(2)$ yang lama\\ sampel baru $2 = 4-3-1-2$ mengantikan sampel $X(3)$ yang lama. \end{verse} Kemudian evaluasi induk 2 lainnya dengan proses yang sama, yang memiliki nilai bilangan acak $(R)$ lebih kecil dari $P_c$. Setelah proses \textit{crossover} dilakukan, diperoleh sampel berikut, \begin{center} \begin{tabular}{c c c} $X(1) = 3-4-1-2$ & $X(3) = 4-3-1-2$ & $X(5) = 4-2-1-3$ \\ $X(2) = 3-1-4-2$ & $X(4) = 3-2-1-4$ & $X(6) = 3-2-1-4$ \end{tabular} \end{center} Proses mutasi dipilih dengan cara membangkitkan bilangan acak dan pekerjaan pada sampel akan ditukar dengan pekerjaan lainnya. Nilai parameter mutasi ditentukan dengan rumus sebagai berikut $P_m=P_c/2=0,8/2=0,4$. Jumlah sampel yang akan dimutasi adalah $Na=\lceil Pm \times N\rceil=\lceil 0,4\times 6\rceil=\lceil 2,4\rceil= 3$, sehingga ada 3 sampel yang mengalami proses mutasi. Untuk mengetahui sampel mana yang mengalami mutasi maka akan dibangkitkan bilangan acak $(R)$. Jika $R < P_m$ maka dilakukan proses mutasi, dan jika $R > P_m$ maka tidak dilakukan proses mutasi. Berikut sampel yang dimutasi pada Tabel 5, \begin{table}[!h] \caption{Penentuan sampel yang dimutasi}\label{T5} \centering \begin{tabular}{c c c l | c c c l} \hline \textbf{Sampel} & $R$ & $P_m$ & \textbf{Keterangan} & \textbf{Sampel} & $R$ & $P_m$ & \textbf{Keterangan}\\ \hline $X(1)$ & 0,1442 & & tetap & $X(4)$ & 0,2669 & 0,4 & dimutasi\\ $X(2)$ & 0,1442 & 0,4 & dimutasi & $X(5)$ & 0,3851 & 0,4 & dimutasi \\ $X(3)$ & 0,4591 & 0,4 & tidak dimutasi & $X(6)$ & 0,4782 & 0,4 & tidak dimutasi \\ \hline \end{tabular} \end{table} Selanjutnya melakukan proses mutasi pada sampel yang terpilih. Berikut ini diberikan proses mutasi pada sampel $X(2)$. Diketahui $n=4$ dan dua bilangan acak yang dibangkitkan $r_1=0,1979$ dan $r_2=0,9461$, maka $I=\lceil 4\times 0,1979\rceil =\lceil 0,7916\rceil = 1$ dan $J=\lceil 4\times 0,9461\rceil=\lceil 3,7844\rceil=4$. Kemudian membangkitkan nilai $r$ secara acak pada selang $[0,1]$ dan diperoleh nilai $r= 0,4132$. Sehingga nilai $K = \lceil 0,4132\times 3\rceil = \lceil 1,2396\rceil = 2$. Karena $K=2$, maka dilakukan pembalikan pada sampel $X(2)=3-1-4-2$, sehingga diperoleh sampel $X(2)$ yang baru, yaitu $3-2-4-1$. Proses mutasi pada sampel $X(4)$ dan sampel $X(5)$, dilakukan dengan langkah yang sama seperti proses mutasi sampel $X(2)$. Berikut sampel baru hasil mutasi, yaitu \begin{center} \begin{tabular}{c c c} $X(1) = 3-4-1-2$ & $X(3) = 4-3-1-2$ & $X(5) = 4-1-2-3$ \\ $X(2) = 3-2-4-1$ & $X(4) = 3-1-2-4$ & $X(6) = 3-2-1-4$ \end{tabular} \end{center} Setelah itu menghitung nilai \textit{makespan} (fungsi tujuan) dari sampel tersebut. Nilai \textit{makespan} dari sampel yang baru disajikan pada Tabel \ref{T6}. \begin{table}[!h] \caption{Nilai fungsi tujuan (\textit{makespan}) sampel baru}\label{T6} \centering \begin{tabular}{c c | c c} \hline \textbf{Sampel} & \textbf{\textit{Makespan}} & \textbf{Sampel} & \textbf{\textit{Makespan}}\\ \hline $X(1)$ & 389052,25 & $X(4)$ & 389063,06\\ $X(2)$ & 389107,16 & $X(5)$ & 389055,68\\ $X(3)$ & 389054,05 & $X(6)$ & 389063,06\\ \hline \end{tabular} \end{table} berdasarkan Tabel 6 diperoleh nilai \textit{makespan} terkecil pada iterasi pertama yaitu sebesar 389052,25. Proses iterasi dilakukan sampai kriteria pemberhentian terpenuhi. kriteria pemberhentian terpenuhi pada saat iterasi ke-31 dengan nilai $\varepsilon$ sebesar 0,00000007369, sedangkan nilai $\beta$ sebesar 0,0000001 sehingga $\varepsilon < \beta$ dan proses iterasi dihentikan. Pada Tabel 7 dapat dilihat hasil percobaan sebanyak 16 kali, dimana masing-masing penghitungan dilakukan sampai kriteria pemberhentian terpenuhi, \begin{table}[!h] \caption{Hasil urutan pekerjaan dengan Algoritma CEGA}\label{T7} \centering \begin{tabular}{c c c} \hline \textbf{No} & \textbf{Urutan pekerjaan} & \textbf{\textit{Makespan}}\\ \hline 1 & $3-4-1-2$ & 389052,25\\ 2 & $3-4-1-2$ & 389052,25\\ 3 & $3-4-1-2$ & 389052,25\\ 4 & $3-1-4-2$ & 389052,25\\ 5 & $3-4-1-2$ & 389052,25\\ 6 & $3-4-1-2$ & 389052,25\\ 7 & $2-1-4-3$ & 389052,97\\ 8 & $3-4-1-2$ & 389052,25\\ 9 & $3-4-1-2$ & 389052,25\\ 10 & $3-4-1-2$ & 389052,25\\ 11 & $3-1-4-2$ & 389052,25\\ 12 & $3-4-1-2$ & 389052,25\\ 13 & $3-4-1-2$ & 389052,25\\ 14 & $3-1-4-2$ & 389052,25\\ 15 & $3-4-1-2$ & 389052,25\\ 16 & $3-4-1-2$ & 389052,25\\ \hline \end{tabular} \end{table} berdasarkan Tabel 7, diperoleh urutan pekerjaan yang memiliki fungsi tujuan terkecil yaitu urutan pekerjaan $3-4-1-2$ dengan urutan pengerjaan produk BEST 47, produk BEST 20 SH, produk BEST 50 SH, produk BEST 47 A atau urutan pekerjaan $3-1-4-2$ dengan urutan pengerjaan produk BEST 47, produk BEST 50 SH, produk BEST 20 SH, produk BEST 47 A dengan nilai \textit{makespan} sebesar 389052,25 detik. \section{Kesimpulan} Berdasarkan pembahasan yang telah dilakukan, permasalahan penjadwalan \textit{flow shop} dapat diselesaikan dengan Algoritma CEGA. Pada penyelesaian permasalahan penjadwalan \textit{flow shop} di CV. Bestone Indonesia menggunakan Algoritma CEGA dengan nilai parameter yang digunakan yaitu $N$ sebanyak 6, $\rho$ sebesar 0,01, $P_{ps}$ sebesar 1, $\alpha$ sebesar 0,6 dan $\beta$ sebesar 0,000001 menghasilkan urutan pengerjaan produk BEST 47, produk BEST 20 SH, produk BEST 50 SH, produk BEST 47 A dan urutan pengerjaan produk BEST 47, produk BEST 50 SH, produk BEST 20 SH, produk BEST 47 A. Nilai \textit{makespan} paling minimum yang diperoleh yaitu sebesar 389052,25 detik atau 108,09 jam dengan kriteria pemberhentian $\varepsilon$ sebesar 0,00000007369 . %\section{Ucapan Terima kasih} %Tuliskan ucapan terima kasih kepada pihak-pihak yang telah membantu dalam penulisan makalah ini (\textbf{tanpa gelar}). \begin{thebibliography}{0} \bibitem{A1} Ginting, R., 2009, \emph{Penjadwalan Mesin}, Graha Ilmu, Yogyakarta \bibitem{A2} Haming, M. dan Nurnajamuddin, M., 2014, \emph{Manajemen Produksi Modern Operasi Manufaktur dan Jasa, Buku 2}, Cahaya Prima Sentosa, Jakarta \bibitem{A3} Arkeman, Y., Seminar, B., dan Gunawan, H., 2012,\emph{Algoritma Genetika Teori dan Aplikasinya untuk Bisnis dan Industri}, IPB Press, Bogor \bibitem{A4} Kurniawati, A. dan Karim, S., 2016, Penjadwalan Produksi Flow Shop dengan Metode Ignal-Scharge dan Algoritma Nawaz, Enscore dan Ham (NEH) di CV. Bestone Indonesia,\emph{urnal Sains, Teknologi dan Industri}, \textbf{13}: 229 -- 241 \bibitem{A5} Widodo, S., Santoso, B. dan Siswanto, E., 2014. Pendekatan Algoritma Cross Entropy–Genetic Algorithm untuk Menurunkan Makespan Pada Penjadwalan Flow Shop,\emph{JEMIS}, \textbf{2}: 41 -- 49 \bibitem{A6} Nurkhalida, L. dan Santosa, B., 2012, \emph{Pendekatan Algoritma Cross Entropy–Genetic Algorithm Pada Permasalahan Multi Objective Job Shop Scheduling}, (serial online) Available at: https//www.researchgate.net/publication/267976436-pendekatan-cross-entropy-genetic-algorithmn-pada-permasalahan-multi-objective-job-shop-scheduling. Pdf, (14 Mei 2021) \bibitem{A7} Syarif, A., 2014, \emph{Algoritma Genetika Teori dan Aplikasi}, Edisi ke-2, Graha Ilmu, Yogyakarta \bibitem{A8} Boer, D., Kroese, D.P., Mannor, S., and Rubinstein, R.Y., 2005, A tutorial on the Cross-Entropy Method,\emph{Annals of Operations Research}, \textbf{134}: 19 -- 67 \bibitem{A9} Bashori, H.,Pratikto, dan Sugiono, 2015, Penjadwalan \textit{Flow Shop} dengan Penerapan Algoritma \textit{Cross Entropy-Genetic Algorithm} (CEGA) untuk Meminimasi \textit{Makespan}, \emph{JEMIS}, \textbf{3}: 35 -- 42 \bibitem{A10} Muharni, Y., Saeful M, A. I., dan Rubyanti, T. E., 2019, Penjadwalan \textit{Flow Shop} Mesin Paralel Menggunakan Metode \textit{Longest Processing Time} dan \textit{Cross Entropy-Genetic Algorithm} Pada Pembuatan Produk Steel Bridge B-60, \emph{Jurnal Ilmiah Teknik Industri},\textbf{7}: 213 -- 225 \bibitem{A11} Bahsori, H, 2015, Upaya Meminimasi \textit{Makespan} dengan Penerapan Algoritma \textit{Cross Entropy} Pada Penjadwalan \textit{Flow Shop}, \emph{Widya Teknika}, \textbf{23}: 10 -- 14 \bibitem{A12} Alfandianto, A., Nugroho, y. A., dan Setiafindari, W., 2017, Penjadwalan Produksi Menggunakan Pendekatan Algoritma Genetika di PT Pertani (PERSERO) Cabang D.I Yogyakarta, \emph{Jurnal DISPROTEK}, \textbf{2}: 1 -- 7 \bibitem{A13} Suprayogi, D. A., dan Mahmudy, W. F., 2014, Penerapan Algoritma Genetika \textit{Traveling Salesman Problem with Time Window}, \emph{Jurnal Buana Informatika}, \textbf{6}: 121 -- 130 \bibitem{A14} Utama, D. M., Ardiansyah, L. R., dan Garside, A. K., 2019, Penjadwalan \textit{Flow Shop} untuk Meminimasi \textit{Total Tardiness} Menggunakan Algoritma \textit{Cross Entropy-Genetic Algorithmn}, \emph{Jurnal Optimasi Sistem Industri}, \textbf{18}: 133 -- 141 \bibitem{A15} Saputro, N., dan Yento, 2004, Pemakaian Algoritma Genetik untuk Penjadwalan \textit{Jop Shop Dinamis Non Deterministik}, \emph{Jurnal Teknik Industri}, \textbf{6}: 61 -- 70 \end{thebibliography} \end{document}