## EULER: Jurnal Ilmiah Matematika, Sains dan Teknologi
Journal Homepage: http://ejurnal.ung.ac.id/index.php/Euler DOI: https://doi.org/10.34312/euler.v10i2.14488 Desember 2022, Vol. 10, No. 2, Hal. 292-302

## Critical Path Method dan Algoritma Genetika untuk Optimasi Durasi dan Biaya Pembangunan
Wahdania A.T. Ja’a 1 , Muhammad Rifai Katili 2 , Djihad Wungguli 1 *, Nisky Imansyah Yahya 1
1 Jurusan Matematika, Universitas Negeri Gorontalo, Bone Bolango 96554, Indonesia
2 Jurusan Teknik Informatika, Universitas Negeri Gorontalo, Bone Bolango 96554, Indonesia
*Penulis Korespondensi. Email: djihad@ung.ac.id

## Abstrak
Suatu  proyek  yang  besar  memerlukan  penjadwalan  yang  tepat  untuk  memperoleh  durasi pembangunan serta biaya yang optimal. Optimalisasi merupakan proses pengajuan durasi proyek untuk  mendapatkan  solusi  yang  efisien  dengan  menggunakan  berbagai  alternatif  yang  dapat ditinjau dari segi biaya serta waktu. Dipilih Critical Path Method dan Algoritma Genetika sebagai metode yang efektif untuk merencanakan serta mengendalikan jadwal adalah Critical Path Method , karena  metode  ini mempertimbangkan  asumsi  waktu  maka  pelaksanaan  proyek  dilakukan  tanpa memikirkan  sumber  daya  dan  juga  bisa  menentukan  kapan  suatu  kegiatan  dimulai  dan  kapan berakhirnya  proyek.  Sedangkan  metode Algoritma  Genetika merupakan  metode  yang  dapat memberikan  hasil  yang  cepat  dan  efisien  dalam  membentuk  jadwal  proyek.  Berdasarkan  hasil penelitian  diperoleh  bahwa  telah  berhasil  mendapatkan  Nilai  optimasi  dengan  meminimalkan durasi proyek menggunakan CPM (Critical Path Method) adalah 199 hari dari total waktu proyek pembangunan puskesmas biau 210 hari kerja. dan biaya yang timbul karena adanya optimalisasi tersebut menggunakan Algoritma Genetika sebesar Rp. 231.515.082 dari biaya awal proyek sebesar Rp.382.784.000.
Kata Kunci: Optimasi; Critical Path Method; Algoritma Genetika

## Abstract
A  large  project  requires  proper  scheduling  to  obtain  the  duration  of  development  and  costs incurred more optimally. Optimization is submitting the project duration efficient solution by using various alternatives that can be reviewed in terms of cost and time. Optimization problems can be solved  using  operating  research.  Selected  Critical  Path  Method  and  Genetic  Algorithm  as  a compelling method for planning and an methods rolling schedules the Critical Method because this method considers the assumption of time, then the implementation of the project is done without thinking about resources and can also determine when an activity starts and when the end of the project. While the Genetic Algorithm method is a method that can provide quick and efficient results in forming a project schedule. Based on the results of the study obtained that has managed to get the optimization value by minimizing the duration of the project using CPM (Critical Path Method) is 199 days from the total project time of the construction of the health center Biau 210 working days.  and  the  costs  incurred  due  to  the  optimization  using  genetic  algorithms  amounted  to  Rp. 231,515,082 from the initial cost of the project of Rp.382,784,000.
Keywords: Optimization; Critical Path Method; Genetic Algorithms

