4

BAB II

LANDASAN TEORI

2.1 Penjadwalan

2.1.1 Definisi Penjadwalan

Pembeda antara perencanaan dengan penjadwalan ialah terdapat pada

kerangka waktu (period), dimana perencanaan dilakukan pada jangka waktu yang

relatif lebih panjang. Penjadwalan merupakan proses pengurutan dalam

pengerjaan suatu produk dari awal hingga akhir dan dikerjakan pada mesin dan

waktu yang telah ditentukan Baker and Trietsch (2013).

Sedangkan Pinedo (2012) mengatakan bahwa, perusahaan manufaktur dan

jasa memanfaatkan penjadwalan sebagai pengambil keputusannya dalam

pengalokasian sumber daya. Hal ini juga bertujuan mengoptimalkan hasil output

selama job tersebut dikerjakan. Rencana produksi digunakan sebagai pendukung

agar penjadwalan yang rinci dapat terlaksana. Informasi ini berupa kemampuan

dan kapasitas mesin, data operator pada setiap departemen, dan data pendukung

lainnya. Waktu merupakan informasi yang berperan penting dalam pembuatan

jadwal produksi. Tipe waktu yang dibutuhkan ialah waktu tersedia, waktu pada

saat dilakukannya setiap operasi, dan waktu pemeliharaan. Pengenalan terhadap

aspek pengerjaan yang ada di dalam pabrik juga dibutuhkan saat penjadwalan

produksi dibuat.

2.1.2 Penjadwalan Flowshop

Penjadwalan flowshop dapat diartikan sebagai pergerakan unit yang masing-

masing job nya melewati rangkaian stasiun kerja dan telah disusun berdasarkan

produknya. Produksi flowshop didesain dan diterapkan untuk produk yang

memiliki kapasitas produksi stabil dan banyak serta dapat dilakukan berulang kali.

Seluruh job diurutkan berdasarkan alur urutan proses produksi sebuah produk,

sesuai mesin dan waktu prosesnya disebut juga sebagai sistem penjadwalan

flowshop. Kriteria pengukuran dalam penjadwalan harus berjalan tanpa adanya

5

waktu menganggur. Peningkatan jumlah job atau mesin akandiutamakan untuk

dipertimbangkan ketika sudah mencapai solusi yang optimal. Berikut adalah tipe

aliran Flowshop menurut Morton and Pentico (1993):

1. Pure Flowshop

Aliran ini memerlukan pengerjaan job yang dioperasikan dengan jalur

yang sama. Dengan demikian setiap pekerjaan membutuhkan urutan operasi

tertentu yang harus dilakukan agar pekerjaan selesai.

Gambar 2.1 Pola Aliran Pure Flowshop

2. Skip Flowshop

Proses aliran urutan job yang dapat dilewati atau berpola melompat

(skip) untuk menyelesaikan suatu job tertentu. Dengan begitu akan

menghindari atau melewati salah satu mesin karena tidak terjadi proses

produksi pada mesin tersebut alias akan di ‘skip’.

Gambar 2.2. Pola Aliran Proses Skip Flowshop

3. Re-entrant Flowshop

Pada aliran ini mesin dapat digunakan lebih dari sekali (berulang-ulang)

dalam membuat produk.

Gambar 2.3. Pola Aliran Proses Reentrant Flowshop

6

4. Compound Flowshop

Sesuai dengan artinya compound, aliran ini terdiri dari sekelompok

mesin yang memuat jalur parallel atau batch di setiap tahapan proses

produksinya.

Gambar 2.3. Pola Aliran Proses Compound Flowshop

2.1.3 Klasifikasi Kondisi Penjadwalan

Menurut penelitian Prasetya (2017), dalam Baker and Trietsch (2013),

mengatakan bahwa kondisi penjadwalan dapat diklasifikasikan berdasarkan

perbedaan yang terjadi dalam proses produksi, diantaranya ialah:

1. Menurut kedatangan job.

a) Statik, job diurutkan sesuai pemesanan yang masuk dengan suatu batasan.

Job yang baru masuk tidak dapat mempengaruhi pengurutan job yang ada.

b) Dinamik, job diurutkan sesuai dengan job yang terbaru (ter-update).

