BAB 2

LANDASAN TEORI

2.1 Pengertian Penjadwalan

Penjadwalan adalah aspek yang penting dalam pengendalian operasi baik

dalam industri manufaktur maupun jasa. Dengan meningkatkan titik berat kepada

pasar dan volume produksi untuk meningkatkan kepuasan konsumen. Dengan

penjadwalan yang efektif dapat meningkatkan keuntungan dalam fungsi operasi

diwaktu yang akan datang.

Penjadwalan adalah suatu proses pengambilan keputusan yang memainkan

peranan penting dalam kebanyakan bidang manufaktur dan pelayanan industri.

Penjadwalan digunakan dalam pengadaan bahan dan produksi, dalam transportasi dan

distribusi dan dalam proses informasi dan komunikasi.

Ada beberapa tipe berbeda dari masalah penjadwalan yang dihadapi oleh

perusahaan adalah sebagai berikut [2,hlm 413]:

1. Job shop scheduling

Job shop scheduling secara umum lebih dikenal sebagai shop floor control,

yang merupakan kegiatan penyusunan input (memasang yang diperlukan)

menjadi output (produk).

30

2. Personnel scheduling

Personnel scheduling adalah hal yang penting dalam industri manufaktur dan

jasa. Walaupun penjadwalan pembagian waktu dalam lantai produksi lebih

diutamakan dari pengendalian dalam lantai produksi itu sendiri, tenaga kerja

juga dapat menjadi masalah yang besar. Sebagai contoh misalnya

penjadwalan tenaga medis dalam rumah sakit. Penentuan waktu seperti jam

kerja penuh, shift pagi/ malam dan subkontrak menjadi masalah dalam

penjadwalan tenaga kerja ini.

3. Facilities scheduling

Penjadwalan ini menjadi sangat penting ketika fasilitas menjadi hal yang

utama. Sebagai contoh adalah penjadwalan ruang operasi pada rumah sakit.

Untuk meningkatkan pelayanan kesehatan, beberapa rumah sakit

menggunakan fasilitas ini.

4. Vehicle scheduling

Perusahaan manufaktur harus mengirim produk mereka dengan biaya dan

waktu yang efisien. Contoh dari penjadwalan ini adalah penjadwalan

pengiriman peralatan, pos dan pengiriman untuk pelanggan ditempat yang

berbeda.

5. Vendor scheduling

Perusahaan dengan sistem JIT (just in time), penjadwalan pengiriman adalah

hal yang penting. Bagian penjualan harus mengkoordinasikan dengan sistem

31

dari jumlah produk yang akan dikirim untuk menjamin bahwa JIT berfungsi

dengan efisien.

6. Project scheduling

Rencana adalah penghubung dari tugas-tugas. Walaupun beberapa tugas dapat

dikerjakan bersama-sama, tetapi beberapa tugas tidak dapat mulai dikerjakan

hingga tugas yang sebelumnya selesai. Project yang kompleks mungkin

melibatkan ribuan tenaga kerja yang saling berkoordinasi melengkapi rencana

tersebut dengan waktu dan biaya. Penjadwalan ini merupakan komponen yang

penting dari fungsi perencanaan.

7. Dinamic versus static scheduling

Bermacam-macam pesanan datang secara simultan untuk diproses di sebuah

mesin. Dalam kenyataannya masalah penjadwalan yang ada bersifat dinamik

dalam arti job akan datang berkelanjutan sepanjang waktu.

Secara umum, penjadwalan merupakan suatu proses dalam perencanaan dan

pengendalian produksi yang merencanakan produksi serta pengalokasikan sumber

daya pada suatu waktu tertentu dengan memperhatikan kapasitas sumber daya yang

ada.

Menurut Ricard W. Conway, penjadwalan adalah suatu proses pengurutan

pembuatan produk secara menyeluruh pada beberapa mesin.

Menurut Roger Schroeder, penjadwalan adalah proses untuk menentukan:

1. Sequence, yang berarti pengurutan pekerjaan yang akan dilakukan

sebelumnya.

32

2. Timing, yang berarti menentukan saat mulai dan saat akhir setiap pekerjaan.

Menurut Baker, penjadwalan didefinisikan sebagai suatu proses

pengalokasian sumber daya/ mesin-mesin yang ada untuk melaksanakan tugas-tugas

yang ada dalam suatu waktu tertentu [3, hlm 2]. Definisi ini dapat dijabarkan menjadi

dua arti yaitu:

1. Penjadwalan sebagai fungsi dari pengambilan keputusan\

