8

BAB 2

LANDASAN TEORI

2.1 Definisi Penjadwalan

Penjadwalan merupakan bagian yang strategis dari proses

perencanaan dan pengendalian produksi dan juga merupakan rencana

pengaturan urutan kerja serta pengalokasian sumber baik waktu maupun

fasilitas untuk setiap operasi yang harus diselesaikan. Menurut Thomas E.

Morton dan David W. Pentico (2001, p12), penjadwalan merupakan proses

pengorganisasian, pemilihan, dan penentuan waktu penggunaan sumber daya

yang ada untuk menghasilkan output seperti yang diharapkan dalam waktu

yang diharapkan pula. Sementara menurut Kennent R. Baker (2004, p132),

penjadwalan didefinisikan sebagai proses pengalokasian sumber-sumber atau

mesin-mesin yang ada untuk menjalankan sekumpulan tugas dalam jangka

waktu tertentu. Definisi lain menurut Conway (2001, p56) mengatakan

bahwa penjadwalan adalah proses pengurutan pembuatan produk secara

menyeluruh pada sejumlah mesin tertentu dan pengurutan didefinisikan

sebagai proses pembuatan produk pada satu mesin dalam jangka waktu

tertentu. Input dari suatu penjadwalan mencakup urutan ketergantungan antar

operasi (routing), waktu proses untuk masing-masing operasi, serta fasilitas

yang dibutuhkan oleh setiap operasi.

Menurut Bedworth (2002, p72), terdapat dua target yang ingin

dicapai melalui penjadwalan mesin, yaitu jumlah output yang dihasilkan

9

(throughput), serta batas waktu penyelesaian yang telah ditetapkan (due date).

