5

BAB II

LANDASAN TEORI

2.1 Pengertian Penjadwalan

Penjadwalan adalah aktivitas perencanaan untuk menentukan kapan dan

dimana setiap operasi sebagai bagian dari pekerjaan secara keseluruhan harus

dilakukan pada sumber daya yang terbatas, serta pengalokasian sumber daya pada

suatu waktu tertentu dengan memperhatikan kapasitas sumber daya yang ada.

Penjadwalan dapat diartikan sebagai pengalokasian sejumlah sumber daya

(resource) untuk melakukan sejumlah tugas atau operasi dalam jangka waktu

tertentu dan merupakan proses pengambilan keputusan yang peranannya sangat

penting dalam industri manufaktur dan jasa yaitu mengalokasikan sumber-sumber

daya yang ada agar tujuan dan sasaran perusahaan lebih optimal (Baker & Trietsch,

2009).

Menurut Pinedo (2012), penjadwalan dapat didefinisikan sebagai proses

pengalokasian sumber daya untuk mengerjakan sekumpulan tugas dalam jangka

waktu tertentu dengan 2 arti penting sebagai berikut.

a. Penjadwalan merupakan suatu fungsi pengambilan keputusan untuk membuat

atau menentukan jadwal.

b. Penjadwalan merupakan suatu teori yang berisi sekumpulan prinsip dasar,

model, teknik, dan kesimpulan logis dalam proses pengambilan keputusan yang

memberikan pengertian dalam fungsi penjadwalan.

Penjadwalan dibutuhkan untuk mengurangi alokasi tenaga operator, mesin

dan peralatan produksi, dan dari aspek lainnya untuk lebih efisien. Hal ini sangat

penting dalam pengambilan keputusan dalam proses kelangsungan produksi.

2.2 Persoalan Penjadwalan

Persoalan penjadwalan adalah persoalan pengalokasian pekerjaan ke mesin,

pada kondisi mesin mempunyai kapasitas dan jumlah terbatas. Secara umum

masalah penjadwalan dapat dijelaskan sebagai n job (J1, J2,…,Jn) yang harus

diproses di m mesin (M1, M2,…,Mn). Waktu yang diperlukan untuk memproses

6

pekerjaan J1 pada mesin M adalah P setiap job harus diproses tanpa dihentikan

selama waktu proses p mesin hanya dapat menangani satu job pada saat yang sama,

dan secara terus menerus tersedia sejak waktu nol (time zero).

Pemecahan permasalahan yang diinginkan adalah mendapatkan jadwal

yang optimal, yaitu menyelesaikan semua pekerjaan dengan mendapatkan jadwal

yang optimal yaitu menyelesaikan semua pekerjaan dengan adanya keterbatasan

kapasitas dan ketersediaan mesin dengan memenuhi fungsi tujuannya. Secara

umum persoalan penjadwalan dapat dinyatakan sebagai berikut (Richard W et al.

1976) :

a) Misalkan adalah resiko yang ditanggung karena mengerjakan tugas A lebih

dahulu dari pada tugas B.

b) Misalkan adalah resiko yang ditanggung karena mengerjakan tugas B lebih

dahulu dari pada tugas A. β

c) Jika lebih besar dari pada , maka tugas B dikerjakan lebih awal , kemudian

diikuti oleh tugas A. Pemilihan dan ini dapat dikaitkan dengan pemilihan

kriteria optimalitas yang ditetapkan oleh pengambilan keputusan.

2.3 Tujuan Penjadwalan

Tujuan penjadwalan adalah untuk mengurangi waktu keterlambatan dari

batas waktu yang ditentukan agar dapat memenuhi batas waktu yang telah disetujui

dengan konsumen, penjadwalan juga dapat meningkatkan produktifitas mesin dan

mengurangi waktu menganggur. Produktifitas mesin menigkat maka waktu

menganggur berkurang, secara tidak langsung perusahaan dapat mengurangi biaya

produksi. Semakin baik suatu penjadwalan semakin menguntungkan juga bagi

perusahaan dan bisa menjadi acuan untuk meningkatkan keuntungan dan strategi

bagi perusahaan dalam pemuasan pelanggan.

Beberapa tujuan yang ingin dicapai dengan dilaksanakannya penjadwalan

adalah sebagai berikut (Baker & Trietsch, 2009).

7

1. Meningkatkan produktifitas mesin, yaitu dengan mengurangi waktu mesin

menganggur.

2. Mengurangi persediaan barang setengah jadi dengan mengurangi jumlah rata-

rata pekerjaan yang menunggu antrian suatu mesin karena mesin tersebut sibuk.

3. Menggurangi keterlambatan karena telah melampaui batas waktu dengan cara,

a. Mengurangi maksimum keterlambatan,