Penjadwalan merupakan suatu proses untuk menentukan sebuah urutan.

2. Penjadwalan merupakan suatu teori

Penjadwalan adalah kumpulan dari prinsip-prinsip, model, teknik dan

kesimpulan logis dalam pengambilan keputusan penjadwalan merupakan

bagian dari shop floor control.

Keputusan yang dibuat dalam penjadwalan meliputi pengurutan pekerjaan

(sequencing), waktu mulai dan selesai pekerjaan (timing), urutan operasi untuk suatu

pekerjaan (routing). Masalah penjadwalan selalu berkaitan dengan pengurutan

produksi (sequencing) yang didefinisikan sebagai penentu urutan-urutan kedatangan

dari bermacam-macam pekerjaan yang harus diselesaikan dalam jangka waktu

tertentu. Masalah penjadwalan seringkali muncul jika terdapat sekumpulan tugas

secara bersamaan, sedangkan peralatan yang dimiliki terbatas.

Masukkan dari suatu penjadwalan mencakup jenis dan banyaknya part yang

akan dioperasikan, urutan ketergantungan antar operasi, waktu proses untuk masing-

masing operasi, serta fasilitas yang dibutuhkan oleh setiap operasi. Keluaran

33

penjadwalan meliputi dispatch list (daftar urutan-urutan pemrosesan part serta waktu

mulai dan selesai dari pemrosesan part).

Dengan begitu, adalah sangat jelas bagi perusahaan akan pentingnya

penjadwalan [10, hlm 466]:

1. Dengan penjadwalan secara efektif, perusahaan menggunakan asetnya dengan

efektif dan menghasilkan kapasitas uang yang diinvestasikan menjadi lebih

besar, yang sebaliknya akan mengurangi biaya.

2. Penjadwalan menambah kapasitas dan fleksibilitas yang terkait memberikan

waktu pengiriman yang lebih cepat dan dengan demikian pelayanan kepada

pelanggan menjadi lebih baik.

3. Keuntungan yang ketiga dari bagusnya penjadwalan adalah keunggulan

kompetitif dengan pengiriman yang bisa diandalkan.

2.2 Tujuan Penjadwalan

Kebanyakan tujuan dari penjadwalan adalah meminimalkan total flow time,

total tardiness, maximum completion time, maximum tardiness, lateness atau jumlah

dari pekerjaan yang tepat waktu. Secara umum penjadwalan mempunyai tujuan

seperti:

1. Efisiensi pemakaian sumber daya dan minimasi makespan

2. Agar lebih responsive terhadap permintaan. Minimasi rata-rata flow time

atau rata-rata waktu menunggu (tardiness).

3. Memenuhi batas waktu (due date, tardiness, lateness).

34

Menurut Baker, penjadwalan memiliki beberapa tujuan yaitu [3, hlm 5]:

1. Meningkatkan produktivitas mesin, yaitu dengan mengurangi waktu

menganggur.

2. Mengurangi persediaan barang setengah jadi (work in process inventory)

untuk mengurangi biaya penyimpanan dengan jalan mengurangi jumlah

rata-rata pekerjaan yang menunggu dalam antrian suatu mesin karena

masih terlalu sibuk.

3. Mengurangi waktu keterlambatan karena batas waktu (due date) telah

dilampaui dengan cara mengurangi maksimum keterlambatan maupun

dengan mengurangi jumlah pekerjaan yang terlambat.

4. Meminimasi ongkos produksi.

5. Pemenuhan due date, karena dalam kenyataannya apabila terjadi

keterlambatan pemenuhan due date yang telah ditetapkan dapat dikenakan

suatu denda/ pinalty.

Menurut Baker, jika makespan suatu penjadwalan adalah konstan, maka

urutan kerja yang tepat akan menurunkan flow time dan rataan work in process.

35

2.3 Fungsi Penjadwalan

Fungsi dari penjadwalan berbeda-beda, hal tersebut bergantung dari tipe

operasinya. Macam-macam tipe operasi adalah sebagai berikut [4, hlm 45]:

1. In process industries

Seperti di pabrik-pabrik kimia dan farmasi, penjadwalan bisa saja terdiri

dari pencampuran bahan-bahan, membersihkan kotoran, dan mulainya

memproduksi produk-produk lain. Program linear dapat menentukan biaya

termurah dari campuran bahan-bahan dan kuantitas pemesanan ekonomis

dengan dapat menentukan jangka waktu optimum dari suatu produksi

berjalan.

2. Untuk produk massal