Kedua target ini dinyatakan melalui kriteria penjadwalan (misalnya minimasi

makespan, minimasi mean flow time, minimasi mean lateness, minimasi

maksimum tardiness, minimasi mean tardiness, minimasi number of tardy

dan sebagainya.

2.2 Tujuan Penjadwalan

Tujuan penjadwalan secara umum adalah :

1. Meningkatkan produktivitas mesin, yaitu dengan mengurangi waktu

mesin menganggur.

2. Mengurangi persediaan barang setengah jadi dengan jalan

mengurangi jumlah rata-rata tugas yang menunggu dalam antrian

suatu mesin karena mesin tersebut sibuk.

3. Mengurangi keterlambatan (hukuman) karena batas waku telah

dilampaui, dengan cara :

a. Mengurangi maksimum keterlambatan.

b. Mengurangi jumlah pekerjaan yang terlambat.

2.3 Klasifikasi Penjadwalan

Menurut Conway (2001, p56), masalah penjadwalan dapat

diklasifikasikan berdasarkan faktor-faktor yaitu :

1. Jumlah mesin

Dibagi menjadi dua bagian yaitu :

10

• Penjadwalan pada mesin tunggal.

• Penjadwalan pada mesin ganda.

2. Pola kedatangan job

Dibagi menjadi dua bagian yaitu :

• Statik

Semua job datang secara bersamaan dan siap dikerjakan pada

mesin- mesin yang tidak bekerja.

• Dinamik

Job datang secara acak selama diadakan penjadwalan.

3. Sistem Informasi

Dibagi menjadi dua bagian yaitu :

• Informasi bersifat deterministik.

• Informasi bersifat stokastik.

Informasi ini meliputi informasi yang berhubungan dengan

karakteristik job, yaitu saat kedatangan, batas waktu penyelesaian,

perbedaan kepentingan di antara job-job yang dijadwalkan,

banyaknya operasi, serta waktu proses tiap operasi. Disamping itu

terdapat pula informasi yang menyangkut karakteristik mesin, seperti

jumlah mesin, kapasitas, fleksibilitas serta efisiensi penggunaan yang

berbeda untuk job yang berbeda.

11

4. Aliran proses

Dibagi menjadi tiga bagian yaitu :

• Pure Flow Shop

Pola aliran prosesnya identik.

Gambar 2.1 Pola Aliran Pure Flow Shop

• General Flow Shop

Pola aliran prosesnya tidak identik

Gambar 2.2 Pola Aliran General Flow Shop

M1 M2 M3 M4 M5

Input Input Input Input Input

output output output output output

M1 M2 M3 M4 output

Input (pekerjaan-pekerjaan baru)

12

• Job Shop

Pada pola aliran proses job shop, masing-masing job memiliki

urutan operasi yang unik. Setiap job bergerak dari satu

mesin/stasiun kerja menuju mesin/stasiun kerja lainnya

dengan pola yang random.

Gambar 2.3 Pola Aliran Job Shop

Proses job shop mempunyai karakteristik dari pengaturan

peralatan yang sama berdasarkan fungsi (seperti milling,

drilling, turning, forging, dan perakitan); sebagaimana aliran

job dari satu stasiun kerja ke stasiun kerja lain, atau dari satu

departemen-departemen lainnya.

Menurut Fogarty (2003, p97), karakteristik proses job shop

adalah sebagai berikut :

MESIN K

Pekerjaan-pekerjaan baru

Pekerjaan-pekerjaan lengkap

Pekerjaan-pekerjaan dalam proses

Pekerjaan-pekerjaan dalam proses

13

1. Peralatan penanganan material dan peralatan produksi

multi-guna dapat diatur dan dimodifikasi untuk

menangani berbagai produk yang berbeda.

2. Produk-produk yang berbeda diproses dalam lot-lot

atau batch.

3. Pemrosesan order-order membutuhkan pengendalian

dan perencanaan yang terperinci sehubungan dengan

variasi pola-pola aliran dan pemisahan stasiun-stasiun

kerja.

4. Pengendalian membutuhkan informasi tentang job dan

shop floor yang terperinci meliputi urutan proses,

prioritas order, waktu yang dibutuhkan oleh setiap job,

status dari job in process, kapasitas stasiun kerja, dan

kapasitas yang dibutuhkan dari stasiun kerja kritis

pada suatu perioda.

5. Beban-beban stasiun kerja berbeda secara menyolok;

masing-masing memiliki persentase utilitas yang

berbeda.

6. Ketersediaan sumber-sumber, meliputi material,

personal, dan peralatan, harus dikoordinasikan dengan

perencanaan order.

14

7. Sejumlah material work in process cenderung

meningkat. Hal ini dalam aliran proses menyebabkan

antrian-antrian dan work in process yang panjang.

8. Menggunakan teknik-teknik penjadwalan tradisional,

total waktu dari awal operasi pertama sampai selesai

operasi terakhir, relatif panjang dibandingkan dengan

total waktu operasi.

9. Para pekerja langsung biasanya memiliki skill yang

lebih tinggi dan lebih terlatih daripada pekerja untuk

operasi flow process.

2.4 Istilah dalam Penjadwalan

Dalam pembahasan mengenai masalah penjadwalan akan dijumpai

beberapa istilah yang cukup penting, diantaranya adalah sebagai berikut :

• Completion Time ( Ci )

Menunjukkan rentang waktu sejak pekerjaan pertama mulai dikerjakan

sampai proses tersebut selesai.

Cj = Fj + rj

• Flow Time ( Fj )

Waktu antara job ke-j siap dikerjakan sampai job tersebut diselesaikan.

Fi = Ci - ri

15

• Process Time ( tij )

Merupakan waktu yang diperlukan untuk menyelesaikan suatu operasi atau

proses ke-i dari job ke-j. Waktu proses ini telah mencakup waktu untuk

persiapan dan pengaturan proses.

• Due Date ( dj )

Adalah batas waktu penyelesaian yang ditentukan untuk job j.

• Lateness ( Lj )

Adalah besarnya simpangan waktu penyelesaian job j terhadap due date yang

telah ditentukan untuk job tersebut.

Lj = Cj - dj ≤ 0, artinya saat penyelesaian memenuhi batas akhir.

Lj = Cj - dj ≥ 0, artinya saat penyelesaian melewati batas akhir.

• Tardiness ( Tj )

Adalah besarnya keterlambatan dari job j. Tardiness adalah lateness yang

berharga positif.

Tj ≥ 0 jika Lj ≥ 0

Tj = 0 jika Lj < 0

• Earliness ( ej )

Adalah keterlambatan yang bernilai negatif.

ej ≥ 0 jika Lj < 0

ej = 0 jika Lj ≥ 0

16

2.5 Variabel-variabel dalam Penjadwalan

Dibagi menjadi dua yaitu :

1. Variabel Pembatas :

• Ready Time ( rj )

Menyatakan saat job j siap dijadwalkan

• Process Time ( tj )

Yaitu lamanya waktu proses yang dibutuhkan oleh job j.

• Due Date ( dj )

Adalah batas waktu penyelesaian yang ditentukan untuk job j.

2. Variabel hasil penjadwalan :

• Waiting Time ( wij )

Adalah waktu tunggu seluruh operasi dari suatu job.

• Completion Time ( cj )

• Lateness ( Lj )

• Flow Time ( Fj )

• Tardiness ( Tj )

• Earliness ( ej )

2.6 Kriteria Evaluasi Jadwal

Keberhasilan suatu penjadwalan dapat diukur dengan besaran-

besaran yang melibatkan informasi dari job-job yang merupakan fungsi dari

sekumpulan waktu penyelesaian. Jika terdapat n job yang akan dijadwalkan,

maka tingkat keberhasilan dapt dinilai dari besaran-besaran berikut :

17

• Completion Time

Yaitu waktu yang dibutuhkan untuk menyelesaikan seluruh job yang

dijadwalkan,

Cmax = max {Cj}

• Mean Flow Time

Yaitu rata-rata waktu yang dihabiskan oleh setiap job di lantai pabrik.

Flow Time adalah selisih Completion Time dengan Ready Time.

∑=

=n

jjF

nF

1

1

• Mean Weight Flow Time

Definisi Mean Weight Flow Time mirip dengan Mean Flow Time,

tetapi mempertimbangkan prioritas pengerjaan setiap job dalam

perhitungannya.

∑

∑

=

== n

jj

n

jjj

w

w

FwF

1

1

• Maximum Lateness

Yaitu besarnya simpangan maksimum, atau selisih waktu

penyelesaian seluruh job yang dijadwalkan terhadap batas waktu

penyelesaian job-job tersebut (due date). Lateness bernilai negatif jika

waktu penyelesaian job lebih awal dari due date, dan bernilai positif

jika job diselesaikan detelah due date yang ditentukan untuk job tersebut.

Lmax = max {Lj}

18

• Mean Tardiness

Yaitu rata-rata keterlambatan seluruh job yang dijadwalkan.

Tardiness adalah lateness yang bernilai positif. Jika lateness bernilai

negatif maka besarnya tardiness adalah nol.

∑=

=n

jjT

nT

1

1

• Mean Weight Tardiness

Yaitu rata-rata keterlambata seluruh job yang dijadwalkan dengan

memasukkan faktor prioritas pengerjaan masing-masing job ke dalam

perhitungan fungsi obyektifnya.

∑

∑

=

== n

jj

n

jjj

w

w

TwT

1

1

• Number of Tardy Job

Menunjukkan kuantitas job yang mengalami keterlambatan.

∑=

=n

jjt NN

1

Dimana

Nt = 1 jika Cj ≥ dj

Nt = 0 jika Cj ≤ dj

19

• Utilitas Mesin

Utilitas mesin adalah bagian dari kapasitas mesin yang dibebani

untuk menjalankan proses-proses yang dibutuhkan terhadapt waktu yang

tersedia.

max

1

C

tU

n

jj∑

==

Cmax = maksimum completion time

Beberapa kriteria optimalitas dalam proses penjadwalan adalah :

1. Berkaitan dengan waktu

Kriteria optimalitas yang telah dikemukakan diatas

merupakan kriteria optimalitas yang berkaitan denga waktu. Apabila

penjadwalan yang dilakukan memperhatikan kriteria yang berkaitan

dengan hal tersebut maka efisiensi waktu akan dapat tercapai. Kriteria

optimalitas lain yang berkaitan dengan waktu adalah pemenuhan due

date.

Due-date merupakan batas waktu yang ditetapkan oleh

konsumen agar seluruh produk yang dipesannya sudah siap (selesai).

Pihak produsen selalu berusaha untuk memenuhi due-date tersebut,

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

diproduksi lagi oleh perusahaan lain dan produsen bertindak sebagai

supplier bagi perusahaan lain, maka keterlambatan yang terjadi

menyebabkan terjadinya waktu menungu bagi perusahaan lain

20

tersebut dan hal ini akan berdampak negatif yaitu hilagnnya

kepercayaan perusahaan tersebut kepada produsen.

2. Berkatian dengan biaya

Kriteria yang berkatian dengan biaya ini lebih ditujukan pada

biaya produksi. Terdapat hubungan antara kriteria yang berkaitan

dengan waktu dan kriteria yang berhubungan dengan waktu, misalnya

biaya produksi akan bertambah jika terjadi keterlambatan karena

harus membayar denda. Dengan demikian suatu penjadwalan

produksi tertentu diharapkan mendapatkan ongkos yang minimal.

3. Kriteria gabungan

Beberapa kriteria optimalitas tersebut dapat digabungkan dan

dikombinasikan sehingga menjadi beberapa kriteria yang

sesungguhnya adalah multikriteria.

2.7 Penjadwalan Job Shop Secara Umum

2.7.1 Asumsi-asumsi Dalam Pemasalahan Penjadwalan Job Shop

Berkenaan dengan pokok permasalahan pada tugas akhir ini

maka diberlakukan beberapa asumsi yang menyangkut karakteristik

job, mesin yang digunakan dan waktu pemrosesan.

a. Asumsi Mengenai Job

1. Setiap job mempunyai jumlah operasi tertentu, dimana

setiap operasi dapat dikerjakan hanya pada satu mesin.

21

2. Pada saat yang sama, setiap job tidak boleh diproses pada

lebih dari satu mesin.

3. Setiap job yang telah mulai dikerjakan harus diselesaikan,

dan tidak boleh ada penundaan.

4. Setiap job harus diselesaikan menurut tugas yang telah

disusun dalam suatu routing, dan tidak berdasarkan

routing yang lain.

5. Setiap tugas merupakan suatu kesatuan, walaupun

mungkin terdiri dari beberapa unit.

6. Setiap job mungkin harus menunggu diantara dua mesin

sampai waktu menunggu tersebut selesai.

7. Setiap job mempunyai waktu penyerahan yang pasti dan

ditentukan bersama dengan konsumen.

8. Setiap tugas boleh diproses lebih dari satu kali di mesin

yang sama.

9. Setiap tugas dapat diproses pada beberapa jenis mesin

yang mampu melaksanakan tugas tersebut.

b. Asumsi Mengenai Mesin

1. Setiap mesin dioperasikan secara independe. Oleh karena

itu setiap mesin dapat beroperasi pada kecepatan output

maksimum

22

2. Tingkat keandalan masing-masing mesin tidak berubah

atau tingkat kerusakan mesin tetap selama pengerjaan

suatu order tertentu.

3. Setiap mesin hanya memproses satu job pada saat tertentu.

4. Setiap mesin secara kontinyu siat untuk dibebani tugas

selama proses penjadwalan apabila tidak mengalami

interupsi akibat kerusakan atau perawatan.

5. Setiap mesin beroperasi sesuai dengan informasi waktu

dan distribusi yang diketahui secara tepat.

c. Asumsi Mengenai Waktu Proses

1. Waktu proses telah diketahui dan tertentu baik rata-rata

maupun distribusinya

2. Waktu proses independent terhadap jadwal. Artinya

urutan set up time bersifat independent dan move time

antar mesin dapat diabaikan.

3. Setiap waktu proses secara implicit sudah mencakup

waktu pemindahan benda kerja, set up, dan penghentian

mesin.

2.7.2 Matriks Waktu Proses Dalam Persoalan Job Shop

Dalam menggambarkan persoalan job shop diperlukan

besaran waktu yang digunakan untuk memproses masing-masing

operasi tiap-tiap job. Besaran waktu ini tersusun dalam sebuah

23

matriks yang disebut matriks waktu poses. Sebagai ilustrasi, matriks

waktu proses diperlihatkan pada gambar 2.4 berikut.

⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢

⎣

⎡

nmnn

m

m

ttt

tttttt

21

22221

11211

:::......

Gambar 2.4 Matriks waktu proses

Elemen tij dari matriks waktu proses menyatakan besarnya

waktu yang diperlukan untuk memproses operasi ke-i pada job ke-j.

Selanjutnya, dalam pembahasan masalah penjadwalan dalam tugas

akhir ini, matriks waktu proses disajikan dalam bentuk tabel.

2.7.3 Matriks Routing Mesin

Suatu karakteristik utama dari disiplin penugasan adalah tipe

mesin yang diperlukan untuk mengerjakan suatu job yang disebut

‘routing’. Dalam permasalahan job shop, routing suatu job tidak

harus sama dengan routing job yang lainnya dari sejumlah n-job yang

akan dijadwalkan. Hal inilah yang membedakan permasalahan job

shop dengan flow shop yang memiliki routing sama untuk setiap job

dari sejumlah n-job yang akan diproses. Routing dari sejumlah job

yang akan dijadwalkan ditabulasikan ke dalam bentuk matriks yang

disebut matriks routing. Contoh matriks routing dapat dilihat pada

gambar 2.5 berikut.

24

⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢

⎣

⎡

nmnn

m

m

rrr

rrrrrr

...:::

...

...

21

22221

11211

Gambar 2.5 Matriks Routing Mesin

Elemen rij dari matriks routing menyatakan tipe mesin yang

diperlukan untuk melakukan operasi ke-i job ke-j. Dalam

pembahasan persoalan penjadwalan job shop pada tugas akhir ini,

routing mesin disajikan dalam bentuk tabel.

2.7.4 Ruang Jawab Penjadwalan Job Shop

Dalam persoalan job shop, jadwal yang layak akan diperoleh

jika hasil penjadwalan yang bersangkutan memenuhi kriteria berikut :

1. Seluruh operasi dari semua job telah dialokasikan/ditugaskan.

2. Tidak terdapat operasi yang tumpang tindih (overlap) diantara

masing-masing operasi dari semua job dan ketentuan presedensi

telah terpenuhi.

Berdasarkan ketentuan tersebut, jumlah kombinasi

penjadwalan yang layak yang mungkin dibuat adalah tak terbatas. Hal

ini disebabkan waktu menganggur dapat disisipkan di antara operasi

sebanyak mungkin tanpa melanggar ketentuan presedensi. Oleh

karena itu perlu dipertimbangkan suatu jadwal yang mendekati

25

ukuran performansi (performance) yang sesuai dengan kriteria

optimalitas yang telah dipilih. Jadwal-jadwal yang layak (feasible)

tersebut dapat diklasifikasikan sebagai berikut :

1. Set Jadwal Semi Aktif (SA) :

Merupakan set jadwal dimana tidak satupun operasi dapat

dikerjakan lebih awal tanpa mengubah susunan beberapa

operasi pada mesin.

2. Set Jadwal Aktif (A) :

Merupakan set jadwal dimana tidak satu operasi pun dapat

dipindahkan lebih awal tanpa menunda operasi lain.

3. Set Jadwal Non Delay (ND) :

Merupakan set jadwal dimana tidak satu pun mesin dibiarkan

menganggur jika pada saat yang sama terdapat operasi yang

membutuhkan mesin tersebut.

4. Set Jadwal Optimal (O) :

Merupakan set jadawal dimana tidak terdapat jadwal lain yang

memiliki tingkat preferensi yang lebih baik dari set jadwal

optimal.

Dalam suatu jadwal dapat dilakukan local left shift atau

limited left shift yakni pergeseran operasi ke kiri (lebih awal) tanpa

merubah susunan operasi-operasi pada mesin, serta global left shift

yakni pergeseran lebih awal dengan merubah susunan operasi tanpa

26

menunda operasi lain, sehingga dapat diperoleh beberapa teorema

yang menyatakan hubungan antar keempat jenis set jadwal tersebut.

Berdasarkan klasifikasi jadwal diatas, dikenal adanya 3

teorema yang berhubungan dengan kedudukan set jadwal satu

terhadap yang lainnya, yaitu :

1. Jadwal semi aktif mendominasi jadwal yang layak. Hal ini

terjadi karena pada jadwal yang layak masih bisa dilakukan

sejumlah local left shift.

2. Set jadwal aktif mendominasi set jadwal semi aktif. Hal ini

disebabkan karena pada jadwal semi aktif masih mungkin

dilakukan global left shift atau masih terdapat kemungkinan

menggeserkan sejumlah operasi untuk dikerjakan lebih awal.

3. Set jadwal non delay merupakan sub set dari jadwal aktif.

Berdasarkan definisi jadwal non delay, maka tidak mungkin

dilakukan local left shift maupun global left shift pada set

jadwal non delay.

Dari ketiga teorema diatas dapat ditarik kesimpulan bahwa

jadwal optimal terdapat dalam set jadwal aktif, atau jadwal optimal

merupakan jadwal dengan tingkat preferensi yang paling tinggi dari

set jadwal aktif. Hubungan antara keempat jenis jadwal yang telah

disebutkan diatas dapat dilihat dalam bentuk diagram Venn pada

gambar 2.6 berikut ini.

27

Gambar 2.6 diagram Venn Ruang Jadwal yang Layak

Meskipun jadwal non delay merupakan sub set dari jadwal

aktif, jadwal optimal belum tentu terdapat pada ruang jadwal non

delay.

2.8 Teknik Priority Dispatching

Penjadwalan dengan pendekatan heuristik menggunakan

aturan pengurutan atau priority dispatching dalam menentukan job

yang akan diproses selanjutnya. Terdapat beberapa aturan pengurutan

job yaitu :

1. R (Random)

Memilih job dalam antrian dengan kemungkinan yang sama

bagi setiap job.

2. FCFS (First Come First Serve)

Job dikerjakan sesuai dengan saat kedatangan. Job yang datang

lebih dahulu dikerjakan lebih awal.

F

Nd Op A

SA

28

3. SPT (Shortest Processing Time)

Urutan pengerjaan job berdasarkan waktu proses yang

terpendek. Aturan ini cenderung mengurangi work-in-process,

mean flow time serta mean lateness.

4. EDD (Earliest Due Date)

Job dikerjakan berdasarkan due date yang lebih mendesak.

5. CR (Critical Ratio)

Priority index dihitung berdasarkan ( due date saat ini ) / ( sisa

lead time ).

6. LWR (Least Work Remaining)

Aturan ini mempertimbangkan sisa waktu proses sampai job

tersebut diselesaikan. Job dengan sisa waktu terkecil dipilih

untuk diproses.

7. MWKR (Most Work Remaining)

Aturan ini mempertimbangkan sisa waktu proses sampai job

tersebut diselesaikan. Job dengan sisa waktu terkecil dipilih

untuk diproses.

8. TWK (Total Work)

Memilih operasi dengan job yang memiliki jumlah operasi

terbanyak.

9. LWK (Least Total Work)

Memilih operasi dengan job yang memiliki jumlah operasi

terkecil.

29

10. FOR (Fewest Operation Remaining)

Aturan ini mempertimbangkan successive operation yaitu

semua operasi yang tergantung dari operasi yang bersangkutan.

11. ST (Slack Time)

Merupakan variasi dari aturan EDD dengan cara mengurangkan

waktu proses dari due date. Job yang memiliki nilai ST kecil

dijadwalkan terlebih dahulu.

12. ST / O (Slack Time per Operation) atau S / ROP (Slack /

Remaining Operations)

Merupakan variasi dari ST yang membagi ST dengan jumlah

operasi yang harus dijadwalkan.

13. WINQ (Work In Next Queue)

Aturan ini berdasarkan utilitas mesin. Ide dasarnya dengan

mempertimbangkan panjangnya antrian pada setiap stasiun

yang akan dilalui oleh masing-masing job. Penjadwalan setiap

job dilakukan pada stasiun yang memiliki antrian yang

terpendek.

14. LSU (Least Setup)

Memilih job yang memiliki waktu setup terkecil, dengan

demikian meminimasi changeover time.

15. INDEX (By Least Index)

Memilih job dengan index prioritas terkecil.

30

2.9 Algortima Lintasan Terpanjang

Masalah (P ( k , oM )) adalah penjadwalan satu-mesin untuk

mesin k yang belum dijadwalkan dengan oM adalah himpunan

mesin-mesin yang telah dijadwalkan. Masalah ini ekivalen dengan

mencari sebuah jadwal untuk mesin k yang menimimasi maksimum

lateness, dengan :

Setiap operasi i yang dikerjakan pada mesin k memiliki :

• Waktu proses id ,

• Release time ir dan

• Due date if

Pada jaringan uang terbentuk, ir = L ( 0 , i ), dan if = L ( 0, n ) – L

( i , n ) + id dengan L ( i , j ) adalah lintasan terpanjang dari simpul i

ke j dalam TD , dan T : = ∪ ( pS : p ∈ oM ). Jadi L ( i , j )

adalah lintasan terpanjang dari simpul i ke j dalam suatu jaringan

yang terbentuk dari busur-busur operasi dalam satu job untuk semua

job dan busur-busur pembentuk operasi pada semua mesin yang telah

dijadwalkan.

Masalah ini dapat dipandang sebagai suatu masalah minimasi

makespan dimana setiap job harus diproses pada tiga mesin dengan

mesin pertama dan ketiga memiliki kapasitas tak terhingga dan mesin

kedua ( mesin k pada model diatas) memproses satu job setiap waktu,

31

dan waktu proses dari job i adalah ir pada mesin pertama, id pada

mesin kedua, dan ii fnLq −= ),0(: pada mesin ketiga. Nilai dari ir

dan iq sering disebut sebagai “head” dan “tail” dari job i.

Jadi masalah penjadwalan satu mesin [ Carlier, 1982 ] yang

diselesaikan dalam algoritma adalah bentuk :

Min nt

nt - it ≥ ii qd + ,

it ≥ ir , i ∈ N * ,

jt - it ≥ id ∨ it - jt ≥ id (i,j) ∈ kE ,

)),(*( MokP

dimana ir dan iq didefinisikan seperti diatas, dan N * adalah

himpunan operasi-operasi yang akan diproses pada mesin k.

Untuk keperluan penyelesaian problem penjadwalan satu-

mesin )),(*( MokP , kita harus menyelesaikan dua masalah lintasan

terpanjang dalam TD untuk menghitung nilai ir dan iq .

Perhitungan lintasan terpanjang membutuhkan waktu yang

relatif besar dari keseluruhan pendekatan ini, walaupun begitu ide

sentral dari pendekatan ini tidak terletak pada pencarian lintasan

terpanjang. Penyelesaian problem lintasan terpanjang dengan cepat

adalah penting untuk efisiensi prosedur secara keseluruhan.

32

2.9.1 Komputasi Algoritma Lintasan Terpanjang

Untuk keperluan perhitungan lintasan terpanjang ini

penulis mengembangkan suatu algoritma yang ide dasarnya

didapat dari The Shortest Path Problem [ Lieberman, 1990 ].

Modifikasi dilakukan dengan memanfaatkan keuntungan

panah berarah yang membentuk jaringan. Digunakan double

link list untuk membentuk pohon biner yang memiliki cabang

yang merupakan simpul sebelumnya ( prodeccessor ) dan

simpul sesudahnya ( successor ) dari suatu simpul.

Algoritma ini membuat pohon binuer yang terdiri dari

simpul-simpul yang berpengaruh terhadap panjang lintasan

simpul yang dicari. Pohon ini terus dibuat sampai cabang

mencapai simpul akhir atau simpul yang lintasan

terpanjangnya telah diketemukan. Begitu simpul tersebut

menemukan kondisi tersebut dilakukan penelusuran rekursif

dari suatu simpul ujung ke simpul sebelumnya. Nilai lintasan

terpanjang dari suatu simpul adalah maksimum dari nilai

lintasan terpanjang antara kedua cabang successor yang

dimiliki ditambah dengan waktu proses ( besar busur ) simpul

successor.

Keuntungan dari algoritma yang dikembangkan ini adalah

penghematan waktu ketika lintasan terpanjang simpul yang

33

lain akan dicari. Untuk mencari nilai lintasan terpanjang

simpul yang akan dicari ini dibutuhkan lintasan terpanjang

dari simpul successor-nya. Karena sebagian besar dari simpul

sesudahnya telah diketahui nilainya, maka pencarian lintasan

terpanjang simpul tersebut menjadi lebih cepat.

2.10 Algoritma Schrage

Pada Algoritma Schrage operasi yang siap dengan iq terbesar

dijadwalkan terlebih dahulu. Detailnya adalah sebagai berikut :

Pada algoritma ini, U adalah himpunan operasi-operasi yang telah

untuk dijadwalkan dan U adalah himpunan dari operasi-operasi

lainnya, I adalah operasi-operasi yang akan dijadwalkan, dan t adalah

waktu.

1. Set t = Min ir , untuk Ii∈ ; =U φ .

2. Pada waktu t, jadwalkan di antara operasi-operasi i yang siap

( tri ≤ ) dari U , pilih operasi j adalah operasi dengan iq

terbesar.

3. }{ jUU ∪= ; tt j = ; t = Max { ij dt + , Min ir dengan

Ui∈ } ; jika U sama dengan I, algoritma selesai; jika tidak

lakukan langkah 2.

34

Theorema :

L adalah makespan dari jadwal algoritma Schrage.

a. Jika jadwal ini tidak optimal, maka terdapat sebuh operasi

kritis c dan sebuah himpunan J yang kritis sehingga :

h( J ) = Min ir + ∑ id + Min iq > cdL − untuk Ji∈ .

Konsekuensinya, jarak antara optimal dengan jadwal Schrage

adalah kurang dari cd ; dan pada jadwal yang optimal, c akan

diproses sebelum atau sesudah himpunan operasi-operasi J.

b. Jika jadwal ini optimal, maka terdapat J sehingga h(J) = L.

Keterangan :

Pada jadwal yang tidak optimal, pada operasi-operasi yang dilalui

oleh lintasan terpanjang (critical path) dari simpul nol (simpul mulai)

ke simpul akhir yang disebut sebagai operasi-operasi kritis, dengan p

adalah operasi terakhir yang dilalui lintasan kritis, jika terdapat i < p

sehingga iq < pq , maka c adalah operasi kritis yang terdekat dengan

operasi kritis p sehingga cq < pq ; dan himpunan J = { c + 1,…,

p }; jadi cq < gq untuk setiap Jg ∈ .

Pada jadwal yang optimal, operasi c ini yang akan diproses sebelum

atau sesudah himpunan operasi-operasi J.

35

2.11 Metoda Branch and Bound

Metoda ini didasarkan pada algoritma Schrage, critical set J

dan operasi kritis c.

Deskripsi dari pohon :

Pohon adalah setiap konfigurasi jadwal dari one-machine problem,

dengan lower bound f(S) dan upper bound of adalah solusi terbaik

yang telah diketahui.

Branching ( Pencabangan ) :

Cabang dari pohon yang diperhatikan adalah cabang yang memiliki

lower bound yang terkecil dan kemudian menerapkan algoritma

Schrage.

Jika c tidak ada, maka jadwal tersebut optimal (sesuai dengan

teorema); jika terdapat c maka operasi c akan diproses sebelum atau

sesudah J.

Dua masalah yang muncul adalah : masalah pertama, operasi c

diproses sebelum semua operasi J dengan membuat

},max{ ∑ += pgcc qdqq dengan Jg ∈ .

Pada masalah yang kedua, operasi c diproses setelah semua operasi J

dengan membuat

,max{ cc rr = min }∑+ gg dr dengan Jg ∈ .

36

Lower Bound dari simpul yang baru adalah :

})}{(),(),(max{)( cJhJhSfSf ∪=

cabang baru akan ditambahkan pada pohon jika lower bound-nya

lebih kecil dari upper bound of .

Upper Bound (Batas atas)

Setiap kali algoritma Schrage diterapkan, dilakukan perbandingan

makespan dengan of . Jika makespan lebih kecil dari of maka of =

makespan dari konfigurasi jadwal tersebut.

Gambar 2.7 Branching

S

c sebelum J c sesudah J

S1 S2

37

2.12 Pengertian Technological Constraint dan Precedence Constraint

Simon French memberikan definisi untuk kedua istilah itu

sebagai berikut :

• Technological Constraint memberikan urutan proses pada

setiap job, atau dengan kata lain memberikan routing untuk

setiap job.

• Precedence Constraint membatasi urutan pengoperasian

proses- proses antar job yang berbeda.