2. Menurut waktu proses

a) Deterministik, waktu proses sudah dipastikan.

b) Stokastik, harus memperkirakan probabilitas karena waktu proses yang

diterima belum pasti.

7

2.1.4 Kendala Penjadwalan Pada Pengurutan Job

Pada umumnya, masalah dan hambatan dapat ditemukan pada setiap proses

produksi yang akan dilewati, dan hal ini akan mempengaruhi penjadwalan

produksinya. Menurut Pinedo (2012) masalah dan hambatan ialah:

1. Mesin Rusak

Ketika mesin rusak (breakdown), akan mengakibatkan operasi terhambat

dan mengalami proses menunggu sampai mesin dapat digunakan kembali

secara normal. Dengan demikian proses produksi akan berhenti dan

penjadwalan urutan job awal mengalami gangguan. Penyesuaian jadwal awal

dibutuhkan sampai didapatkannya penjadwalan yang feasible. Kemudian

langkah selanjutnya perlu dilakukan penjadwalan ulang (rescheduling).

Waktu perbaikan dan penyelesaiannya dibutukan sebagai informasi

perbaikan kerusakan mesin yang akan datang. Berikut prinsip perbaikan

mesin untuk mengembangkan algoritma penjadwalan:

a. Rescheduling dilakukan dari titik waktu terjadinya gangguan mesin dan

setiap operasi yang belum dikerjakan

b. Apabila operasi sudah selesai sebelum terjadinya gangguan maka tidak

dihiraukan.

c. Gangguan terjadi ketika sedang beroperasi maka tidak akan terjadi

perubahan pada proses produksinya.

d. Jika sudah teridentifikasi maka dilakukan rescheduling dengan

memundurkan waktu operasi terhadap waktu perbaikan mesin.

2. Adanya penambahan pesanan

Penambahan pesanan baru dapat terjadi sewaktu-waktu. Dengan adanya

hal tersebut pelaksanaan penjadwalan akan mengalami gangguan. Maka,

penjadwalan ulang dibutuhkan dengan mempertimbangkan pesanan baru.

Hasil yang diharapkan ialah hasil optimal pada setiap produksi. Informasi

perbaikan membutuhkan data berupa jenis produk yang dipesan, routing job

(rute proses produksi), jumlah pesanan dan due date yang diminta custome.

Berikut prinsip yang ada ketika ada pesanan tambahan:

8

a. Rescheduling dilakukan dari titik waktu terjadinya gangguan dan pada

operasi yang belum dikerjakan.

b. Gangguan terjadi ketika sedang beroperasi maka tidak akan terjadi

perubahan pada proses produksinya.

c. Apabila operasi sudah selesai sebelum terjadinya gangguan maka tidak

dihiraukan.

3. Berubahnya prioritas produksi

Penjadwalan akan dipengaruhi oleh perubahan prioritas pembuatan

produk. Pada algoritma penjadwalan gangguan perubahan prioritas

mempunyai prinsip yang sama dengan kasus adanya penambahan pesanan.

4. Operasi produk tertentu mengalami pengulangan

Kecacatan pada produk akan mengharuskan terjadinya pengulangan

operasi, hal ini menjadikan proses produk lainnya mengalami adanya delay

dan menunggu sampai produk yang mengalami pengulangan selesai.

5. Perubahan due date

Due date dimajukan atau dimundurkan akan mempengaruhi adanya

gangguan proses produksi. Jika duedate mengalami kemunduran perusahaan

tidak akan mengalami perubahan urutan proses produksi awal. Akan tetapi,

sebaliknya jika dimajukan penjadwalan urutan job semula otomatis akan

mengalami perubahan.

9

2.1.5 Terminologi pada penjadwalan

Istilah umum pada penjadwalan ialah sebagai berikut:

a. Processing Time / waktu proses (Pi), merupakan waktu proses (Processing

Time) operasi atau proses dari job ke- i yang terdiri dari cakupan waktu

persiapan dan pengaturan proses.

b. Due Date (di), batas akhir waktu job ke-i. Apabila batas melewati duedate

maka dinyatakan sebagai tardy (terlambat).