b. Mengurangi jumlah pekerjaan yang terlambat.

4. Meminimasi ongkos produksi.

5. Pemenuhan batas waktu yang telah ditetapkan (due date), karena dalam

kenyataan apabila terjadi keterlambatan pemenuhan due date dapat dikenakan

suatu denda (penalty).

Teknik penjadwalan yang tepat bergantung pada pada volume pesanan, ciri

operasi, keseluruhan kompleksitas pekerjaan, serta perhatian pada tujuan dari

penjadwalan itu sendiri.

2.4 Klasifikasi Penjadwalan

Klasifikasi penjadwalan produksi menurut Ginting (2009), pada prinsipnya

ada dua macam, yaitu:

a. Penjadwalan maju (forward schedulling)

Operasi penjadwalan dimulai dari tanggal penerimaan order secara maju. Dan

kemungkinan terjadi persediaan bahan baku sampai pada giliran diproses.

Keuntungan dari metode ini penjadwalan dapat disusun secara SPT (Short

processing time) sehingga didapatkan suatu penjadwalan dengan flowtime yang

minimum.

b. Penjadwalan mundur (backward schedulling)

Suatu teknik penjadwalan dimulai dari waktu penyelesaian operasi terakhir.

Keuntungan dari metode ini adalah mengurangi barang setengah jadi (work in

process)

Klasifikasi penjadwalan menurut Pinedo (2012), terbagi menjadi:

a. Penjadwalan mesin tunggal (single machine)

8

b. Penjadwalan Paralel

Penjadwalan paralel dibagi menjadi:

1. Penjadwalan N job pada mesin paralel identik (identical machines parallel)

prinsip dalam penjadwalan paralel identik adalah pengalokasian beban ke

mesin yang lebih dahulu idle/kosong.

2. Penjadwalan N job pada mesin paralel non identik, dimana setiap mesin

mempunyai fungsi yang sama namun waktu proses berbeda. Flow time tidak

bisa dievaluasi langsung dari waktu proses. Tidak selalu alternatif waktu

terpendek dari setiap job akan menjadi keputusan alokasi pada mesin.

3. Penjadwalan N job pada mesin paralel unrelated perluasan dari paralel non

identik. Terdapat m mesin paralel, dimana mesin i untuk memproses job j

maka kecepatan mesin adalah vij.

4. Penjadwalan Flow Shop dan Flexible Flow shop, terdapat m mesin serial

dimana masing-masing job harus diproses di setiap mesin. Semua job harus

mengikuti rute yang sama. Setelah proses selesai di satu mesin maka akan

dilanjutkan proses pada mesin selanjutnya.

5. Penjadwalan Job Shop dan Flexible Job Shop terdapat m mesin dimana setiap

job memiliki rute produksi yang harus diikuti. Job dapat diproses lebih dari

satu kali pada mesin yang sama. Kondisi ini yang sering disebut dengan

recirculation. Flexible job shop adalah perluasan dari job shop dan mesin

paralel. Pada kasus ini terdapat m mesin seri dengan c stasiun kerja dengan

sejumlah mesin identik untuk setiap stasiun kerja.

6. Penjadwalan Open Shop Penjadwalan ini diterapkan untuk kasus m mesin

dimana setiap job harus diproses lagi untuk setiap mesin. Akan tetapi waktu

proses dapat bernilai nol. Tidak ada batasan urutan produksi untuk setiap job,

setiap job memiliki urutan proses yang berbeda pula.

2.5 Jenis-jenis Aliran Produksi

Jenis-jenis aliran produksi merupakan suatu skema dimana proses

berjalannya aliran dapat di klasifikasikan menjadi berberapa tipe. Adapun jenis-

9

jenis aliran proses menurut Baker & Trietsch (2009), yang secara umum dimiliki

banyak perusahaan yaitu:

a. Aliran proses flow shop, yaitu lantai produksi yang memroses produknya dengan

urutan proses yang sama terhadap semua komponen produk yang bersangkutan

dari mulai bahan awal sampai produk selesai. Jadi setiap pekerjaan yang telah

diproses pada suatu mesin dan kemudian sedang diproses pada mesin yang lain

tidak dapat diproses kembali pada mesin yang telah dilalui sebelumnya. Adapun

beberapa variasi aliran proses flow shop diantaranya:

1. Simple Flow Shop

Semua jenis pekerjaan melalui urutan proses yang sama.

2. Skip Flow Shop

Aliran pekerjaan pada jenis aliran proses ini cenderung melalui urutan proses

yang sama, tetapi ada beberapa pekerjaan yang tidak diproses pada mesin-

mesin tertentu.

3. Reentrant flow shop

Yakni aliran proses dimana terdapat penggunaan satu atau beberapa mesin

lebih dari sekali dalam membuat produk dimaksud.