## 1. Pendahuluan
Perkembangan  teknologi  dan  ilmu  pengetahuan  mendorong  perkembangan  dibidang pembangunan.  Suatu  proyek  yang  besar  tentu  saja  memerlukan  penjadwalan  yang  tepat  untuk memperoleh  durasi  pembangunan  serta  biaya  yang  dikeluarkan  lebih  optimal.  Optimalisasi merupakan proses pengajuan durasi proyek untuk mendapatkan solusi yang efisien (optimal) dengan menggunakan berbagai alternatif yang dapat ditinjau dari segi biaya serta waktu. Masalah optimasi dapat diselesaikan menggunakan riset operasi. Riset operasi merupakan metode untuk merumuskan
permasalahan serta memformulasikan baik pada bisnis, sosial, ekonomi maupun bidang lainnya ke dalam pemodelan matematis agar dapat memperoleh solusi yang optimal [1]. Salah satu permasalahan yang biasanya diselesaikan dengan riset operasi adalah masalah proyek pembangunan suatu gedung.
Pada  pembangunan  Gedung  diperlukan  adanya  suatu  penanganan  manajemen  penjadwalan yang  baik,  karena  penjadwalan  kerja  membutuhkan  perhitungan  yang  cermat  sehingga  perlu ditangani dengan teliti. Sebuah proyek dikatakan berhasil jika penyelesaian efisien dilihat dari kerja yang efektif baik bagi pekerja ataupun alat yang digunakan [2]. Keterlambatan penyelesaian proyek merupakan masalah yang sering muncul dan berdampak pada keseluruhan pekerjaan proyek. Untuk mengantisipasi  keterlambatan  tersebut,  maka  dilakukan  dengan  beberapa  alat  pengendalian  [3]. Dalam suatu proyek sangat diperlukan optimalisasi untuk estimasi durasi waktu dan biaya yang harus dikeluarkan. Optimalisasi dilakukan untuk mengurangi kendala untuk mendapatkan hasil yang efisien dari sumber daya yang dioptimalkan.
Dari  hasil  wawancara  yang  dilakukan  dengan  konsultan  proyek  Puskesmas  Biau  Kabupaten Gorontalo  Utara,  diketahui  perencanaan waktu  pembangunan  proyek  tidak  bisa  dipastikan  apakah selesai  dengan  waktu    yang  sudah  ditentukan,  karena  dalam  pelaksanaan  pengerjaan  proyek  tidak terlepas  dari  kendala  keterlambatan  waktu  yang  dialami  proyek  pada  umumnya,  Sehingga pelaksanaan  pengerjaan  proyek  pembangunan  Puskesmas  Biau  ini  konsultan  melihat  faktor  yang menyebabkan  keterlambatan  sebuah  proyek.  Adapun  faktor  yang  menyebabkan  keterlambatan proyek yaitu keterlambatan terkait material, keterlambatan terkait tenaga kerja, keterlambatan terkait peralatan, perencanaan yang tidak sesuai, kurangnya personil secara teknikal, dan pelaksanaan kerja yang  tidak  sesuai  dengan  metode.  Hal  ini  menyebabkan  tidak  bisa  ditentukan  kapan  berakhirnya pembangunan proyek tersebut.  Oleh karena itu dibutuhkan suatu solusi yang dapat menyelesaikan permasalahan  tersebut.  Beberapa  metode  yang  digunakan  untuk  menyelesaikan  persoalan perencanaan proyek diantaranya Critical Path Method .
Critical Path Method (CPM) pada dasarnya adalah merupakan metode yang berorientasi pada waktu, dalam arti bahwa CPM akan berakhir pada penentuan waktu. Metode  ini mengidentifikasi jalur  kritis pada  aktivitas  yang  ditentukan  ketergantungan antar aktifitasnya [4]. Jalur Kritis adalah suatu deretan kegiatan kritis yang menentukan jangka waktu penyelesaian bagi keseluruhan proyek [5].  Sedangkan  aktifitas  merupakan  tugas  spesifik  yang  mempunyai  hasil  yang  dapat  diukur  dari durasi pengerjaannya [6]. Beberapa penelitian  mengenai CPM  yang pernah dilakukan sebelumnya diantaranya dilakukan Ulfa et.al . [7]. Penelitian ini dilakukan untuk mengetahui jaringan kerja atau network jalur kritis, mengetahui waktu yang optimal, serta menganalisis perkiraan total biaya pada proyek dengan menggunakan metode CPM. Penelitian lainnya dilakukan Ilwaru et.al . [8], penelitian ini dilakukan untuk mengetahui jalur kritis yang di dalamnya terdapat aktivitas-aktivitas kritis dan membandingkan penjadwalan waktu antara waktu kerja yang di jadwalkan pemilik proyek dan waktu kerja yang di jadwalkan dengan metode CPM. Wibowo et.al . [9] melakukan penelitian CPM dengan memodelkan semua mata kuliah dalam bentuk jaringan yang saling terhubung. Dalam pendekatan ini, durasi waktu tempuh semua mata kuliah sudah diketahui. Setelah input penjadwalan selesai, dapat dibuat sebuah bagan jaringan antar mata kuliah.
Selain penelitian yang hanya menggunakan metode CPM, terdapat beberapa penelitian yang menggunakan kombinasi CPM dengan metode lainnya diantaranya dilakukan Safitri et. al. [10] yang menggunakan  metode  CPM  dan Precedence  Diagram  Method untuk  menyelesaikan  optimasi penjadwalan proyek. Hasil penelitian didapatkan waktu yang efisien dan biaya yang lebih optimal. Muzdalifah et.  al. [11]  melakukan  penelitian  untuk  mengembangkan  penjadwalan  proyek  yang realistis  dengan  mengintegrasikan  dua  komponen  proyek,  yaitu  optimasi  waktu  dan  biaya  harian. Metode yang digunakan merupakan kombinasi dari metode CPM dan Cuckoo Search . Sa’adah et.al . [12] menggunakan metode CPM yang digunakan untuk menganalisis lintasan kritis yang fokus pada pekerjaan struktur beton dan menggunakan metode Crashing untuk mengetahui perbandingan biaya dan waktu akibat adanya percepatan ( crashing ).
Berdasarkan  uraian  di  atas,  dalam  artikel    ini  akan  dilakukan  kombinasi  metode  CPM  dan Algoritma  Genetika  untuk  masalah  optimasi  penjadwalan  proyek  Pembangunan  Puskesmas  Biau Kabupaten Gorontalo Utara. Penelitian ini untuk mengetahui durasi proyek yang optimal dan biaya yang timbul karena adanya optimalisasi tersebut. Metode CPM digunakan untuk merencanakan serta mengendalikan  jadwal  karena  metode  ini  mempertimbangkan  asumsi  waktu  maka  pelaksanaan proyek  dilakukan tanpa  memikirkan  sumber  daya.  Selain  itu  CPM  dapat  menentukan  kapan  suatu kegiatan  dimulai  dan  kapan  berakhirnya  proyek.  Sedangkan  metode  Algoritma  Genetika dimaksudkan  untuk  memberikan  hasil  yang  cepat  dan  efisien  dalam  membentuk  jadwal  proyek. Tujuan dua metode ini digunakan untuk menentukan durasi serta biaya proyek yang lebih optimal, selain itu juga dapat mengkoordinasi dan mengontrol penyelesaian proyek dengan biaya yang lebih optimal serta jangka waktu yang efisien.

