5

BAB II

LANDASAN TEORI

2.1 Pengertian Penjadwalan

Penjadwalan produksi merupakan kegiatan pengurutan pengerjaan di setiap

pemrosesan untuk mencapai optimalitas dengan merencanakan pengalokasian sumber

daya yang ada dalam melakukan beberapa pekerjaan pada waktu tertentu (Masudin,

Utama et al. 2014). Menurut Pinedo (2016), Penjadwalan adalah suatu proses

pengambilan keputusan dalam membuat dan menentukan jadwal. Berhubungan dengan

proses pengalokasian sumber daya untuk mengerjakan sekumpulan job dalam jangka

waktu tertentu.

Menurut Ginting (2009), penjadwalan ialah pengaturan waktu dalam kegiatan

operasi yang terdiri dari kegiatan mengalokasikan mesin, tenaga operator, urutan

proses, dan jenis produk. Dan menurut Eddy Herjanto (2010), tujuan dari penjadwalan

yaitu untuk meminimasi keterlambatan, waktu proses, waktu tunggu, konsumsi energi,

serta efisiensi penggunaan fasilitas, peralatan dan tenaga kerja.

2.2 Penjadwalan Flowshop

Penjadwalan flowshop ialah penjadwalan dengan urutan proses tiap job yang

sama dari mesin awal berurutan melewati proses operasi sampai mesin terkahir (Baker

and Trietsch 2013).

Mesin 1 Mesin 2 Mesin 3 Mesin n .

Input

Output

Gambar 2.1 Pola Aliran Flowshop

6

Berikut terdapat beberapa kondisi yang dimiliki penjadwalan flow shop :

Waktu pengerjaan setiap job pada tiap-tiap mesin selalu sama.

Semua mesin dalam kondisi baik (tidak ada terjadi mesin breakdown).

Tiap mesin hanya dapat memproses satu job dalam waktu yang sama.

Tidak terdapat 2 proses operasi yang dikerjakan secara bersamaan pada job

yang sama.

Tidak diperbolehkan menyela kegiatan operasi pada suatu mesin apabila

operasi belum selesai pada mesin tersebut (No Pre-emption).

No Cancellation, yaitu setiap job harus diproses hingga selesai.

Job deskripsi sudah diketahui sebelumnya.

2.3 Klasifikasi Kondisi Penjadwalan

Menurut Baker and Trietsch (2013) Berdasarkan kondisi yang terjadi dalam

proses produksi, penjadwalan produksi dapat diklasifikasikan menjadi dua yaitu

sebagai berikut :

1. Berdasarkan waktu proses.

a) Stokastik, waktu proses masih perlu diolah kembali dengan distribusi

probabilitas karena masih belum bisa dipastikan.

b) Deterministik, sudah dapat diketahui dengan pasti waktu prosesnya.

2. Berdasarkan pola kedatangan job.

a) Dinamik, selalu memperbarui urutan job apabila terdapat job baru yang masuk.

b) Statik, pengurutan job terbatas pada pemesanan yang masuk. Job yang baru

tidak mempengaruhi pengurutan job yang sudah dibuat.

2.4 Gantt Chart

Gantt Chart adalah diagram perencanaan yang digunakan dalam melakukan

penjadwalan sumber daya dan alokasi waktu (Render and Heizer 2005). Gantt chart

dibuat agar mudah dipahami, balok horizontal menunjukkan pengerjaan job sepanjang

7

garis waktu. Gantt chart dipergunakan untuk penjadwalan sederhana yang kegiatannya

tidak terlalu berkaitan. Berikut contoh pembuatan gantt chart dalam permutation

flowshop scheduling :

𝑝𝑡𝑗,𝑖 = [5 2 32 6 4

15 2 2] dengan urutan job = J1-J2-J3

Menentukan waktu penyelesaian (makespan) seluruh job pada mesin terakhir yaitu

dapat menggunakan rumus sebagai berikut:

𝑐𝑗,𝑖 = 𝑝𝑡𝑗,𝑖 , 𝑗 = 1 , 𝑖 = 1 (2.1)

𝑐1,𝑖 = 𝑐1,𝑖−1 + 𝑝𝑡1,𝑛 , 𝑖 = 2, … , 𝑚 (2.2)

𝑐𝑗,1 = 𝑐𝑗−1,1 + 𝑝𝑡𝑗,1 , 𝑗 = 2, … , 𝑛 (2.3)

𝑐𝑗,𝑖 = 𝑚𝑎𝑥(𝑐𝑗−1,𝑖 , 𝑐𝑗,𝑖−1) + 𝑝𝑡𝑗,𝑖 , 𝑗 = 2, … , 𝑛, 𝑖 = 2, … , 𝑚 (2.4)