4. Compound Flow Shop

Yakni aliran proses yang memuat kelompok jenis mesin pada setiap tahap

prosesnya. Kelompok mesin biasanya berupa mesin mesin paralel.

5. Aliran proses Job Shop

Merupakan proses transformasi dimana produk dibuat atas dasar pesanan

dalam jumlah tertentu. Setiap order dapat mempunyai urutan dari jumlah lot

atau batch atau mesin yang berbeda. Dalam lantai produksi stasiun kerja dan

departemen dikelompokkan berdasarkan fungsinya. Kerena setiap order

dapat mempunyai urutan dari jumlah lot atau batch atau mesin yang berbeda,

maka memungkinkan setiap stasiun kerja memproses beberapa item yang

berbeda. Artinya bahwa pekerjaan diperbolehkan untuk diproses lebih dari

satu kali pada mesin yang sama. Jika setiap mesin hanya dilalui satu kali,

10

disebut aliran proses job shop murni dan sebaliknya disebut aliran proses job

shop umum.

2.6 Klasifikasi Kondisi Penjadwalan

Penjadwalan produksi dapat diklasifikasikan dari perbedaan kondisi yang

mendasarinya, klasifikasi penjadwalan yang sering terjadi dalam proses produksi

adalah sebagai berikut:

1. Berdasarkan Product Positioning.

a) Make to order

Jumlah dan jenis produk yang dibuat berdasarkan pemintaan dari konsumen,

biasanya salah satu tujuan kebijakan ini adalah mengurangi biaya simpan.

b) Make to stock

Jumlah dan jenis produk terus menerus dibuat untuk disimpan dalam

inventory

2. Berdasarkan pola kedatangan job.

a) Statik, pengurutan job terbatas pada pesan yang ada. Job yang baru tidak

mempengaruhi pengurutan job yang sudah dibuat.

b) Dinamik, pengurutan job selalu diperbaharui jika ada job baru yang datang.

3. Berdasarkan waktu proses

a) Deterministik, waktu proses yang diterima sudah diketahui dengan pasti.

b) Stokastik, waktu proses yang diterima belum pasti, oleh karena itu pelu

diperkirakan dengan menggunakan distribusi probabilitas.

2.7 Ukuran Performansi Penjadwalan

Pengambilan keputusan penjadwalan produksi terdapat beberapa-beberapa

kriteria. Kriteria dalam pengambilan keputusan tentang penjadwalan yang

ditampilkan sebagai evaluasi dari penjadwalan sejumlah job yang diproses di dalam

sejumlah mesin yang merupakan fungsi dari sekumpulan waktu penyelesaian

(Ginting, 2009). Ukuran performansi merupkan tujuan dari penjadwalan akan hasil

yang diinginkan (Baker & Trietsch, 2009). Adapun kriteria penjadwalan produksi

adalah sebagai berikut:

11

1. Kriteria performansi penjadwalan berdasarkan atribut tugas.

a) Completion time, waktu yang dibutuhkan untuk menyelesaikan pekerjaan

mulai dari saat tersedianya pekerjaan (t = 0) sampai pada pekerjaan tersebut

selesai dikerjakan. Atau menunjukkan rentang waktu sejak pekerjaan pertama

mulai dikerjakan sampai proses tersebut selesai dimana:

Cj = Fj - rj

b) Mean flow time merupakan waktu rata-rata waktu pekerjaan j yang

dihabiskan dimana:

F=1

𝑛 ∑ 𝐹𝑖𝑛

𝑗=1

c) Flow time (Fi), Adalah waktu yang dibutuhkan oleh suatu pekerjaan dari saat

pekerjaan tersebut masuk ke dalam suatu tahap proses sampai pekerjaan

yangbersangkutan selesai dikerjakan.

Fi = Ci - ri

d) Mean weight flow time, memiliki arti yang hamper sama dengan mean flow

time, hanya saja mempertimbangkan prioritas pengerjaan setiap job, dimana

dalam perhitungan sebagai berikut:

𝐹 =1

𝑛∑ 𝐹𝑗

𝑛

𝑗=1

e) Maksimum latenees, yaitu besarnya simpangan maksimum atau selisih waktu

penyelesaian seluruh job yang dijadwalkan terhadap batas waktu

penyelesaian job tersebut, dimana Lmaks = maks {I}.

f) Mean tardiness, merupakan rata-rata keterlambatan seluruh job yang

dijadwalkan dan dapat dihitung dengan rumus sebagai berikut:

T = 1

𝑛 ∑ 𝑇𝑖𝑛

𝑖=1

2. Kriteria berdasarkan atribut pabrik

a) Utilitas mesin, merupakan rasio dari jumlah mesin yang dibebankan pada

mesin dengan rentan waktu untuk menyelesaikan seluruh tugas pada semua