c. Completion Time / waktu penyelesaian (Ci), selisih waktu saat job (t= 0)

dimulai hingga job ke-i selesai.

d. Lateness (Li), Waktu keterlambatan yang terjadi melebihi batas waktu

penyelesaiaan job (duedate).

Li = Ci – di……..…………………………………………………………..(1)

e. Tardiness (Ti), Waktu keterlambatan penyelesaian job terhadap duedate yang

ditentukan.

T𝑖=Max{0,Li}……..…………………………………………………….....(2)

f. Earliness atau Lateness negative merupakan waktu penyelesaian yang terjadi

sebelum dudate.

0,ii LMinE ……..……………………………………………………..(3)

g. Slack (Si), ialah selisih antara waktu yang tersedia pada setiap job.

Si = di-ti……………………………………………………………………(4)

h. Makespan (M), waktu total penyelesaian job yang berasal dari keseluruhan

waktu proses

i. Flow Time (Fi), Routing waktu mulai dari job ke-i dinyatakan ready sampai

selesai dikerjakan.

j. Ready Time (Ri), Waktu pada saat job siap atau dapat dikerjakan pada waktu

itu juga.

10

2.1.6 Ukuran Peformansi Penjadwalan

Berdasarkan penelitian Prasetya (2017), dalam Baker and Trietsch (2013),

ukuran performansi mempunyai tujuan bagi penjadwalan untuk menghasilkan

sesuai yang diinginkan. Berdasarkan urutan job yang ada penjadwalan mempunyai

kriteria diantaranya:

1. Atribut job

a) Flow time (Fi), merupakan waktu saat dimulainya suatu job dari saat masuk

proses sampai job selesai, berikut persamaan rumusnya:

𝐹𝑖 = 𝐶𝑖 − 𝑟𝑖………………………………………………………………... (5)

b) Completion Time (Ci), merupakan rentang waktu job saat pertama mulai (t =

0) dikerjakan sampai selesai, berikut persamaan rumusnya:

𝐶𝑖 = 𝐹𝑖 + 𝑟𝑖………………………………………………………………...(6)

c) Mean flow time, merupakan average dari keseluruhan waktu job yang

melewati semua aliran, berikut persamaan rumusnya:

Fj = 1

𝑛 ∑ 𝐹𝑖𝑛

𝑗=1 …………………………..……………………………… (7)

d) Mean weight flow time, ialah average seluruh job, namun job yang dapat

diprioritaskan akan dikerjakan terlebih dahulu, berikut persamaan rumusnya:

Fw =1

𝑛 ∑ 𝐹𝑗𝑛

𝑗=1 ……..…………………………………………………….(8)

e) Maximum Lateness, merupakan selisih total waktu terhadap batas waktu (due

date), dimana Lmax = max.

f) Lateness, merupakan keterlambatan yang bernilai positif jika job dapat

diselesaikan lebih cepat dari dari due date-nya, berikut persamaan rumusnya:

Ti = 𝑚𝑎𝑥 (0, 𝐿𝑖)……..……………………………………………………(9)

g) Total waktu keterlambatan (tardiness), yaitu total keterlambatan setiap job,

berikut persamaan rumusnya:

T = ∑ 𝑇𝑖𝑛𝑖=1 ……..…………………………………………………….. (10)

h) Mean tardiness, merupakan average dari waktu keterlambatan total, berikut

persamaan rumusnya:

𝑇 = 1

𝑛 ∑ 𝑇𝑖𝑛

𝑖=1 ……..…………………………………………………..(11)

11

2.2 Gantt Chart

Gantt chart berfungsi sebagai alat merencanakan dan mengelola produksi

batch. Dalam istilah modern, Gantt menggunakan pendekatan permintaan yang

tergantung waktu untuk perencanaan produksi. Perencanaan produksi Gantt bekerja

dengan cara 'top-down' dengan menghubungkan persyaratan item akhir dengan

komponen penyusunnya dengan produksi bertahap untuk memungkinkan semua

komponen tersedia ketika diperlukan untuk kegiatan produksi selanjutnya. Tanggal

jatuh tempo ini selanjutnya digunakan untuk merencanakan produksi harian dengan