## 2. Metode Penelitian
Penelitian  ini  merupakan  penelitian  kuantitatif  dengan  studi  kasus  proyek  pembangunan Puskesmas Biau Kabupaten Gorontalo Utara. Penelitian ini dilakukan dengan tahapan pertama adalah merumuskan masalah yang akan diteliti, mempelajari referensi, setelah itu dilakukan pengumpulan data dan mengolah data menggunakan Critical Path Method dan Algoritma Genetika.  Data diolah menggunakan Critical  Path  Method untuk  mencari  durasi  optimal  dan  Algoritma  Genetika menentukan  biaya  dari  optimalisasi  durasi.  Data  yang  digunakan  dalam  penelitian  ini  yaitu  data primer yang diperoleh dari konsultan proyek puskesmas Biau Kabupaten Gorontalo Utara. Adapun data yang didapatkan dari proyek yaitu variabel durasi dan biaya proyek. Tahapan dalam CPM yang pertama  ialah  membuat  diagram  jaringan  setelah  diagram  jaringan  terbentuk  kemudian  hubungan antar simbol dan urutan kegiatan untuk mendapatkan jalur kritis dari kegiatan proyek tersebut dan mencari  tenggang  waktu  kegiatan  untuk  memperoleh  durasi  optimal  dari  pengerjaan  proyek. Sedangkan tahapan Algoritma Genetika yaitu input data merupakan tahapan awal dari olah data AG, setelah input data dibangkitkan populasi awal, crossover , dan masuk tahapan mutasi serta mencari nilai fitness terbaik dan kromosom terbaik untuk mendapatkan biaya optimal dari pengerjaan proyek tersebut.

## 3. Hasil dan Pembahasan
Sistem  ini  menghasilkan  sebuah  penjadwalan  proyek  dengan  mengoptimasi  penjadwalan proyek  dengan  menggunakan Critical  Path  Method dan  Algoritma  Genetika  dalam  menentukan durasi  proyek  yang  optimal  dan  biaya  yang  timbul  karena  adanya  optimalisasi.  Perhitungan  dari sistem  yang  dilakukan  pada  penelitian  ini  menggunakan  data  kegiatan,  durasi,  dan  biaya  proyek Pembangunan Puskesmas Biau. Data tersebut dapat dilihat pada Tabel 1.
Tabel 1 .Kegiatan, durasi, dan biaya proyek pembangunan puskesmas Biau
Simbol kegiatan Uraian kegiatan Durasi (hari) Kegiatan pendahulu Biaya per kegiatan (RP) A Penimbunan 13 - 50.500.000 B Pemadatan Timbunan 3 A 2.700. 000 C Bowplank 2 A 740. 000 D Pondasi 8 B 22.800. 000 E Sloof 7 C 12.915. 000 F Tiang Kolom K250 4 D 5.100. 000 G Naik Bata& Kolom Praktis 14 E, F 39.900. 000 H Ring Balok 5 G 7.725. 000 I Plesteran Aci 12 G 18.017. 000 J Pemasangan Rangka baja Ringan dan Penutup 9 H, I 25.500. 000 K Pemasangan Keramik Dinding 4 J 3.600. 000
Simbol kegiatan Uraian kegiatan Durasi (hari) Kegiatan pendahulu Biaya per kegiatan (RP) L Pemasangan Keramik Lantai 10 K 14.700. 000 M Pemasangan Plafond/Gypsum 13 L 10.725. 000 N Instalasi Jaringan Listrik 6 M 8.640. 000 O Penataan Halaman Dalam 7 N 3.780. 000 P Pemasangan Kusen & Daun Jendela 18 O 8.892. 000 Q Instalasi Air Kotor 6 P 1.885. 000 R Instalasi Air Bersih 4 Q 1.900. 000 S Pengecetan Luar Dalam 13 R 8.125. 000 T Pekerjaan Tembok Bata Pagar 10 S 22.000. 000 U Pekerjaan Kangsting 3 T 840. 000 V Pemasangan Paving 14 U 21,300. 000 W Pekerjaan Rumah Mesin 8 V 4.840. 000 X Pekerjaan Sumur Bor 1 W 6.000. 000 Y Pemasangan ACP,Logo Dan Tulisan Nama 4 X 17.500. 000 Z Pekerjaan Logo Pagar Besi Dan Pintu Gerbang 6 Y 5.980. 000 AA Pekerjaan pagar Kawat Duri 4 Z 1.880. 000 AB Pembersihan 2 AA 300. 000