mesin.

U = ∑ (𝑈𝑗)𝑛

𝑗=1

𝑚 dimana 𝑈𝑚 =

∑ (𝑇𝑗)𝑛𝑗=1

𝐹𝑚𝑎𝑥

12

b) Minimasi makespan, yaitu jangka waktu penyelesaian seluruh job yang akan

dijadwalkan yang merupakan jumlah dari seluruh proses.

Ms = ∑𝑛𝑘=1 ∑𝑛

𝑘=1 𝑡𝑖𝑘

c) Pemenuhan due date, merupakan penyelesaian pekerjaan sesuai dengan

batas waktu yang ditentukan oleh pelanggan dimana harus selalu dilakukan

produsen untuk mempertahankan pelanggannya.

2.8 Penjadwalan Flowshop

Tipe penjadwalan flowshop adalah pergerakan dari unit satu ke unit yang

lain secara terus menerus dengan melewati workstation dan disusun berdasarkan

produk yang di buat (Baker & Trietsch, 2009). Menurut Pinedo (2012), sistem

produksi flowshop memiliki berbagai aturan yaitu:

1. Flowshop, dimana job yang belum dikerjakan karena menunggu proses dari job

yang mendahului harus menunggu hingga job yang mendahului selesai diproses

pada suatu mesin.

2. Flexsible flowshop, dimana tipe flowshop ini memiliki routing yang berbeda

yang memungkinkan job yang datang untuk langsung masuk kedalam stasiun

kerja, kecuali bila tetap harus diproses pada routing yang sama.

2.9 Penjadwalan Fleksible Flowshop

Tipe penjadwalan flexsible flowshop adalah generalisasi dari tipe flow shop

yang pada dasanya terdapat m mesin yang disusun secara seri ke beberapa stage,

yang didalam stage tersebut terdapat sejumlah mesin identik yang disusun secara

pararel. Masing-masing job akan di proses melewati stage 1 kemudian stage 1 dan

seterusnya. Pada masing-masing stage, job akan diproses oleh salah satu mesin

identik (Pinedo, 2012). Adapun skema flexsible flowshop dapat dilihat pada gambar

2.1

13

S1 S2 Sk Sk1.1

1.2

1.M1

2.2

2.1 K.1

K.2

K.MK2.M2

K.1

K.2

K.MK

...... ... ...... ...

Gambar 2.1 Skema Flexsible FlowShop

Sumber : Kulcsar, 2005

Flexible flowshop disebut juga sebagai hybrid flowshop dan multiprocessor

flowshop. Hybrid flwoshop adalah generalisasi dari permasalahan flowshop klasik

dengan adanya bebrapa mesin pararel setiap stage atau tahap dari suatu proses

(Kulcsár & Erdélyi, 2005).

2.10 Prioritas Dispatching Rules

Penjadwalan flow shop dapat diselesaikan dengan menggunakan metode

heuristik (Baker & Trietsch, 2009). Dispatching rule atau sering diistilahkan

scheduling in advance merupakan teknik heuristik yang sering digunakan dalam

penjadwalan. Beberapa metode dispatching rules adalah:

1. First Come First Serve (FCFS). Menurut aturan ini, urutan penjadwalan

dilakukan berdasarkan waktu kedatangan job atau pesanan pelanggan. Jadi, job

yang pertama kali datang, akan dikerjakan terlebih dahulu dan begitu seterusnya

untuk job-job berikutnya.

2. Earliest Due Date First (EDD) Menurut aturan ini, urutan penjadwalan

dilakukan berdasarkan pada due date setiap job. Aturan ini mengabaikan waktu

kedatangan dan total waktu proses setiap job. Artinya job yang memiliki due

date yang paling awal diantara job-job lainnya dipilih sebagai job yang memiliki

prioritas paling tinggi untuk diproses pada sebuah mesin. Aturan ini cenderung

digunakan untuk meminimalkan maximum lateness pada job-job yang ada dalam

antrian.

3. Longest Processing Time (LPT)Dengan menggunakan aturan ini, proses

dengan waktu operasi yang paling panjang akan dijadwalkan terlebih dahulu.

Aturan ini juga sangat sederhana yaitu dengan cara mengurutkan pekerjaan

14

dari yang mempunyai waktu proses terbesar hingga yang terkecil (t1≥ t2≥…≥

tn). Setelah itu penjadwalan dilakukan berdasarkan urutan tersebut.

4. Shortest Processing Time First (SPT). Menurut aturan ini, job diurutkan

berdasarkan pada lamanya waktu proses tiap job. Jadi job yang mempunyai

waktu proses paling singkat akan diproses terlebih dahulu dan kemudian

dilanjutkan job-job lainnya sampai pada job yang paling lama waktu prosesnya.