menentukan jumlah yang akan dibuat dan kemudian melacak produksi terhadap

tujuan harian (Wilson, 2003). Gantt chart dapat membantu penggunanya untuk

memastikan bahwa; urutan kinerja sesuai yang telah diperhitungkan, catatan

perkiraan waktu dari kegiatan yang dilakukan, perencanaan dari semua kegiatan,

waktu proyek yang dibuat secara keseluruhan.

Mesin

1 Job1.1 Job2.1

2 Job1.2 Job2.2

1 2 3 4 5 6 7 8 9 10 Waktu

12

2.3 Cross Entropy Genetic Algorithm

Menurut Widodo (2017) metode CEGA merupakan penggabungan dari

metode Cross Entropy (CE) dan Genetic Algorithm (GA). Prosedur dari metode

Cross Entropy Genetic Algorithm dapat digambarkan sebagai berikut:

MULAI

Pendefisian Input dan

Ouput

Penentuan Nilai

Parameter Inisial

Pembangkitan Sampel

Awal

Perhitungan Fungsi

Tujuan (minimasi

tardiness)

Pemilihan Sampel Elite

Pembaharuan Parameter

crossover dan parameter

mutasi

Apakah Sudah

Memenuhi Syarat

Pemberitahuan?

Pembobotan Sampel Elite

Penghitungan Nilai

Linear Fitness Rangking

Penentuan Kromosom

Induk

Crossover

Mutation

Optimal Solution

SELESAI

Tidak

Ya

Gambar 2.4 Flowchart CEGA Algorithm

1. Nilai parameter initial yang harus ditentukan ialah

a. (N) jumlah sampel, berupa urutan prioritas dari seluruh job yang akan

dijadwalkan. Jika job banyak maka sampel yang dibangkitkan juga

harus sebanding.

b. (ρ) parameter kejarangan, berfungsi sebagai penentu sampel elit yang

akan diambil pada suatu populasi solusi (N). Menurut Kothari and

Kroese (2009) dalam penelitian Widodo (2017) kisaran rho ialah

sebesar 1% - 10%,

c. (α) koefisien kehalusan, berada pada nilai angka 0<α<1, namun nilai

optimal berada pada nilai 0,4<α<0,9 (De Boer et al., 2005).

13

d. (Pps) parameter pindah silang, mempunyai nilai inisial sebesar 1

(Santosa et al., 2011).

e. (β) kriteria pemberhentian pada iterasi. Berfungsi sebagai

pemberhentian iterasi ketika sudah mencapai optimal. Menurut

(Santosa et al., 2011) selisih parameter pindah silang pada iterasi

sekarang dengan sebelumnya.

2. Membangkitan secara random atau acak sebanyak nilai N, dan urutan

nantinya akan sepanjang nilai n.

3. Menghitng fungsi tujuan T (total waktu keterlambatan (tardiness)), berikut

notasi fungsi tujuannya:

𝑇 = ∑ 𝑇𝑖, 𝑇𝑖𝑛𝑖=1 = 𝑀𝑎𝑥 [0, Ci – di], 𝑖= 1, 2, …, n……..………………(12)

Keterangan:

Ti = Tardiness ke-i

4. Mengoreksi pemberhentian iterasi (β). Jika Iterasi berhenti maka selisih

antara parameter iterasi sekarang dibanding sebelumnya lebih kecil dari

batasnya.

5. Urutan job optimal merupakan hasil akhir, total waktu keterlambatan

(tardiness) T, jumlah iterasi, dan waktu komputasi.

6. Sampel elit dipilih jika β > batas yang ditetapkan, selanjutnya menyeleksi

sejumlah rho (ρ)*N dari total sampel (N) dari semua sampel yang telah

diurutkan mulai dari minimum ke maximum.

7. Sampel elit kemudian dilakukan pembobotan melalui Rangking Selection

yang berfungsi menentukan sampel induk Crossover.

Ranking (I (N-i+1)) = Fmax - (Fmax - Fmin)*((i-1) / (N-1)) ……..…….(13)

8. Memperbarui parameter pindah silang (Pps) dan mutasi (Pm) berfungsi untuk