Penjadwalan dari produksi akan sangat menentukan ketika jalur perakitan

telah dipasang. Keputusan penjadwalan dari hari ke hari terdiri dari

penentuan seberapa cepat waktu untuk menyelesaikan satu item dalam line

dan beberapa jam yang dibutuhkan per hari untuk menyelesaikan satu line.

3. Untuk proyek-proyek

Keputusan penjadwalan sangat banyak dan berhubungan dengan teknik

penjadwalan proyek seperti PERT dan CPM.

4. Untuk batch atau job shop production

Keputusan penjadwalan bisa menjadi sangat kompleks. Dalam kaitannya

dengan penjadwalan produksi, batch flow, job shop, dan cellular process

telah banyak ditemui. Dalam tiap kasus, jenis produk-produknya dibuat

36

secara normal dan banyak diantaranya make to order. Waktu yang

dibutuhkan untuk memproses masing-masing pekerjaan atau produk,

bervariasi dari pekerjaan satu ke pekerjaan lain karena perbedaan dalam

waktu set-up dan kebutuhan pemrosesan yang lain serta juga perbedaan

ukuran order pelanggan. Lingkungan batch production merupakan

lingkungan yang dinamis karena order-order dari pelanggan yang datang

secara berkesinambungan dan produk-produk yang telah jadi diproses

serta kemudian diantar ke pelanggan sepanjang waktu.

2.4 Permasalahan dalam Penjadwalan Produksi

Masalah penjadwalan seringkali muncul jika terdapat sekumpulan tugas yang

harus ditetapkan harus dikerjakan terlebih dahulu, bagaimana urutan kerja dari tugas-

tugas berikutnya, serta pengalokasian tugas pada mesin sehingga diperoleh suatu

proses yang terjadwal.

Pada umumnya persoalan penjadwalan ini dipecahkan dengan sendirinya

menurut kebiasaan tanpa memberikan perhatian yang lebih besar sehingga

pemecahan persoalan dengan suatu teknik baru akan lebih mudah dan lebih

menguntungkan. Cara yang umum dilakukan adalah cara yang didasarkan pada FCFS

(First Come First Serve), sehingga tugas yang datang lebih dahulu akan dilayani

lebih awal daripada tugas yang datang kemudian.

37

Secara umum, persoalan penjadwalan dapat dinyatakan sebagai berikut :

1. Misalkan α adalah risiko yang ditanggung karena mengerjakan tugas A

lebih dahulu daripada tugas B.

2. Misalkan β adalah risiko yang ditanggung karena mengerjakan tugas B

lebih dahulu dari tugas A.

3. Jika α lebih baik daripada β, maka tugas B dikerjakan lebih awal

kemudian diikuti tugas A.

Pemilihan α dan β ini dapat dikaikan dengan pemilihan kriteria optimalitas

yang diterapkan oleh pengambil keputusan.

2.5 Istilah-istilah dalam Penjadwalan Produksi

Dalam membahas masalah penjadwalan biasanya akan dijumpai beberapa

variabel dan istilah, dalam penulisan ini digunakan variabel j = job dan i = operasi.

Definisi dari istilah-istilah yang sering digunakan ialah:

a. Waktu proses ( ijt )

Adalah waktu yang diperlukan untuk menyelesaikan suatu operasi j dari suatu

job i (termasuk waktu set up, penghentian mesin dan waktu pemindahan

bahan ke mesin).

38

b. Makespan ( sM ) [2, hlm 419]

Adalah jangka waktu penyelesaian suatu penjadwalan yang merupakan

jumlah seluruh waktu proses.

∑= is tM

c. Ready time ( ijR )

Menyatakan job j operasi ke-1 siap untuk dijadwalkan.

d. Waiting Time ( jW )

Adalah waktu tunggu seluruh operasi dari suatu job

∑= ijj WW

e. Flow Time ( jF ) [2, hlm 419]

Adalah waktu antara suatu saat dimana suatu pekerjaan dapat diproses dengan

suatu saat dimana pekerjaan tersebut telah selesai dikerjakan.

jjj WtF +=

f. Completion Time ( jC )

Adalah jangka waktu antara permulaan bekerja ada pekerjaan pertama,

dimana waktu tersebut ditunjuk oleh t = 0 dan waktu pada saat pekerjaan j

selesai.

g. Rata-rata flow time [4, hlm 254]

Fs = ∑ jFn1

39

h. Due date ( jD )

Adalah batas waktu akhir suatu job harus diselesaikan.