2.11 Output Penjadwalan

Suatu aliran kerja dapat dikatakan lancar apabila alur kerja tersebut

membentuk aktivitas-aktivitas output, dimana menurut (Ginting, 2009) ada

beberapa output yang dihasikan dalam proses tersebut, diantaranya:

1. Pengurutan (sequencing)

Sequencing merupakan penugasan tentang order-order mana yang harus

diprioitaskan terlebih dahulu bila suatu fasilitas harus memproses banyak job

dalam satu waktu.

2. Pembebanan (loading)

Pembebanan dilakukan dengan menugaskan order-order fasilitas, operator-

operator dan berbagai alat tertentu.

3. Prioritas job (dispatching)

Dispatching merupakan prioritas tentang job mana yang akan diseleksi dan

diprioritaskan untuk dapat diproses terlebih dahulu.

4. Pengendalian kinerja penjadwalan

Pengendalian kerja dilakukan dengan melakukan peninjauan terhadap status

order-order pada saat melalui sistem tertentu dan mengatur kembali urutan-

urutannya.

5. Updating Jadwal

Melakukan revisi-revisi pada aturan prioritas sebagai bentuk refleksi jika adanya

kondisi operasi yang memungkinkan untuk di ganti.

6. Updating Schedules

Pembuatan jadwal terbaru jika pada kondisi dilapangan terjadi masalah baru

yang memang perlu diakomodasi.

15

2.12 Gantt Chart

Menurut Heizer dan Render (2005), Gantt Chart merupakan diagram

perencanaan yang digunakan untuk penjadwalan sumber daya dan alokasi waktu.

Gantt Chart adalah contoh teknik non-matematis yang banyak digunakan dan

sangat popular di kalangan para manajer karena sederhana dan mudah dibaca. Gantt

Chart dapat membantu penggunanya untuk memastikan bahwa,

a. Semua kegiatan telah direncanakan

b. Urutan kinerja telah diperhitungkan

c. Perkiraan waktu kegiatan telah tercatat

d. Keseluruhan waktu proyek telah dibuat

Gantt Chart sangat mudah dipahami, balok horizontal (horizontal bar)

dibuat pada tiap kegiatan proyek sepanjang garis waktu. Gantt Chart juga dapat

digunakan untuk penjadwalan operasi yang berulang. Gantt chart digunakan untuk

penjadwalan sederhana atau proyek-proyek yang kegiatannya tidak terlalu

berkaitan atau proyek kecil, sedangkan network untuk penjadwalan proyek yang

rumit.

Gantt chart tidak bisa secara eksplisit menunjukkan keterkaitan antara

aktivitas dan bagaimana satu aktivitas berakibat pada aktivitas lain bila waktunya

terlambat atau dipercepat, sehingga perlu dilakukan modifikasi terhadap Gantt

chart. Untuk mengatasi kekurangan-kekurangan yang ada pada Gantt chart maka

dikembangkan sebuah teknik baru yaitu jaringan (network). Berikut merupakan

contoh pengerjaan produk di suatu perusahaan manufaktur:

Gambar 2.2 Gantt chart

16

Kelebihan penggunaan Gantt Chart, diantaranya :

1. Dapat menunjukkan waktu, kegiatan dan urutan kegiatan.

2. Jika jumlah kegiatan tidak terlalu banyak atau hanya sekedar jadwal induk, maka

metode Gantt Chart menjadi pilihan pertama dalam proses perencanaan dan

pengendalian kegiatan, karena mudah dipahami oleh semua lapisan pelaksana

proyek.

Dari kelebihan diatas Gantt Chart juga memiliki kelemahan, antara lain

1. Tidak memperlihatkan saling ketergantungan dan hubungan antar kegiatan

sehingga sulit diantisipasi jika terjadi keterlambatan suatu kegiatan terhadap

jadwal keseluruhan proyek.

2. Tidak mudah dilakukan perbaikan dan pembaharuan (updating) disebabkan

Gantt Chart baru harus dibuat kembali (tidak efesien), padahal pembuatan ulang

akan memakan waktu dan jika tidak dilakukan segera maka peta tersebut akan

menurun daya gunanya.

3. Untuk proyek yang berukuran sedang dan besar serta kompleks, maka Gantt

Chart tidak mampu menyajikan jadwal secara sistematis dan mengalami

kesulitan dalam menentukan keterkaitan antar kegiatan.

2.13 Energi Proses

Konservasi adalah pelestarian atau perlindungan. Sedangkan untuk

konservasi energi adalah kegiatan pemanfaatan energi secara efisien dan

rasional tanpa mengurangi penggunaan energi yang memang benar-benar

diperlukan. Tujuan konservasi energi adalah untuk memelihara kelestarian sumber