Keterangan : 𝑛 = number of jobs

𝑚 = number of machines

𝑗 = job

𝑖 = machines

𝑝𝑡𝑗,𝑖 = waktu proses job ke-j di mesin ke-i

𝑐𝑗,𝑖 = waktu penyelesaian job ke-j di mesin ke-i

Gambar 2.2 Gantt Chart

Resource

M3

M2

M1

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 time

Job 1 Job 2 Job 3

Job 3

Job 3Job 1 Job 2

Job 1 Job 2

8

Keunggulan dari penggunaan gantt chart yaitu memudahkan pembaca dalam

menunjukkan waktu, kegiatan yang dilakukan dan urutan kegiatanya. Lebih disarankan

untuk jumlah kegiatan yang tidak terlalu banyak atau hanya sekedar jadwal induk,

karena mudah dipahami. Dan kekuranganya yaitu tidak memperlihatkan hubungan

antar kegiatan, kurang efisien karena tidak mudah dilakukan perbaikan. Dan tidak

mampu menyajikan jadwal sistematik untuk proyek yang berukuran besar serta

kompleks.

2.5 Konsumsi Energi

Menurut Mouzon, Yildrim dan Twomey (2007), Konsumsi energi dapat

dikurangi dengan mengendalikan keadaan operasional suatu mesin. Mesin yang

menganggur dibiarkan hidup dalam waktu lama akan meningkatkan konsumsi energi.

Tingginya konsumsi energi yang dikeluarkan dapat mempengaruhi produktifitas dari

sistem manufaktur. Penjadwalan produksi yang baik perlu mempertimbangkan jumlah

konsumsi energi yang dikeluarkan dalam proses produksi. Untuk menentukan total

konsumi energi yang dikeluarkan dapat dihitung menggunakan rumus sebagai berikut:

𝐵𝑖 = ∑ 𝑝𝑡𝑗,𝑖𝑛𝑗=1 , 𝑖 = 1 … 𝑚 (2.5)

𝑌𝑖 = 𝑐1,𝑖 − 𝑝𝑡1,𝑖 , 𝑖 = 1 … 𝑚 (2.6)

𝐶𝑇𝑖 = max(𝑐𝑗,𝑖) , 𝑗 = 1 … 𝑛, 𝑖 = 1 … 𝑚 (2.7)

𝑤𝑖𝑖 = 𝐶𝑇𝑖 − (𝐵𝑖 + 𝑌𝑖) , 𝑖 = 1 … 𝑚 (2.8)

𝑇𝐸𝐶 = ∑ (𝐵𝑖. 𝐸𝑝𝑖) +𝑚𝑖=1 (𝑤𝑖𝑙. 𝐸𝑖𝑖) (2.9)

Keterangan : 𝐵𝑖 = waktu sibuk pada mesin ke-i

𝑌𝑖 = waktu mulai di mesin ke-i

𝑝𝑡𝑗,𝑖 = waktu proses job ke-j di mesin ke-i

𝑐𝑗,𝑖 = waktu penyelesaian job ke-j di mesin ke-i

𝐶𝑇𝑖 = total waktu penyelesaian di mesin ke-i

9

𝑤𝑖𝑖 = waktu idle pada mesin ke-i

𝑇𝐸𝐶 = Total Konsumsi Energi

𝐸𝑝𝑖 = Besar energi yang dikeluarkan saat sibuk pada mesin ke-i

𝐸𝑖𝑖 = Besar energi yang dikeluarkan saat idle pada mesin ke-i

2.6 Genetic Algorithm

Metode Genetic Algorithm merupakan pemodelan berdasarkan pada mekanisme

genetika alam dan seleksi alam untuk mendapatkan ruang solusi optimal. Berikut

prosedur metode Genetic Algorithm (Tang and Liu 2002) pada gambar 2.3:

Inisisalisasi populasi (N) secara

random, menentukan parameter Pc dan

Pm

Mengevaluasi nilai fitness

tujuan

Seleksi

Crossover

Mutasi

Kriteria terpenuhi?

Mulai

Selesai

Yes

No

Gambar 2. 3 Prosedur Genetic Algorithm

10

1. Inisialisasi nilai parameter yang meliputi : jumlah populasi (N), parameter pindah

salah (𝑃𝑝𝑠) dan parameter mutasi (𝑃𝑚𝑡). Berikut penjelasan mengenai penentuan

parameter inisial :

a. Jumlah populasi (N) pada algoritma ini berupa urutan prioritas dari semua job