mendapatkan baru yang lebih baik. Dengan rumus fungsi:

Pps(i)=(1-α)*u+(Pps(i+1)*α)……..…………..…………………………….(14)

best

e

Z

Zu

*2

……..…………………………………………………….. (15)

14

Dimana, eZ = objektif pada sampel elite, bestZ = objektif terbaik pada tiap

iterasi.

9. Elitisme dengan roulettee wheel berfungsi untuk mepertahankan sampel

yang terbaik.

ri < ci……..…………………………………………………………….. (16)

ci-1 < ri < ci……..………………………………………………………. (17)

10. Kromosom induk ditentukan saat induk pertama berasal dari elitism tadi dan

diberi pembobotan. Kemudian memilih induk kedua dari populasi dan

diberi bobot dengan cara Ranking Selection.

11. Persilangan dilakukan dengan Partially-Mapped Crossover Operator

(PMX2). Crossover in berfungsi untuk mencari kombinasi teroptimal dr

populasi. Rumus nilai random atau acak dari penelitian Ardiansyah (2018):

r1= ceil (random*n) ……..…………………………………………….(18)

12. Mutasi (swap mutation (menukar), flip mutation (membalik), dan slide

mutation (menggeser)) rumus fungsinya sebagai berikut;

2

_ psPPm ……..………………………………...……………………(19)

I, J = ceil (n*rij) ……..………………...………..………………….........(20)

k = ceil (rand K*3) ……..…………………………………….………...(21)

2.4 Literature Review

Beberapa penelitian terdahulu mengenai penjadwalan flowshop dengan

menggunakan pengembangan Genetic Algorithm diperlukan guna menunjang

penelitian. Penelitian pertama kali dilakukan oleh Li et al. (1998) dimana masalah

penjadwalan dapat diselesaikan dengan Genetic Algorithm dan telah menunjukkan

hasil simulasi dan perbandingan yang paling efektif dan efisien. Sama halnya

dengan penelitian sebelumnya solusi optimal dengan kualitas tinggi dan waktu yang

cepat telah ditemukan oleh Onwubolu and Mutingi (1999) akan tetapi bedanya

berada pada sekala produksinya yaitu dilakukan pada sekala produksi menengah

dan besar. Min and Cheng (2006) merujuk jika Genetic Algorithm efektifnya kuat,

dan khususnya pada simulasi Annealing. Untuk pertama kalinya Budiman (2010)

15

menggabungkan Cross Entropy-Genetic Algorithm (CEGA) kemudian

dibandingkan dengan Genetic Algorithm-Simulated Annealing (GASA) dimana

ditemukan jika CEGA lebih baik daripada GASA karena makespan yang paling

kecil.

Pada tahun berikutnya Santosa et al. (2011) menemukan hasil lebih baik

disbanding CEGA Genetic Algorithm-Simulated Annealing (GASA)-Hybrid Tabu

Search. Penelitian Puspitasari and Santosa (2011) menyimpulkan bahwa metode

CEGA performasinya lebih baik dibanding Cross Entropy (CE). Nurkhalida and

Santosa (2012) menyimpulkan bahwa CEGA solusinya lebh kompetitif

dibandingkan algoritma Simulated Annealing (SA). Penelitian selanjutnya

dilakukan oleh Hanka and Santosa (2013), menyatakan jika CEGA lebh optimal

dibandingkan Cross Entropy murni, dan Simulated Annealing.

Pada tahun berikutnya Bashori (2015) menggunakan CEGA untuk

memperkecil makespan pada flowshop scheduling, kemudian disempurnakan

kembali (Bashori et al., 2015) dan mendapatkan makespan jauh lebih kecil apabila

dibandingkan dengan metode perusahaan. Algoritma CEGA dan Differential

Evolution (DE) dibandingkan oleh Witjaksana (2016) menghasilkan bahwa CEGA

lebih baik daripada DE. Penelitian Widodo (2017) memperluas pencarian solusi

dengan menggunakan algoritma CEGA. Di tahun terakhir, Ardiansyah (2018)

membuktikan bahwa Algoritma CEGA dengan total waktu keterlambatan

(tardiness) yang lebih kecil dibandingkan metode perusahaan.