daya alam yang berupa sumber energi melalui kebijakan pemilihan teknologi dan

pemanfaatan energi secara efisien untuk mewujudkan kemampuan penyediaan

energi.

Pada industri manufaktur, peralatan yang paling banyak dipakai dalam

produksi adalah peralatan yang menggunakan daya listrik sebagai energi atau

tenaga untuk dapat mengerakkan peralatan tersebut. Biaya Listrik merupakan salah

satu biaya operasional produksi yang tertinggi setelah biaya Tenaga Kerja

(Manpower). Pada umumnya, biaya listik yang digolongkan sebagai “Electric

Utility Cost” memakan porsi biaya sekitar 7% ~ 10% dari total biaya operasional

17

produksi sehingga sangat penting sekali bagi kita untuk melakukan penghematan

dan optimasi pemakaian peralatan listrik tersebut (Kadir et al. 2011). Berikut ini

cara untuk menghitung biaya pemakaian listrik untuk peralatan-peralatan yang

sering digunakan dalam produk.

a. Menghitung kWh

kWh Pemakaian Listrik = daya alat listrik x lama pemakaian (dalam jam)

b. Menghitung biaya listrik

Biaya Listrik = Pemakaian (kWh) x Tarif Dasar Listrik

(Sumber: PLN Persero batam)

2.14 Algoritma Aturan Prioritas Aliran Fleksible Flowhop Mesin Pararel

Identik

Masalah penjadwalan berupa sequence dependent setup merupakan masalah

yang terjadi pada beberapa sistem produksi. Ketika suatu mesin digunakan untuk

memproses beragam tipe produk, maka bisa muncul waktu dan biaya setup mesin

akibat adanya pergantian tipe produk. Bila setup mesin sering dilakukan dan

waktunya cukup besar, maka tentunya akan berpengaruh terhadap penjadwalan dan

biaya energi mesin yang dikeluarkan, sehingga konsekuensinya kita harus

mempertimbangkan pengaruh setup mesin dalam penjadwalan.

Salah satu metode heuristik dalam memecahkan masalah penjadwalan

adalah metode priority dispatching rule, metode ini berprinsip pembuatan jadwal

secara bertahap dalam pengerjaannya, dengan menggunakan aturan ini, proses

dengan waktu operasi yang paling panjang akan dijadwalkan terlebih dahulu

Metode longest processing time merupakan metode penjadwalan yang memberikan

prioritas tertinggi pada waktu penyelesaian job paling lama diselesaikan. Adapun

algoritma longest processing time (LPT) sebagai berikut (Ginting, 2009):

a. Urutkan semua tugas menururt waktu proses terpanjang (longest processing

time). Pekerjaan yang memiliki waktu yang terpanjang dapatkan pada urutan

pertama.

b. Urutkan masing-masing tugas sesuai dengan waktu proses terpanjang pada

masing-masing mesin sesuai dengan aturan waktu proses terpanjang.

18

c. Setelah semua tugas-tugas selesai diurutkan, balikan urutan pada masing-

masing mesin sesuai dengan aturan waktu proses terpanjang.

Menurut Sriskandarajah & Sethi (1989), penyelesaian penjadwalan untuk

flexible flowshop dengan menggunakan kombinasi LPT dan algoritma heuristik ada

3 tahapan yaitu sebagai berikut :

1. Membentuk kelompok mesin, masing-masing berisi mesin dari masing-masing

pusat. Masing-masing mesin memiliki satu mesin pusat seperti

𝑚1, 𝑚2, 𝑚3, … , 𝑚𝑛 dimana 𝑚1 adalah mesin pusat dan 𝑚2, 𝑚3 dan seterusnya

adalah mesin paralel.

2. Gunakan metode LPT untuk menetapkan job untuk masing-masing kelompok

mesin (flow shop). Untuk setiap job 𝐽𝑗, 1 ≤ J ≤ n, untuk menemukan total waktu

job 𝑡𝑡𝑗= 𝑡1𝑗+𝑡2𝑗+⋯+𝑡𝑚𝑗

3. Karena setiap flowshop terdiri dari atas beberapa mesin, kita dapat memecahkan

setiap flowshops m secara optimal menggunakan algoritma yang telah diusulkan

oleh

a. Johnson (1954) dengan kasus buffer tidak terbatas.

b. Gilmore dan Gomory (1964) untuk kasus tanpa menunggu.

Dan untuk algoritma menggunakan LN dimana algoritma LN digunakan

untuk menjadwalkan sequencing pekerjaan dalam aliran Flexible Flowshop

beberpa mesin identik (Hong et al., 2006).

2.15 Metode Algoritma LN

Persoalan penjadwalan mesin kelompok pada penentuan urutan pekerjaan

dapat digunakan untuk memaksimalkan atau meminimalkan beberapa ukuran