i. Lateness ( jL )

Adalah penyimpangan waktu penyelesaian suatu job ke–j hingga saat due

date.

jjj dCL −=

jL < 0 , jika penyelesaian memenuhi batas akhir

jL > 0 , jika penyelesaian melewati batas akhir

j. Earliness ( jE )

Adalah saat penyelesaian terlalu awal yaitu sebelum due date. Earliness juga

disebut sebagai lateness negatif.

{ }jj LE −= ,0max

k. Rata-rata Lateness

=sL ∑ − )(1jj dG

n

l. Tardiness ( jT )

Adalah keterlambatan penyelesaian suatu pekerjaan hingga saat due date.

{ }jj LT ,0max=

m. Rata-rata Tardiness

sT = ∑ jTn1

40

n. Number of Tardiness

TN = ∑ jδ

jδ = 1, jika Tj > 0

jδ = 0, jika Tj < 0

o. Slack Time (Sj)

Adalah waktu sisa yang tersedia bagi suatu job.

jjj tdS −=

p. Utilitas Mesin (U)

Adalah rasio dari seluruh proses yang dibebankan pada mesin dengan rentang

waktu untuk menyelesaikan seluruh tugas pada semua mesin.

U = maxFmt j

×∑

Dimana : m = mesin

F max = Flowtime max

q. Tmax or Lmax

Tmax = max {0, Lmax}

Lmax = max {Lj}

r. Critical ratio

CR = j

j

Pta )(

tdta jj −=)(

41

dimana : ja (t) = allowance

jd = Due date

jP = Waktu untuk menyelesaikan operasi j

Sehingga :

jj StajP −= )(

jS = Slack Time

2.6 Kendala-kendala dalam Penjadwalan Produksi

Dalam pelaksanaanya, penjadwalan proses produksi ditingkat shop floor akan

mengalami gangguan atau hambatan yang dapat terjadi antara lain :

a. Mesin rusak

Pada saat mesin rusak, maka operasi-operasi yang akan menggunakan mesin

tersebut tidak dapat dikerjakan dan harus menunggu sampai mesin selesai

diperbaiki. Hal ini mengakibatkan terhentinya proses produksi dan

penjadwalan produksi semula menjadi tidak terpenuhi. Oleh karena itu, perlu

dilakukan penyesuaian pada jadwal semula sehingga diperoleh kembali

jadwal produksi yang feasible. Penjadwalan ulang ini dikenal dengan istilah

rescheduling. Informasi yang diperlukan adalah jenis dan nomor mesin yang

rusak, waktu terjadinya kerusakan, dan lamanya waktu perbaikan mesin.

42

b. Penambahan pesanan (order) baru

Pada saat produksi sedang berjalan, tidak tertutup kemungkinan bahwa terjadi

penambahan pesanan baru. Hal ini mengakibatkan pelaksanaan penjadwalan

yang belum memperhitungkan pesanan baru tersebut akan mengalami

gangguan atau kekacauan. Oleh karena itu, diperlukan penjadwalan ulang

dengan mempertimbangkan pesanan baru tersebut, sehingga produksi akan

tetap berada pada kondisi yang optimal serta shop floor dapat segera

menyesuaikan diri dengan penjadwalan yang baru tersebut. Informasi yang

diperlukan dari adanya pesanan baru tersebut adalah jenis produk yang

dipesan, routing pekerjaannya, jumlah pesanan dan due date yang diminta

konsumen.

c. Perubahan prioritas

Penambahan prioritas pembuatan produk akan mempengaruhi penjadwalan

yang telah dilakukan.

d. Perubahan due date

Produk yang mengalami perubahan due date akan menyebabkan perubahan

pada jadwal produksi semula. Perubahan due date ada dua macam yaitu due

date semakin maju dan due date semakin mundur. Penjadwalan produksi yang

semakin mundur tidak akan mengubah penjadwalan produksi dan tidak akan

mengakibatkan perubahan pada performansi penjadwalan semula. Tetapi,

perubahan due date yang semakin maju akan mengubah penjadwalan produksi

43

awal agar kriteria performansi yang dipilih dapat tetap dipertahankan dengan

adanya perubahan due date tersebut.

Pada dasarnya seluruh gangguan dan hambatan dalam melaksanakan

penjadwalan produksi dapat terjadi secara bersamaan maupun sendiri-sendiri.

2.7 Kriteria Optimalitas

Berdasarkan beberapa variabel yang telah dijelaskan, para ahli memberikan

berbagai kriteria ukuran kinerja penjadwalan sebagai berikut:

Minimasi Makespan : { }jCC maxmax =

Minimasi Mean Flow Time : ∑= jFn

F 1

Minimasi Mean Tardiness : ∑= jTn

T 1

Minimasi Maksimum Flowtime : )max( jFF =

Minimasi Mean Lateness : ∑= jLn

L 1

Minimasi Maksimum Tardiness : }max{max jTT =

44

Beberapa kriteria optimalitas dalam proses penjadwalan adalah:

1. Berkaitan dengan waktu

Dalam kaitannya dengan waktu, beberapa kriteria optimalitas yang dapat

digunakan adalah :

• Minimasi mean flowtime, kriteria ini menunjukkan rata-rata waktu

yang dihabiskan setiap komponen di lantai pabrik.

• Minimasi makespan, makespan adalah jumlah waktu yang dibutuhkan

untuk menyelesaikan seluruh proses pada semua komponen yang

dijadwalkan mulai dari saat pemrosesan pertama sampai komponen

terakhir selesai diproses.

• Pemenuhan due date, due date merupakan batas waktu yang

ditetapkan konsumen agar seluruh produk yang dipesan sudah siap.

Pihak produsen selalu berusaha untuk memenuhi due date tersebut,

terutama untuk produk-produk yang kritis, misalnya produk yang akan

diproduksi oleh perusahaan lain dan produsen betindak sebagai

supplier bagi perusahaan lain. Dalam hal ini, keterlambatan yang

terjadi akan menyebabkan waktu menunggu (idle) bagi perusahaan

lain dan akan berdampak negatif yaitu hilangnya kepercayaan

perusahaan tersebut kepada produsen sebagai supplier.

45

2. Berkaitan dengan ongkos

Kriteria ini lebih mengarah ke biaya produksi seperti inventory cost, penalty

cost, dan lain sebagainya dan tidak memperhatikan kriteria waktu yang ada

sehingga dengan satu penjadwalan produksi tertentu diharapkan mendapat

ongkos yang minimal.

3. Kriteria gabungan

Beberapa kriteria optimalitas tersebut dapat digabungkan dan dikombinasikan

sehingga menjadi beberapa kriteria yang sesungguhnya (penjadwalan yang

multi kriteria)

4. Kriteria proses [10, hlm 467]

Teknik penjadwalan yang benar tergantung pada volume pesanan, ciri operasi

dan keseluruhan kompleksitas pekerjaan, sekaligus pentingnya tempat pada

masing-masing dari empat kriteria.

Empat kriteria tersebut adalah:

a. Meminimalkan waktu penyelesaian. Ini dinilai dengan menentukan rata-

rata waktu penyelesaian.

b. Memaksimalkan utilasi. Ini dinilai dengan menentukan persentase waktu

fasilitas itu digunakan.

c. Meminimalkan persediaan barang dalam proses. Ini dinilai dengan

menentukan rata-rata jumlah pekerjaan dalam sistem. Hubungan antara

jumlah pekerjaan dalam sistem dan persediaan barang dalam proses adalah

46

tinggi. Dengan demikian semakin kecil jumlah pekerjaan yangada dalam

sistem, maka akan semakin kecil persediaannya.

d. Meminimalkan waktu tunggu pelanggan. Ini dinilai dengan menentukan

rata-rata jumlah keterlambatan.

2.8 Klasifikasi Penjadwalan Produksi

Penjadwalan produksi dapat berbeda-beda dilihat dari kondisi yang

mendasarinya. Beberapa model penjadwalan yang sering terjadi didalam proses

produksi berdasarkan beberapa keadaan antara lain adalah:

1. Berdasarkan mesin yang dipergunakan dalam proses :

a. Penjadwalan pada mesin tunggal (single machine shop)

b. Penjadwalan pada mesin jamak (m machine)

2. Berdasarkan pola aliran proses:

a. Penjadwalan flow shop, proses produksi dengan aliran flow shop

berarti proses produksi dengan pola aliran identik dari satu mesin

ke mesin lain. Walaupun pada flow shop semua tugas akan

mengalir pada jalur produksi yang sama, yang biasa dikenal

sebagai pure flow shop, tetapi dapat pula berbeda dalam dua hal.

Pertama, jika flow shop dapat menangani tugas yang bervariasi.

Kedua, jika tugas yang datang kedalam flow shop tidak harus

dikerjakan pada semua jenis mesin. Jenis flow shop seperti ini

disebut general flow shop.

47

Gambar 2.1 Gambar Lintasan Proses Flow Shop

b. Penjadwalan job shop, proses produksi dengan aliran job shop

berarti proses produksi dengan pola aliran atau rute proses pada

setiap mesin yang spesifik untuk setiap pekerjaan, dan mungkin

berbeda untuk tiap job. Akibat aliran proses yang tidak searah ini,

maka setiap job yang akan diproses pada satu mesin dapat

merupakan job yang baru atau job dalam proses , dan job yang

keluar dari satu mesin dapat merupakan job jadi atau job dalam

proses.

Gambar 2.2 Gambar Lintasan Proses Job Shop

3. Berdasarkan pola kedatangan job:

a. Penjadwalan statis yaitu job yang datang bersamaan dan siap

dikerjakan pada mesin yang tidak bekerja.

48

b. Penjadwalan dinamis yaitu kedatangan job yang tidak menentu

4. Berdasarkan sifat informasi yang diterima:

a. Penjadwalan deterministic yaitu informasi yang diperoleh pasti,

misalnya informasi tentang pekerjaan dan mesin seperti waktu

kedatangan pekerjaan dan waktu proses.

b. Penjadwalan stokastik yaitu informasi yang diperoleh tidak pasti

tetapi memiliki kecenderungan yang jelas atau menyangkut adanya

distribusi probabilitas tertentu.

2.9 Teknik Penyusunan Penjadwalan

Penjadwalan produksi harus disusun dengan tepat agar proses produksi

berjalan dengan baik. Penjadwalan melibatkan pembebanan tanggal jatuh tempo atas

pekerjaan-pekerjaan khusus, tapi banyak pekerjaan yang bersaing secara simultan

untuk sumber daya yang sama. Untuk membantu mengatasi kesulitan yang melekat

pada penjadwalan, kita bisa mengelompokkan teknik penjadwalan sebagai berikut

[10, hlm 468]:

1. Penjadwalan ke depan

Penjadwalan ke depan memulai skedul/ jadwal segera setelah persyaratan

diketahui, penjadwalan ke depan digunakan di beragam organisasi seperti

rumah sakit, klinik, restoran untuk makan malam, dan perusahaan alat-alat

pemesinan. Skedul-skedul tersebut disusun berdasarkan tanggal permulaan

operasi yang diketahui dan kemudian bergerak ke muka dari operasi pertama

49

sampai operasi terakhir untuk menentukan tanggal penyelesaian. Atau proses

penjadwalan dimulai dengan tanggal permulaan order tertentu dan tanggal

penyelesaian diwaktu yang akan datang ditentukan berdasarkan siklus

pemrosesan dan keterbatasan kapasitas. Dalam fasilitas ini, pekerjaan

dilaksanakan atas pesanan pelanggan dan sesegera mungkin dilakukan

pengiriman. Penjadwalan ke depan biasanya dirancang untuk menghasilkan

jadwal yang bisa diselesaikan meskipun tidak berarti memenuhi tanggal jatuh

temponya. Di dalam beberapa keadaan, penjadwalan ke depan menyebabkan

penumpukan barang dalam proses. Pendekatan ini banyak digunakan dalam

industri kimiawi, pemroses makanan dan industri lainnya dimana keluarannya

sangat dibatasi dalam jangka pendek oleh kapasitas-kapasitas yang tersedia,

karena untuk mengubahnya diperlukan waktu yang lama.

2. Penjadwalan ke belakang

Penjadwalan ke belakang dimulai dengan tanggal jatuh tempo, menjadwal

operasi final dahulu. Tahap-tahap dalam pekerjaan kemudian dijadwal, pada

suatu waktu, dibalik. Dengan menggunakan lead time untuk masing-masing

item, akan didapatkan waktu awal. Namun demikian, sumber daya yang perlu

untuk menyelesaikan jadwal bisa jadi tidak ada. Penjadwalan ke belakang

digunakan di lingkungan perusahaan manufaktur, sekaligus lingkungan

perusahaan jasa seperti catering atau penjadwalan pembedahan.

50

Dalam praktik, seringkali digunakan penjadwalan ke depan dan ke belakang

untuk mengetahui titik temu yang beralasan antara apa yang bisa dicapai dengan

tanggal jatuh tempo pelanggan.

Kerusakan mesin, ketidakhadiran, masalah mutu, kekurangan dan faktor-

faktor lain membuat pejadwalan menjadi lebih kompleks. Konsekuensinya, tanggal

penugasan tidak meyakinkan bahwa pekerjaan akan dilakukan sesuai dengan jadwal.

Banyak teknik khusus yang telah dibuat untuk membantu kita dalam mempersiapkan

jadwal yang dihandalkan.

2.10 Penjadwalan Flow Shop

Sistem penjadwalan dalam flow shop adalah penjadwalan dari seluruh job

dalam urutan proses yang sama dan masing-masing job menuju ke masing-masing

mesin dalam satu waktu tertentu [1, hlm 437]. Sistem ini dapat digambarkan seperti

urutan linear pada mesin-mesin seperti pada lini perakitan. Setiap job diproses sesuai

dengan urutan prosesnya dan dari satu mesin ke mesin lainnya.

Penjadwalan yang memiliki urutan yang sama atas penggunaan masing-

masing mesin disebut dengan permutation schedules. Dalam kriteria pengukuran

diperlukan penjadwalan harus dipertimbangkan ketika didapatkan solusi yang optimal

dengan meningkatkan jumlah job atau mesin.

Pada umumnya, setiap operasi berikutnya berasal dari satu operasi yang

mendahuluinya dan operasi kedua dari terakhir mempunyai satu operasi yang

mengikutinya. Oleh karena itu, setiap job memiliki urutan operasi yang spesifik untuk

51

menyelesaikan job tersebut. Tipe struktur ini sering disebut sebagai linear predence

structure.

Gambar 2.3 Gambar Linear Predence Structure

Lantai produksi terdiri dari m mesin berbeda, dan setiap job terdiri dari m

operasi yang memerlukan mesin yang berbeda. Karakteristik flow shop dinyatakan

dengan aliran pekerjaan yang terarah. Pada pekerjaan flow shop, penomoran mesin

dimungkinkan sehingga jika operasi ke-j dari suatu job mendahului operasi ke-k,

maka mesin yang diperlukan dari operasi ke-j mempunyai nomor yang lebih kecil

dibandingkan dengan mesin yang dibutuhkan oleh operasi ke-k, mesin-mesin dalam

flow shop diberi nomor 1, 2, 3,…….., m; dan operasi job ke-i ditandai dengan (i,1),

(i,2),…….,(i,m).

Setiap job dapat diperlakukan seolah-olah job tersebut memiliki m operasi

yang tetap. Aliran pekerjaan flow shop terbagi menjadi dua, yaitu pure flow shop dan

general flow shop. Pada aliran pekerjaan pure flow shop, setiap job memiliki satu

operasi pada setiap mesin. Sedangkan pada general flow shop, suatu pekerjaan

dimungkinkan terdiri kurang dari m operasi dengan operasi-operasi pada mesin-mesin

yang tidak berdekatan (bersebelahan), dan operasi terakhir tidak selalu dimulai pada

mesin 1 dan diakhiri pada mesin m.

52

Karakteristik dasar penjadwalan flow shop adalah sebagai berikut:

a. Terdapat n job yang tersedia dan siap diproses pada waktu t = 0

b. Waktu set up independent terhadap urutan pengerjaan.

c. Terdapat m mesin berbeda, yang tersedia secara kontinu.

d. Operasi-operasi individual tidak dapat dipecah-pecah.

Teorema-teorema yang dapat digunakan untuk penjadwalan flow shop dengan

m mesin adalah:

a. Penjadwalan heuristic Campbell, Dudek and Smith (CDS).

Dalam prakteknya, masalah penjadwalan sering kali melibatkan sejumlah besar

pekerjaan yang harus diproses oleh banyak mesin. Penjadwalan heuristic CDS

adalah sebuah metode penjadwalan pada mesin seri yang merupakan pendekatan

dari Johnson’s rule. Johnson’s rule atau aturan Johnson merupakan algoritma

yang digunakan untuk menjadwalkan sejumlah pekerjaan pada dua mesin seri.

Algoritma ini bertujuan untuk meminimasikan nilai makespannya. Johnson’s rule

telah dikembangkan oleh Campbell, Dudek, and Smith dan digunakan untuk

menjadwalkan sejumlah pekerjaan (n job) yang dikerjakan pada mesin (m mesin)

yang memungkinkan untuk menghasilkan alternatif penjadwalan sebanyak jumlah

mesin - 1 penjadwalan, dan memilih yang terbaik untuk diimplementasikan.

Heuristic CDS dikembangkan sejak tahun 1970. Heuristic ini menghasilkan

urutan m – 1 dan pilihan dengan makespan terkecil [1, hlm 443]. Dalam

prakteknya, masalah penjadwalan seringkali melibatkan sejumlah besar job yang

harus diproses oleh banyak mesin. Untuk kasus seperti ini, aturan Johnson tidak

53

dapat digunakan. Pengembangan dari aturan Johnson ini disebut heuristic CDS.

Heuristic ini mengkombinasi mesin-mesin atau stasiun-stasiun kerja menjadi dua

mesin atau stasiun kerja dan selalu ditetapkan aturan Johnson ini disebut heuristic

CDS. Heuristic ini mengkombinasikan mesin-mesin atau stasiun-stasiun kerja

menjadi dua mesin atau stasiun kerja dan selalu diterapkan aturan Johnson.

Langkah-langkah penjadwalan heuristic CDS [ 4, hlm 559] :

1. Menentukan langkah alternatif yang akan diambil sebanyak jumlah mesin-

1.

2. Dari setiap langkah alternatif tersebut, kemudian dihitung waktu

prosesnya untuk 1t dan 2t .

3. Dari semua pekerjaan yang akan dijadwalkan, tentukan waktu proses

terkecil dari masing-masing pekerjaan tersebut.

4. Seperti aturan Johnson’ s Rule, tempatkan urutan pekerjaan dari sebelah

kiri jika terdapat waktu proses terkecil untuk mesin 1 ( 1t ), dan jika waktu

proses terkecil ada pada mesin 2 ( 2t ), tempatkan urutan pekerjaan dari

sebelah kanan. Ulangi urutan yang disebutkan di atas jika terdapat

pekerjaan-pekerjaan baru yang akan dijadwalkan.

5. Buatlah rangkaian urutan pekerjaannya di setiap alternatif yang ada.

6. Hitung total waktu penyelesaian (makespan) di setiap alternatif yang ada.

7. Pilihlah urutan di salah satu alternatif yang ada yang mempunyai

makespan terkecil.

54

b. Nawaz, Enscore, dan Ham (NEH) heuristic [1, hlm 443]

Heuristic NEH pertama kali digunakan dalam waktu proses untuk masing-masing

job dan untuk mengurangi waktu dari produksinya. Langkah-langkah dari

heuristic NEH adalah :

1. Lakukan pengurutan job berdasarkan aturan SPT (Short Processing Time)

2. Kemudian memulai dengan mencoba 2 urutan pertama tersebut (j1, j2)

dan (j2, j1). Hitung makespan dari kedua urutan tersebut dan pilih

makespan terkecil (misalnya j2, j1)

3. Perhitungan dilanjutkan berdasarkan job selanjutnya, misalnya j3. hitung

makespan dari ketiga urutan tersebut yaitu (j3, j2,j1), (j2,j3,j1), (j2,j1,j3)

dan pilih urutan makespan terkecil.

4. Lakukan terus perhitungan tersebut hingga didapatkan urutan dengan

makespan terkecil.

Dalam jurnal “Some Efficient Heuristic Methods for The Flow Shop

Sequencing Problem”, dilakukan penelitian perbandingan beberapa metode

penjadwalan job untuk menentukan yang terbaik dengan berbagai macam masalah

yang ada. Masalah penjadwalan yang biasa dihadapi adalah seperti adanya job

dengan jumlah besar yang datang secara bersamaan, jumlah mesin yang digunakan

dan problem yang akan dihadapi seperti mesin rusak, penambahan order baru,

perubahan prioritas dan lain-lain. Tujuan dari penelitian ini adalah mencari metode

penjadwalan yang terbaik dalam meminimalkan waktu antara waktu mulai dari mesin

pertama sampai dengan waktu akhir yang diperlukan untuk menyelesaikan pekerjaan

55

terakhir. Waktu ini disebut dengan makespan. Ada beberapa batasan yang diberikan

pada penelitian ini, seperti:

• Semua job harus diproses dalam setiap mesin.

• Semua mesin hanya melakukan satu pekerjaan dalam satu waktu.

• Waktu set up mesin termasuk dalam waktu proses.

• Urutan setiap operasi sama untuk setiap mesin dan urutan telah

ditentukan.

Metode penjadwalan yang diperbandingkan adalah metode penjadwalan

Gupta, Johnson, Rapid Access Procedure (RA), Palmer, CDS dan NEH. Hasil

penelitian tersebut adalah sebagai berikut:

Tabel 2.1 Perbandingan Metode Penjadwalan

Dari perhitungan tersebut didapat bahwa metode penjadwalan NEH adalah

metode penjadwalan yang paling optimal dibandingkan metode penjadwalan yang

lain.