## 3. 1 Optimasi Menggunakan CPM
Data  yang  digunakan  dalam  penelitian  ini  yaitu  jadwal  kegiatan  dan  durasi  aktivitas.  Data tersebut diperoleh dari data primer yang didapatkan langsung dari wawancara konsultan proyek dan observasi  langsung  dilapangan.  Untuk  memudahkan  dalam  menggambarkan  jaringan  kerja,  maka setiap  aktivitas  dapat  diurutkan  berdasarkan  waktu  penyelesaian  kegiatan.  Selain  itu  pembuatan jaringan  kerja  menggunakan  metode  CPM  yang  menggambarkan  hubungan  antara  komponen- komponen  kegiatan  serta  menjelaskan  arus  proyek  dari  awal  suatu  kegiatan  dimulai  hingga berakhirnya atau terselesaikannya proyek tersebut. Untuk data durasi waktu dan urutan kegiatan dapat dilihat pada Tabel 2.
Tabel 2 Data urutan kegiatan No Uraian kegiatan Aktivitas Durasi (hari) Kegiatan pendahulu Biaya per kegiatan (RP) 1 Penimbunan A 13 - 50.500.000 2 Pemadatan Timbunan B 3 A 2.700. 000 3 Bowplank C 2 A 740. 000 4 Pondasi D 8 B 22.800. 000 5 Sloof E 7 C 12.915. 000 6 Tiang Kolom K250 F 4 D 5.100. 000 7 Naik Bata& Kolom Praktis G 14 E, F 39.900. 000 8 Ring Balok H 5 G 7.725. 000 9 Plesteran Aci I 12 G 18.017. 000 10 Rangka baja Ringan dan Penutup J 9 H, I 25.500. 000 11 Pemasangan Keramik Dinding K 4 J 3.600. 000 12 Pemasangan Keramik Lantai L 10 K 14.700. 000 13 Pemasangan Plafond/Gypsum M 13 L 10.725. 000 14 Instalasi Jaringan Listrik N 6 M 8.640. 000 15 Penataan Halaman Dalam O 7 N 3.780. 000 16 Pemasangan Kusen & Daun Jendela P 18 O 8.892. 000 17 Instalasi Air Kotor Q 6 P 1.885. 000
No Uraian kegiatan Aktivitas Durasi (hari) Kegiatan pendahulu Biaya per kegiatan (RP) 18 Instalasi Air Bersih R 4 Q 1.900. 000 19 Pengecetan Luar Dalam S 13 R 8.125. 000 20 Pekerjaan Tembok Bata Pagar T 10 S 22.000. 000 21 Pekerjaan Kangsting U 3 T 840. 000 22 Pemasangan Paving V 14 U 21,300. 000 23 Pekerjaan Rumah Mesin W 8 V 4.840. 000 24 Pekerjaan Sumur Bor X 1 W 6.000. 000 25 ACP,Logo Dan Tulisan Nama Y 4 X 17.500. 000 26 Logo Pagar Besi & Pintu Gerbang Z 6 Y 5.980. 000 27 Pekerjaan pagar Kawat Duri ZZ 4 Z 1.880. 000 28 Pebersihan AB 2 AA 300. 000
Pada  Tabel  2  menunjukan  urutan  kegiatan,  durasi  waktu  dan  kegiatan  yang  mendahului  untuk selanjutnya akan membentuk jaringan kerja seperti yang terlihat pada Gambar 1.

## Gambar 1. Jaringan Kerja
Mengacu  pada  jaringan  kerja  seperti  Gambar  1,  maka  langkah  selanjutnya  adalah  dengan melakukan  perhitungan  maju  dan  perhitungan  mundur,  perhitungan  maju  dilakukan  untuk mengetahui Earliest  Start (ES)  dan Earliest  Finish (EF).  Sedangkan  perhitungan  mundur  akan mengetahui Lates Start (LS) dan Lates Finish (LF). Adapun rumus untuk menghitung adalah sebagai berikut:

## 𝐸𝑆(𝑛 + 1) = 𝐸𝑆 +  𝐷𝑢𝑟𝑎𝑠𝑖
Setelah diketahui nilai ES, EF, LS dan LF pada masing-masing kegiatan, maka selanjutnya akan mencari Free Float (FF) dan Total Float (TF) untuk mengetahui kegiatan kritis. Adapun rumus untuk menghitung adalah:

## 𝐹𝐹 = 𝐸𝐹 − 𝐸𝑆 − 𝐷
Langkah  selanjutnya menetukan suatu kegiatan yang termasuk kedalam kegiatan kritis, yaitu apabila nilai FF dan TF adalah nol. Kegiatan yang termasuk jalur kritis dapat dilihat pada Tabel 3 dan Gambar 2.
Tabel 3. Hasil analisa jalur kritis (CPM)
Uraian kegiatan Durasi (hari) Kegiatan pendahulu Early Lates Float/Slack KET ES EF LS LF FF TF Penimbunan 13 - 0 13 0 13 0 0 Kritis Pemadatan Timbunan 3 A 13 16 13 16 0 0 Kritis Bowplank 2 A 13 15 25 27 12 12 Tidak Kritis Pondasi 8 B 16 24 18 24 0 0 Kritis Sloof 7 C 24 31 24 31 0 0 Kritis Tiang Kolom K250 4 D 15 19 27 31 12 12 Tidak Kritis Naik Bata& Kolom Praktis 14 E, F 31 45 31 45 0 0 Kritis Ring Balok 5 G 45 50 52 57 7 7 Tidak Kritis Plesteran Aci 12 G 45 57 45 57 0 0 Kritis Rangka baja Ringan dan Penutup 9 H, I 57 68 57 66 0 0 Kritis Pemasangan Keramik Dinding 4 J 66 70 66 70 0 0 Kritis Pemasangan Keramik Lantai 10 K 70 80 70 80 0 0 Kritis Pemasangan Plafond/Gypsum 13 L 80 93 80 93 0 0 Kritis Instalasi Jaringan Listrik 6 M 93 99 93 99 0 0 Kritis Penataan Halaman Dalam 7 N 99 106  99 106 0 0 Kritis Pemasangan Kusen & Daun Jendela 18 O 105  124  105  124 0 0 Kritis Instalasi Air Kotor 6 P 124  130  124  130 0 0 Kritis Instalasi Air Bersih 4 Q 130  134  130  134 0 0 Kritis Pengecetan Luar Dalam 13 R 134  147  134  147 0 0 Kritis Pekerjaan Tembok Bata Pagar 10 S 147  157  147  157 0 0 Kritis Pekerjaan Kangsting 3 T 157  160  157  160 0 0 Kritis Pemasangan Paving 14 U 160  174  160  174 0 0 Kritis Pekerjaan Rumah Mesin 8 V 174  182  174  182 0 0 Kritis Pekerjaan Sumur Bor 1 W 182  183  182  183 0 0 Kritis Pasangan ACP Logo & tulisan nama 4 X 183  187  183  187 0 0 Kritis Logo Pagar Besi Dan Pintu Gerbang 6 Y 187  193  187  193 0 0 Kritis Pekerjaan pagar Kawat Duri 4 Z 193  197  193  197 0 0 Kritis Pebersihan 2 AA 197  199  197  199 0 0 Kritis
Gambar  2  menunjukkan  bahwa  dengan  durasi  proyek  199  hari  waktu  kegiatan.  Dan menunjukkan nilai slack setiap simbol kegiatan. Nilai slack nol (0) merupakan nilai dari ES–LS= 0, dimana  nilai  itu  menunjukkan  jalur  kritis.  Sehingga  jalur  kritisnya  adalah  1–2–4–6-8-28.  Dalam pelaksanaan proyek pembangunan Puskesmas Biau Kabupaten Gorontalo Utara terdapat jalur kritis pada  beberapa  aktivitas  kegiatan.  Adapun  yang  termasuk  pada  lintasan  kritis  yaitu  aktivitas Penimbunan,  Pemadatan  Timbunan,  Pondasi,  Sloof,  Naik  Bata&  Kolom  Praktis,  Plesteran  Aci, pemasangan keramik dinding, pemasangan keramik lantai, Pemasangan Plafond/Gypsum, Instalasi
Jaringan  Listrik,  Penataan  Halaman  Dalam,  Pemasangan  Kusen  dan  Daun  Jendela,  Instalasi  Air Kotor,  Instalasi  Air  bersih,  Pengecetan  Luar  Dalam,  Pekerjaan  Tembok  Bata  Pagar,  Pekerjaan Kangsting,  Pemasangan  Paving,  Pekerjaan  Rumah  Mesin,  Pekerjaan  Sumur  Bor,  Pemasangan ACP,Logo  Dan  Tulisan  Nama,  Pekerjaan  Logo  Pagar  Besi  Dan  Pintu  Gerbang,  Pekerjaan  pagar Kawat  Duri,  dan  aktivitas  pembersihan. Dari  Tabel  3,  dapat  diketahui  aktivitas  yang  termasuk  ke dalam jalur kritis pada kegiatan A, B, D, E, G, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, Z,Y, Z, ZZ, AB=13+3+8+7+14+12+9+4+10+13+6+7+18+6+4+13+10+3+14+8+1+4+6+4+2= 199 hari.
Gambar 2. Jalur kritis