efektivitas. Dalam metode algoritma heuristik baru telah dilakukan penelitian untuk

meminimalkan kriteria makespan dari persoalan penjadwalan mesin kelompok.

Algoritma baru ini didasarkan pada kenyataan bahwa pekerjaan dengan jumlah

waktu pemrosesan rata-rata yang lebih tinggi seharusnya diberi prioritas lebih

tinggi dalam menghasilkan jadwal parsial yang pada akhirnya mengarah pada

penentuan jadwal yang lengkap. Langkah-langkah yang terkait dengan metode

heuristik telah diterapkan pada aplikasi dunia nyata yang dipilih dari publikasi.

19

Dalam perkembangannya algortima LN dikembangkan oleh Rasaratnam

Logendran and Nudtapon Nudtasomboon digunakan untuk menjadwalkan

sequencing pekerjaan dalam aliran Flexible Flowshop beberpa mesin identik.

Dalam satu set pekerjaan independen n, masing-masing memiliki m (m> 2) tugas

(T11, T21,, ..., Tm1, T12, T22, ..., T(m-1) n,T mn) yang harus dijalankan dalam

urutan yang sama pada mesin m (P1, P2, ..., Pm), algoritma penjadwalan LN

melakukan penyelesaian yang minimum untuk job terakhir, dalam algoritma LN

ada 11 langkah yang harus di lakukan untuk mendapatkan urutan penjadwalan

antara lain :

a. Langkah 1:

Untuk setiap pekerjaan i, menghitung waktu pengerjaan rata-rata setiap tugas,

T𝑖𝑎𝑣𝑔 = (∑ 𝑡𝑗𝑖)/𝑚

𝑚

𝑗=1

Dimana 𝑡𝑗𝑖 adalah waktu pelaksanaan yang diperlukan untuk J-ke dari

pekerjaan i-ke.

b. Langkah 2: Mengurutkan pekerjaan dalam urutan menurun dari Ti avg

c. Langkah 3: Pilih dua pekerjaan pertama dari daftar diurutkan pada Langkah 2

dan menghasilkan dua jadwal parsial.

d. Langkah 4: Hitung waktu penyelesaian total masing-masing jadwal parsial

yang dihasilkan pada Langkah 3.

e. Langkah 5: Jaga jadwal parsial dengan total waktu penyelesaian lebih kecil.

f. Langkah 6: Set k = 3.

g. Langkah 7: Ulangi langkah 8 sampai 11 untuk k> n

h. Langkah 8: Pilih pekerjaan k-th dari daftar diurutkan pada Langkah 2 dan

menghasilkan k jadwal parsial dengan menyisipkan pekerjaan k-th di jadwal

parsial yang disimpan terakhir.

i. Langkah 9: Hitung waktu penyelesaian total masing-masing jadwal parsial

dihasilkan pada yang langkah 8.

j. Langkah 10: Jaga jadwal parsial dengan total waktu penyelesaian minimum.

k. Langkah 11: Set k = k + 1

20

Setelah langkah 11, penjadwalan selesai dan waktu penyelesaian telah ditemukan.

2.16 Metode Algoritma LPT-LN

Di masa lalu, Sriskandarajah dan Sethi mengusulkan algoritma heuristic

untuk memecahkan persoalan penjadwalan fleksibel flowshop dengan dua pusat

mesin. Metode kombinasi LPT-LN adalah metode perluasan algoritma yang sudah

ada sebelumnya. Dimana Metode LPT (longest processing time) digunakan untuk

menentukan atau menetapkan pekerjaan untuk setiap mesin kelompok sedangan

algoritma LN digunakan untuk menangani pengurutan pekerjaan pada setiap mesin

kelompok, metode ini dapat menghemat waktu penyelesaiannya lebih banyak dari

pada pendekatan yang optimal dan diperoleh sedikit dari solusi optimal. Dengan

demikian lebih cocok untuk nyata aplikasi. Dalam penyelesaian penjadwalan

dengan algoritma LPT-LN ada tiga bagian dalam penyelesaiannya dan disetiap

bagian terdapat beberapa langkah untuk pengerjaannya. Langkah-langkah dapat

dilihat pada gambar Flowchart 2.3 sebagai berikut (Hong et al., 2006):

21

Mulai

Bentuk Kelompok Mesin

Jumlah Waktu Total Masing-

masing Job

Urutkan Waktu Dari Terbesar ke

Terkecil

Cari Waktu Minimum fi antara

Semua Flowshop

Menetapkan Job i Dalam daftar

Urutan Fi

Jumlah Total Waktu Proses

Hapus Pekerjaan Job i dari Daftar

Pekerjaan

Jika Daftar Pekerjaan

Habis

Menghitung Waktu Rata-rata setiap

Tugas