yang akan dijadwalkan. Semakin banyak jumlah job, maka semakin banyak

jumlah populasi awal yang harus dibangkitkan.

b. Nilai inisial untuk parameter pindah silang (𝑃𝑐).

c. Nilai inisial untuk parameter mutasi (𝑃𝑚).

2. Membangkitkan populasi awal secara acak sebanyak N kromosom. Dimana

kromosom merupakan urutan job sepanjang n.

3. Mengevaluasi semua kromosom dalam populasi dengan menghitung nilai fitness

sesuai fungsi tujuan (total konsumsi energi).

4. Penentuan sampel elit, dalam penentuan sampel elit pertama hasil konsumsi energi

dari seluruh sampel diurutkan dari yang terkecil hingga terbesar. Kemudian dipilih

satu sampel terbaik yang memiliki nilai konsumsi energi terkecil.

5. Setelah itu melakukan perhitungan nilai Linier Fitness Ranking (LFR). LFR

merupakan metode pembobotan yang digunakan untuk menentukan batasan-

batasan wilayah dari masing-masing fungsi fitness dari tiap kromosom (Aziz

2017).

𝐿𝐹𝑅(𝐼(𝑁 − 𝐼 + 1)) = 𝐹𝑚𝑎𝑥 − (𝐹𝑚𝑎𝑥 − 𝐹𝑚𝑖𝑛) ∗ ((𝑥 − 1)/(𝑁 − 1)) (2.10)

Dimana Fmax = 1/fungsi fitness (1), Fmin = 1/fungsi fitness (N), x adalah urutan

sampel, N adalah total sampel dan I menyatakan indeks pekerjaan dalam matriks

sampel.

6. Elitisme digunakan untuk menyimpan individu-individu terbaik dari sampel yang

memiliki nilai fungsi tujuan terbaik pada setiap iterasi. Hal tersebut dilakukan agar

sampel tetap muncul kembali pada iterasi selanjutnya (Nurkhalida and Santosa

2012).

11

7. Tahap selanjutnya yaitu menyeleksi kromosom-kromosom sebagai induk dengan

menggunakan mekanisme Roullette Wheel (𝑟𝑤). Induk 1 dipilih dari hasil sampel

elit dan induk 2 dipilih dari seluruh sampel berdasrkan nilai LFR (Santosa,

Budiman et al. 2011). Dengan membangkitkan bilangan acak sebanyak N dimana

𝑟𝑤 ∈ [0,1]. Untuk menentukkan kromosom yang terpilih menjadi induk pindah

silang yaitu menggunakan persamaan 2.11 dan 2.12.

𝑐1 > 𝑟𝑤𝑗 (2.11)

selanjutnya,

𝑐𝑗−1 < 𝑟𝑤𝑗 < 𝑐𝑗 (2.12)

8. Crossover (kawin silang), dilakukan dengan melibatkan persilangan sepasang

kromosom induk untuk membentuk kromosom baru/anak (offspring).

Kemungkinan suatu kromosom mengelami proses crossover berdasarkan dari

probabilitas crossover (𝑃𝑐). Dalam proses crossover dilakukan pertukaran

sebagian gen dari kedua kromosom induk. Dengan upaya dapat menghasilkan

kromosom anak dengan komposisi gen yang lebih baik. Metode yang digunakan

pada proses crossover yaitu 2-point order crossover. Untuk menentukan bilangan

acak yang nantinya akan dirubah kedalam bilangan bulat menggunakan rumus

sebagai berikut :

𝑟𝑖 = 𝑐𝑒𝑖𝑙(𝑟𝑎𝑛𝑑𝑜𝑚 ∗ 𝑛) (2.13)

9. Selanjutnya proses mutasi, yaitu proses untuk menghasilkan individu baru yang

berbeda. Mekanisme yang digunakan pada proses mutase yaitu recipal exchange

mutation. Tahapan dari metode tersebut yaitu dengan memilih dua posisi

(exchange point/XP) secara random. Kemudian menukar nilai pada posisi yang

terpilih. Untuk menentukan berapa banyak kromosom yang akan dimutasi, maka

perlu melakukan perhitungan dengan rumus :

𝑃𝑚 𝑥 𝑁 (2.14)

12

2.7 Whale Optimization Algorithm (WOA)

Algoritma WOA adalah metode metaheuristik yang meniru perilaku paus

(humpback whales) dalam menangkap mangsa. Strategi yang digunakan yaitu serangan

jaringan gelembung dan pencarian mangsa (Abdel-Basset, Manogaran et al. 2018).