## 3.2 Optimasi Menggunakan Algoritma Genetika
Algoritma  Genetika  adalah  algoritme  pencarian  yang  didasarkan  pada  mekanisme  seleksi alamiah  dan  genetika  alamiah  [13].  Solusi  awal  metode  Algoritma  Genetika  dimulai  dengan pengambilan sejumlah populasi secara random. Hasil random awal akan menjadi induk dari proses generasi  selanjutnya.  Jika  suatu  individu  memenuhi  persyaratan  dalam  menjalani  proses  evolusi, maka  individu  yang  mencapai  tujuan  tersebut  akan  mempunyai  kesempatan  lebih  untuk  dipilih menjadi individu terbaik. Sedangkan individu yang tidak sesuai akan dibuang atau diabaikan [14]. Untuk menghasilkan suatu solusi optimal, Algoritma Genetika melakukan proses pencarian diantara sejumlah  alternatif  titik  optimal  berdasarkan  fungsi  probabilistic  [15].  Berikut  tahapan  dalam optimasi dalam Algoritma Genetika.
1. Input Data
Pada proses ini dilakukan pendataan data. Pada optimasi penjadwalan proyek maka input data dapat berupa jenis-jenis kegiatan beserta hubungan ketergantungan antara jenis kegiatan, waktu dan biaya yang diperlukan untuk menyelesaikan pekerjaan tersebut yang disajikan pada Tabel 1.
2. Populasi Awal
Populasi  awal  merupakan  kumpulan  solusi  acak.  Populasi  awal  adalah  kumpulan  awal  dari beberapa  kromosom  yang  di  harapkan  nanti  akan  menghasilkan  suatu  kromosom  baru  yang merupakan  solusi  yang  efisien.  Pada  kasus  penjadwalan  proyek  kromosom  dapat  berupa  jaringan kerja proyek.
Dari  Tabel  4.  Kromosom  merupakan  urutan  jenis  kegiatan  dari  penjadwalan  proyek,  dan kromosom dibentuk oleh sejumlah gen dimana gen tersebut merupakan waktu suatu kegiatan dalam pelaksanaan proyek seperti   kromosom 1 terdiri dari kumpulan gen X1, X2, X128 berisi bilangan
bulat positif yang merupakan saat pelaksanaan kegiatan proyek. Pada kromosom 1 dapat dijelaskan bahwa gen X1 mempunyai nilai 1 menunjukkan bahwa kegiatan A dilaksanakan pada minggu ke 1, gen  X7  mempunyai  nilai  2  menunjukan  bahwa  kegiatan  J  dilaksanakan  pada  minggu  ke  14,  dan seterusnya sampai dengan gen X28 yang mempunyai nilai 30 yang menunjukan bahwa kegiatan AB dilaksanakan pada minggu ke 30.
Tabel 4. Inisialisasi populasi awal Kromosom X1  X2  X3  X4  X5  X6  X7  X8  X9  X10  …  X26  X27  X28 Kromosom1 2 2 3 5 6 6 8 9 11 14 28 30 30 Kromosom2 2 2 3 5 6 6 8 9 11 14 28 30 30 Kromosom3 2 2 3 5 6 6 8 9 11 14 28 30 30 Kromosom4 2 2 3 5 6 6 8 9 11 14 28 30 30 Kromosom5 2 2 3 5 6 6 8 9 11 14 28 30 30 Kromosom6 2 2 3 5 6 6 8 9 11 14 28 30 30 Kromosom7 2 2 3 5 6 6 8 9 11 14 28 30 30 Kromosom8 2 2 3 5 6 6 8 9 11 14 28 30 30 Kromosom9 2 2 3 5 6 6 8 9 11 14 28 30 30 Kromosom10 2 2 3 5 6 6 8 9 11 14 28 30 30