Mengurutkan Pekerjaan dalam

Urutan Menurun dari Hasil Rata-

rata

Pilih Pekerjaan Pertama

Hitung Waktu Penyelesaian

Mencari Jadwal Parsial

Carilah Waktu Penyelesaian Akhir

Selesai

No

Yes

Bagian 1

Bagian 2

Bagian 3

Gambar 2.3 Flowchart Pengerjaan LPT-LN

22

Berikut penjelasan bagaimana proses penelitian yang akan dilakukan mulai

awal sampai selesai. Deskripsi dari metodologi penelitian ini adalah sebagai

berikut:

1. Bagian 1

Bentuk kelompok mesin, masing-masing berisi mesin dari masing-masing mesin

utama.

a. Langkah 1

Membentuk pasangan p mesin, masing-masing berisi satu mesin dari masing-

masing mesin utama. F1, F2, ..., Fp.

b. Langkah 2

Inisialisasi waktu penyelesaian setiap flowshop f1, f2,…,fp ke nol

2. Bagian 2

Menetapkan pekerjaan untuk kelompok mesin.

c. Langkah 3

Untuk setiap pekerjaan Ji, 1≤ i ≤ n, cari total waktu pengerjaan tti = t 1i + t2i

+ ... + tmi.

d. Langkah 4

Mengrutkan pekerjaan dalam urutan waktu pemrosesan terbesar ke terkecil

dari total waktu pengolahan tti

e. Langkah 5

Mencari waktu proses minimum Fi antara semua flowshop.

f. Langkah 6

Menetapkan pekerjaan Job pertama dalam daftar Fi dan diurutkan.

g. Langkah 7

Menambah total waktu tti dari Ji untuk total waktu yang dibutuhkan dari

flowshop yang dipilih Fi, yaitu: fi = fi + tt i.

h. Langkah 8

Hapus pekerjaan Ji dari daftar pekerjaan.

i. Langkah 9

Ulangi langkah 5 sampai 8 sampai daftar pekerjaan kosong.

23

Setelah langkah 9, pekerjaan ini terkelompok ke dalam kelompok p dan

dialokasikan ke pasangan p mesin flowshop.

3. Bagian 3

Mengurutkan pekerjaan di setiap flowshop.

j. Langkah 10

Untuk setiap pekerjaan J, menghitung waktu rata-rata setiap tugas, di mana

𝑡𝑗𝑖 adalah waktu pelaksanaan diperlukan untuk J-ke dari pekerjaan i-ke.

T𝑖𝑎𝑣𝑔 = (∑ 𝑡𝑗𝑖)/𝑚

𝑚

𝑗=1

k. Langkah 11

Mengurutkan pekerjaan dalam urutan menurun dari Ti avg

l. Langkah 12

Pilih dua pekerjaan pertama dari daftar diurutkan pada Langkah 11 dan

menghasilkan dua jadwal parsial.

m. Langkah 13

Hitung waktu penyelesaian total masing-masing jadwal parsial di Langkah

12.

n. Langkah 14

Jaga jadwal parsial dengan waktu total penyelesaian yang lebih kecil.

o. Langkah 15

Set k = 3

p. Langkah 16

Ulangi langkah 17 sampai 20 untuk k> n

q. Langkah 17

Pilih pekerjaan k-th dari daftar diurutkan pada langkah 11 dan menghasilkan

k jadwal parsial dengan menyisipkan pekerjaan k-th di jadwal parsial yang

disimpan terakhir.

r. Langkah 18

Hitung waktu penyelesaian total masing-masing jadwal parsial dihasilkan

pada yang langkah 17.

24

s. Langkah 19

Jaga jadwal parsial dengan total waktu penyelesaian minimum.

t. Langkah 20

Set k = k + 1 dan lakukan langkah 16.

u. Langkah 21

Menunjukkan jadwal yang dipilih di Fi sebagai QFi dan menetapkan waktu

penyelesaian akhir dari masing-masing flowhop.

v. Langkah 22

Waktu penyelesaian akhir semua flowshop.

Setelah Langkah 22, penjadwalan selesai dan penyelesaian keseluruhan

waktu ff telah ditemukan.

Notasi-notasi yang digunakan:

n = Jumlah pekerjaan.

mci = Jumlah mesin-i di mesin utama.

F i = Flowshop pada mesin group.

f ni = Flowshop ke-n pada mesin ke-i.

f Ji = Waktu penyelesaian job j pada mesin ke i.

T Jfi = Total waktu dibutuhkan untuk pekerjaan j pada flowshop n mesin i.

t Ji = Waktu dibutuhkan untuk pekerjaan j pada mesin i.

QF i = Kelompok pekerjaan yang dijalankan pada job ke-i.

FF = Waktu penyelesaian akhir seluruh jadwal.