Berikut adalah prosedur metode Whale Optimization Algorithm (WOA) pada gambar

2.4. :

Inisialisasi

- inisialisasi agen secara acak

Mengevaluasi seluruh agen dan

memilih satu yang terbaik

t < iterasi

Inisialisasi parameter algoritma a, A, L , C, b, P

P < 0,5

A >= L

Mencari agen secara acak

Update pencarian agen

Yes

No

Yes

No

Yes

t++

Mulai

Selesai

Gambar 2.4 Prosedur Whale Optimization Algorithm

13

1. Inisialisasi parameter WOA yang meliputi : jumlah populasi (N), parameter

𝑎, 𝑟, 𝐴, 𝐶, 𝑙 𝑑𝑎𝑛 𝑝. Berikut penjelasan lebih lanjut mengenai penentuan inisisalisasi

parameter :

a. Jumlah populasi (N) pada algoritma ini berupa urutan prioritas dari semua job

yang akan dijadwalkan. Semakin banyak jumlah job, maka semakin banyak

jumlah populasi awal yang harus dibangkitkan.

b. Parameter 𝑎, merupakan parameter yang digunakan untuk mencari nilai koefisien

vektor 𝐴. Dimana 𝑎 adalah penurunan secara linear dari 2 hingga 0 selama iterasi.

c. Parameter 𝑟, merupakan parameter yang digunakan untuk mencari nilai koefisien

vektor 𝐶. Dimana 𝑟 adalah vektor acak dari ∈ [0,1].

d. Parameter 𝐴, merupakan koefisien vektor untuk mencari vektor posisi. 𝐴 adalah

nilai random dengan rentang [−𝑎, 𝑎]. Atau dapat dicari dengan menggunakan

formula.

𝐴 = 2�⃗�. 𝑟 − �⃗� (2.15)

e. Parameter 𝐶, merupakan koefisien vektor untuk mencari vektor jarak.

𝐶 = 2. 𝑟 (2.16)

f. Parameter 𝐿, memiliki rentang nilai antara -1 hingga 1.

g. Parameter 𝑝, memiliki rentang nilai antara 0 hingga 1.

2. Melakukan pembangkitan populasi awal dengan mekanisme random sebanyak N.

Dimana populasi tersebut berupa urutan job sepanjang n.

3. Mengevaluasi semua populasi awal dengan menghitung fitness tiap populasi sesuai

fungsi tujuan. Kemudian mencari agen terbaik (𝑤∗) dari hasil fitness terkecil pada

iterasi = 0.

4. Apabila t < iterasi untuk mencari agen perlu melakukan update parameter WOA

(𝑎, 𝐴, 𝐿, 𝐶 𝑑𝑎𝑛 𝑝). Jika 𝑝 < 0,5 dan |𝐴| < 𝐿 melakukan update agen dengan

formula.

𝑥𝑡+1 = 𝑤∗ − 𝐴. 𝐷 (2.17)

dengan 𝐷 adalah

14

𝐷 = |𝐶. 𝑤∗ − 𝑥𝑡| (2.18)

Dimana 𝑥𝑡 = agen atau populasi ke-t, 𝑤∗ = agen terbaik pada iterasi ke-t. Apabila

|𝐴| ≥ 𝐿, melakukan update agen dengan formula.

𝑥𝑡+1 = 𝑥𝑟𝑎𝑛𝑑 − 𝐴. 𝐷 (2.19)

dengan 𝐷 adalah

𝐷 = |𝐶. 𝑥𝑟𝑎𝑛𝑑 − 𝑥𝑡| (2.20)

Dimana 𝑥𝑟𝑎𝑛𝑑 adalah melakukan seleksi agen secara random.

Dan jika 𝑝 ≥ 0,5 maka melakukan update agen dengan formula.

𝑥𝑡+1 = 𝐷′. 𝑒𝑏𝑙. cos(2𝜋𝑙) + 𝑤∗ (2.21)

dengan 𝐷′ adalah

𝐷′ = |𝑤∗ − 𝑥𝑡| (2.22)

Dimana 𝐷’ adalah nilai absolut dari jarak antara 𝑥𝑡 dan 𝑤∗. 𝑏 didefinisikan sebagai

bentuk dari spiral logaritmik. Dan 𝑙 adalah nilai random ∈ [−1,1].

5. Mengevaluasi hasil pencarian agen 𝑥𝑡+1, memperbarui agen terbaik (𝑤∗) jika 𝑥𝑡+1

lebih baik.

2.8 Literatur Review Penelitian Terdahulu

Adapun beberapa penelitian terdahulu mengenai penjadwalan menggunakan