## 3. Menentukan nilai fitness
Proses ini dilakukan dengan memperhatikan aturan yang telah ditetapkan sebelumnya. Setiap kromosom akan diperiksa satu persatu dan dibandingkan dengan kromosom lainnya sesuai dengan aturan. Pembentukan susunan kromosom pada suatu populasi baru dilakukan dengan menggunakan metode  seleksi roulette-wheel .  Langkah  pertama  metode  ini  adalah  menghitung  total  nilai fitness seluruh kromosom seperti pada Tabel 5.
Tabel 5 . Total nilai fitness Kromosom Nilai Fitness 1 0.25 2 0.5 3 0.25 4 0.5 5 0.25 6 0.2 7 0.5 8 0.25 9 0.2 10 0.2 Total Nilai Fitness 3.10
Langkah kedua adalah menghitung probabilitas setiap kromosom atau urutan kegiatan proyek dengan  cara  membagi  nilai  fitness  tiap  kromosom  dengan  total  nilai fitness .  Sehingga  didapatkan hasil seperti pada Tabel 6.
Tabel 6. Probabilitas tiap kromosom Kromosom Probabilitas 1 0.25/ 3.10 = 0.081 2 0.5 / 3.10 = 0.161 3 0.25 / 3.10 = 0.081 4 0.5  / 3.10 = 0.161 5 0.25 / 3.10 = 0.081 6 0.2  / 3.10 = 0.065
Kromosom Probabilitas 7 0.5  / 3.10 = 0.161 8 0.25 / 3.10 = 0.081 9 0.2  / 3.10 = 0.065 10 0.2  / 3.10 = 0.065 Total 1
Langkah ketiga adalah menempatkan masing-masing kromosom atau urutan kegiatan proyek pada interval nilai  [0-1] seperti pada Tabel 7.
Tabel 7. Kromosom interval Kromosom Interval Nilai Kromosom Interval Nilai 1 0 – 0.081 6 0.406 – 0.486 2 0.082 – 0.162 7 0.487 – 0.567 3 0.163 – 0.243 8 0.568 – 0.648 4 0.244 – 0.324 9 0.729 – 0.810 5 0.325 – 0.405 10 0.811 – 0.891
Untuk menentukan susunan populasi baru hasil seleksi maka dibangkitkan bilangan acak antara [0-1].  Dimisalkan  bilangan  yang  dibangkitkan  adalah  [0.25;0.1;0.35;0.5;0.75;0.6;0.9;0.65].seperti yang terlihat pada Tabel 8.
Tabel 8. Panjang Kromosom Kromosom X1  X2  X3  X4  X5  X6  X7  X8  X9  X10  X26  X27  X28 Kromosom1 2 2 3 5 6 6 8 9  11 14 28 30 30 Kromosom2 2 2 3 5 6 6 8 9  11 14 28 30 30 Kromosom4 2 2 3
5 6 6 8 9  11 14 28 30 30
4. Crossover (Pindah Silang)
Pindah  silang (CrossOver) digunakan  sebagai  metode  pemotongan  kromosom  secara  acak (random). Metode pindah silang yang paling umum digunakan adalah pindah silang  satu  titik  potong ( one-point acak (random) , kemudian bagian pertama dari kromosom induk 1 digabungkan dengan bagian kedua dari kromosom induk 2. Bilangan acak (random) yang dibangkitkan untuk menentukan posisi titik potong adalah [1-N] dimana N merupakan banyaknya jumlah gen dalam satu kromosom seperti pada Tabel 9.
Tabel 9 . Kromosom induk Kromosom X1  X2  X3  X4  X5  X6  X7  X8  X9  X10  X26  X27  X28 Kromosom1 2 2
3 5 6 6 8 9  11 14 28 30 30
Kromosom2
2 2 3
5 6 6 8 9  11 14 28 30 30
Kromosom3
2 2 3
5 6 6 8
9  11 14 28 30 30
Kromosom4
2 2 3
5 6 6 8 9  11 14 28 30 30 Tabel 10. Kromosom hasil proses crossover Kromosom X1  X2  X3  X4  X5  X6  X7  X8  X9  X10  X26  X27  X28 Kromosom1 2 2
3 5 6 6 8 9  11 14 26 26 26
Kromosom2
2 2 3
5 6 6 8 9  11 14 28 30 30
Kromosom3
2 2 3
5 6 6 8 9  11 14 28 29 29 Kromosom4 2 2 3
5 6 6 8 9  11 14 28 29 29
Dari hasil crossover seperti pada Tabel 10, kromosom yang masih memiliki pelanggaran yaitu kromosom 1, 2, dan 4 akan menjalani proses selanjutnya yaitu  mutasi. Sedangkan kromosom yang tidak  memiliki  pelanggaran  yaitu  kromosom  3  akan  disimpan  sebagai  kromosom  yang  baik  yang nantinya akan digunakan untuk dibandingkan kromosom hasil mutasi.

## 5. Mutasi
Untuk mendapatkan posisi gen yang akan dimutasi maka perlu dihitung jumlah total gen dalam satu  populasi  yaitu  Total  gen  =  Jumlah  gen  dalam  satu  kromosom  x  Jumlah  kromosom  yang ada. Berdasarkan contoh yang ada maka total gen adalah = 28 x 3 = 84.  Probabilitas mutasi umumnya disetantara [0-1], misalnya 0,1 maka diharapkan mutasi yang terjadi adalah : 0,1 x 36 = 3,6 = 4 gen yang  akan  mengalami  mutasi.  Pemilihan  posisi  gen  yang  akan  dimutasi  dilakukan  secara  acak. Diasumsikan gen yang mendapatkan bilangan dibawah probabilitas mutasi adalah gen ke 5, 6, 17, dan 25. Nilai gen yang terkena proses mutasi nilainya akan diganti secara random. Setelah proses berhenti,  kromosom  hasil  mutasi  akan  dievaluasi.  Dapat  dilihat  pada  lampiran  6  olah  data  untuk proses mutase dan Tabel 11.
Tabel 11. Krompsom hasil proses mutasi Kromosom X1  X2  X3  X4  X5  X6  X7  X8  X9  X10  X26  X27  X28 Kromosom1 2 2 3 5 6 6 8 9  11 14 26 26 26 Kromosom2 2 2 3 5 6 6 8 9  11 14 28 30 30 Kromosom4 2 2 3 5 6 6 8 9  11 14 28 29 29 Tabel 12. Kromosom terbaik Kromosom1 2 2 3 5 6 6 8 9  11  14  26  26  26
Pada Tabel 12, kromosom 1 dapat dijelaskan bahwa gen X1 mempunyai nilai 1 menunjukkan bahwa kegiatan A dilaksanakan pada minggu ke 2, gen X2 mempunyai nilai A menunjukan bahwa kegiatan B  dilaksanakan pada minggu ke 3, dan seterusnya sampai dengan gen X28 yang mempunyai nilai 3 yang menunjukan bahwa kegiatan X28  dilaksanakan pada minggu ke 28. Atau Pada hari 178 hari-182 hari.
Hasil  akhir  dari  penelitian  ini  adalah  dihasilkannya  suatu  penjadwalan  proyek  yang  lebih optimal  dalam  penyeimbangan  biaya  per kegiatan  (Rp)  sebesar  Rp.388.000  dimana  gen-1  berisi  1 artinya bahwa Pekerjaan ke-1 dilaksanakan pada hari pertama atau hari ke-1, kemudian gen-2 bernilai 1  artinya  bahwa  Pekerjaan  ke-2  juga  di  laksanakan  pada  hari  pertama,sedangkan  gen-1  bernilai  2 artinya bahwa Pekerjaan ke-1 dilaksanakan pada hari ke-2, dan begitu seterusnya sampai pada hari ke-199  hari  kerja  sebesar  Rp.  294.796.000.  yang  diperoleh  dari  optimalisasi  penjadwalan  proyek menggunakan  Algoritma Genetika.

## 4. Kesimpulan
Berdasarkan hasil penelitian dapat disimpulkan bahwa durasi proyek yang optimal dan biaya yang  timbul  karena  adanya  optimalisasi  dari  aktivitas  ke  178  selama  210  hari  sebesar  Rp. 231.515.082.  Hasil  penjadwalan  dengan  menggunakan  CPM  dan  Algoritma  Genetika  merupakan salah satu alternatif bagi para  Kontraktor dalam melakukan penjadwalan proyek. Sedangkan Nilai optimasi  yang  didapatkan  dengan  meminimalkan  durasi  proyek menggunakan  CPM  (Critical  Path Method) adalah 199 hari dari total waktu proyek pembangunan puskesmas biau 210 hari kerja. dan biaya yang timbul karena adanya optimalisasi tersebut menggunakan Algoritma Genetika sebesar Rp. 231.515.082 dari biaya awal proyek sebesar Rp.382.784.000.

## Referensi
[1] K.  G.  S.  Juliawan,  I.  G.  M.  Darmawiguna,  and  M.  W.  A.  Kesiman,  “Simulasi  Metode Penugasan  dan  Transportasi  untuk  Pembelajaran  Riset  Operasional  Berbasis  Web,” J.  Nas. Pendidik. Tek. Inform. , vol. 4, no. 3, p. 96, Dec. 2015, doi: 10.23887/janapati.v4i3.9786.
[2] R.  Arifudin,  “Optimasi  Penjadwalan  Proyek  Dengan  Penyeimbangan  Biaya  Menggunakan Kombinasi Cpm Dan Algoritma Genetika,” J. Masy. Inform. , vol. 2, no. 4, pp. 1–14, 2012, doi: https://doi.org/10.14710/jmasif.2.4.2649.
[3] S. Perdana and A. Rahman, “Penerapan Manajemen Proyek Dengan Metode Cpm (Critical Path Method) Pada Proyek Pembangunan SPBE,” AMALIAH J. Pengabdi. Kpd. Masy. , vol. 3, no. 1, pp. 242–250, Feb. 2019, doi: 10.32696/ajpkm.v3i1.235.
[4] A. Nalhadi and N. Suntana, “Analisa Infrastruktur Desa Sukaci-Baros Dengan Metode Critical Path  Method  (CPM),” J.  Sist.  dan  Manaj.  Ind. ,  vol.  1,  no.  1,  p.  35,  Aug.  2017,  doi: 10.30656/jsmi.v1i1.167.
[5] A. Husen, Manajemen Proyek : Perencanaan, Penjadwalan, Dan Pengendalian Proyek , 2nd ed. Yogyakarta: Andi, 2011.
[6] N.  Rosanti,  E.  Setiawan,  and  A.  Ayuningtyas,  “Penggunaan  Metode  Jalur  Kritis  Pada Manajemen Proyek (Studi kasus: PT. Trend Communications International),” J. Teknol. , vol. 8, no. 1, p. 23, Jan. 2016, doi: 10.24853/jurtek.8.1.23-30.
[7] S. Ulfa and E. Suhendar, “Implementasi Metode Critical Path Method Pada Proyek Synthesis Residence  Kemang,” J.  Optimasi  Tek.  Ind. ,  vol.  3,  no.  1,  Mar.  2021,  doi: 10.30998/joti.v3i1.4167.
[8] V.  Y.  I.  Ilwaru,  D.  L.  Rahakbauw,  and  J.  Tetimelay,  “Penjadwalan  Waktu  Proyek Pembangunan Rumah Dengan Menggunakan CPM (Critical Path Method),” BAREKENG J. ILMU  Mat.  DAN  Terap. ,  vol.  12,  no.  2,  pp.  061–068,  Dec.  2018,  doi: 10.30598/vol12iss2pp061-068ar617.
[9] N. C. H. Wibowo, M. A. Ulinuha, K. Amalia, F. Y. Hassan, and H. Yahya, “Desain Kurikulum Mahasiswa Teknologi Informasi Uin Walisongo Menggunakan Critical Path Method (CPM),” Walisongo  J.  Inf.  Technol. ,  vol.  4,  no.  1,  pp.  53–62,  Aug.  2022,  doi: 10.21580/wjit.2022.4.1.12292.
[10]  E. Safitri, S. Basriati, and L. Hanum, “Optimasi Penjadwalan Proyek Menggunakan CPM Dan PDM  (Studi  Kasus:  Pembangunan  Gedung  Balai  Nilah  Dan  Manasik  Haji  Kua  Kecamatan Kateman Kabupaten Indragiri Hilir),” J. Sains Mat. Dan Stat. , vol. 5, no. 2, pp. 17–25, 2019, doi: http://dx.doi.org/10.24014/jsms.v5i2.7631.
[11]  L. Muzdalifah, E. Fitri Kurniawati, E. Deise Ulul, and K. Gular Pamitra, “Penjadwalan Proyek Perumahan Dengan Optimasi Waktu Dan Biaya Harian,” J. Ris. dan Apl. Mat. , vol. 3, no. 2, p. 78, Oct. 2019, doi: 10.26740/jram.v3n2.p78-87.
[12]  N.  Sa’adah,  E.  Iqrammah,  and  T.  Rijanto,  “Evaluasi  Proyek  Pembangunan  Gedung  Stroke Center  (Paviliun  Flamboyan)  Menggunakan  Metode  Critical  Path  Method  (CPM)  Dan Crashing,” Publ.  Ris.  Orientasi  Tek.  Sipil ,  vol.  3,  no.  2,  pp.  55–62,  Jan.  2022,  doi: 10.26740/proteksi.v3n2.p55-62.
[13]  Suyanto, Artificial  Intelligence :  Searching,  Reasoning,  Planning,  dan  Learning ,  3rd  ed. Bandung: Informatika, 2021.
[14]  I.  Robandi, Artificial  Intelligence:  Mengupas  Rekayasa  Kecerdasan  Tiruan .  Yogyakarta: ANDI, 2021.
[15]  R. L. Haupt and S. E. Haupt, Practical Genetic Algorithms . Wiley, 2003.