genetic algorithm. Dalam penelitian Murata, Ishibuchi et al. (1996) menunjukkan

bahwa kinerja algoritma genetika sedikit lebih rendah sehingga perlu melakukan

hibridisasi dengan algoritma lain untuk meningkatkan kinerjanya. Murata, Ishibuchi et

al. (1996) dalam penelitiannya menunjukkan bahwa Multi-Objective Genetic

Algorithm dapat menemukan solusi yang lebih baik dari pada VEGA (Vector Evaluated

Genetic Algorithm) dan Single-Objective Genetic Algorithm. Min and Cheng (2006)

dalam penelitiannya menerangkan bahwa hasil perhitungan numerik dari algoritma

genetika efektif dan kuat, terutama pada kinerja Hybrid Genetic Algorithm With

Simulated Anneling. Nurjanah (2015) menunjukkan hasil perbandingan dari percobaan

menggunakan Genetic Algorithm (GA) dan Simulated Anneling (SA). Berdasarkan

15

nilai makespan yang diperoleh kedua metode mempunyai tingkat efektifitas yang sama.

Namun berdasarkan kestabilan tingkat konvergensinya GA lebih baik daripada SA.

Penelitian mengenai whale optimization algorithm (WOA) juga telah

digunakan oleh beberapa penelitian yaitu Mafarja and Mirjalili (2017) dalam

penelitiannya membandingkan hasil dari Whale Optimization with Simulated Anneling

(WOASA), Ant Lion Optimization (ALO), Particle Swarm Optimization (PSO) dan

Genetic Algorithm (GA). Menunjukkan bahwa hasil dari WOA with SA lebih optimal

daripada 3 algoritma pembanding. Jiang, Zhang et al. (2018) melakukan penelitian

menggunakan metode Whale Optimization Algorithm (WOA) untuk mengurangi

konsumsi energi pada lantai produksi job shop dan menghasilkan solusi optimal.

Abdel-Basset et al. (2018) dalam penelitiannya melakukan percobaan dengan metode

Hybrid Whale Algorithm (HWA) dan Nawaz Encore Ham (NEH). Hasil penelitiannya

menunjukkan bahwa HWA dengan local search meningkatkan kualitas solusinya.

Dan adapun beberapa penelitian yang membahas mengenai penjadwalan

dengan tujuan untuk meminimasi konsumsi energi. Dai, Tang et al. (2013) dalam

penelitian ini menunjukkan bahwa Genetic-Simulated Annealing Algorithm dapat

menghasilkan solusi optimal dalam meminimasi makespan dan efisiensi energi.

Shrouf, Ordieres-Meré et al. (2014) dalam penelitiannya menunjukkan bahwa hasil

perbandingan antara metode heuristik dengan solusi analitik dalam masalah yang besar.

Metode heuristik lebih baik digunakan karena hasil yang diperoleh lebih signifikan

dalam meminimasi konsumsi energi. Dalam penelitiannya Yao, Qian et al. (2018)

menunjukkan bahwa metode Hybrid Quantum-Inspired Evolution Algorithm (HQEA)

untuk masalah Blocking Flowshop Scheduling Problem (BFSP) menghasilkan solusi

yang efektif untuk mengurangi konsumsi karbon. Utama (2019) dalam penelitiannya

membandingkan algoritma Nawaz Encore Ham (NEH) dan Campbell Dudek Smith

(CDS) untuk meminimasi konsumsi energi. Hasil dari algoritma NEH lebih efektif

dibanding algoritma CDS. Piroozfard, Wong et al. (2018) dalam penelitiannya

16

menunjukkan bahwa algoritma genetika yang digunkan lebih unggul dari pada metode

lainnya. Dan memiliki dapak positif untuk konsumsi karbon yang dihasilkan.

Tabel 2. 1 Literatur Review Penelitian Terdahulu

Nama Penulis

Jenis

Lingkungan

Manufaktur

Metode Performansi

Sambodo and

Rosyidi (2007)

No-Wait Flow

shop Genetic Algorithm

Total

Flowtime

Pezzella,

Morganti et al.

(2008)

Flexible Job

shop Genetic Algorithm Makespan

Hamidinia,

Khakabimamagha

ni et al. (2012)

Hybrid Flow

shop Genetic Algorithm

Total

Tardiness

Mahmudy (2014) Flow shop Genetic Algorithm Makespan

Bashori, Pratikto

et al. (2015) Flow shop

Cross Entropy-Genetic

Algorithm (CEGA) Makespan

Bayani, Herlina et

al. (2017) Flow shop

CDS with Genetic

Algorithm Makespan