SISTEM PRODUKSI

SISTEM PRODUKSI

Pengertian:
Sistem adalah seperangkat unsur yang secara teratur saling berkaitan sehingga membentuk suatu totalitas.
Produksi adalah segala kegiatan untuk menimbulkan atau meningkatkan faedah/ nilai suatu barang atau jasa.

Sistem produksi adalah suatu keterkaitan unsur-unsur yang berbeda secara terpadu, menyatu dan menyeluruh dalam pentranformasian masukan menjadi keluaran.
Sistem Produksi yang sering dipergunakan dapat dibedakan atas dua macam, yaitu :
1. Sistem seri, di mana dua atau lebih sistem merupakan suatu sistem yang lebih besar.
2. Sistem pararel, di mana perusahaan memprodusir barang – barang yang serupa di beberapa pabrik dengan lokasi yang berbeda tetapi dalam saat pengerjaan yang sama, sehingga dapat berproduksi dengan jumlah yang lebih besar.

Dalam pelaksanaan sistem produksi terutama dalam kegiatan menghasilkan produk yang berupa barang, terdapat tiga macam proses, yaitu :
1. Proses produksi yang kontinyu (Continuous process), di mana peralatan produksi yang digunakan disusun dan diatur dengan memperhatikan urut-urutan kegiatan atau routing dalam menghasilkan produk tersebut, serta arus bahan dalam proses telah distandardisir.
2. Proses prooduksi yang terputus – putus ( Intermittent Process), di mana kegiatan produksi dilakukan tidak standard, tetapi didasarkan pada produk yang dikerjakan, sehingga peralatan produksi yang dipergunakan disusun dan diatur dapat bersifat lebih luwes (flexible) untuk dapat dipergunakan bagi menghasilkan berbagai produk dan berbagai ukuran.
3. Proses produksi yang bersifat proyek, di mana kegiatan produksi dilakukan pada tempat dan waktu yang berbeda – beda, sehingga peralatan produksi yang digunakan ditempatkan di lokasi di mana proyek tersebut dilaksanakan dan pada saat yang direncanakan.


PENJADWALAN SATU PROSESSOR

A. PENDAHULUAN
Keluaran perencanaan aggregat ialah suatu jadwal induk. Jadwal tersebut diturunkan menjadi beberapa periode perencanaan, seperti hari atau minggu. Selanjutnya pekerjaan yang harus diselesaikan pada periode tersebut diatur. Diassumsikan bahwa seluruh sumber daya yang dibutuhkan menjalankan aktivitas-aktivitas tersebut telah disediakan pada awal periode. Keputusan yang harus dibuat ialah urutan pekerjaan apa yang harus dikerjakan terlebih dahulu. Pengurutan pekerjaan ialah pokok bahasan bab ini. Pendekatan ini sering kali tidak dapat menghasilkan jawaban optimal. Sering kali harus digunakan pendekatan heuristik karena rumitnya masalah yang harus dihadapi..
Pada saat pimpinan bagian produksi mulai menjadwalkan kegiatan di departemennya, ia harus memperhatikan ketersediaan sumber daya dan peralatan. Selanjutnya, himpunan pekerjaan yang harus diselesaikan harus dikaji ulang. Untuk tiap pekerjaan, pimpinan bagian produksi tersebut harus mengetahui sumber daya yang dibutuhkan dan waktu proses yang dibutuhkan untuk menyelesaikan pekerjaan tersebut. Kendala-kendala seperti halnya saat awal pekerjaan dapat dimulai, maupun kapan pekerjaan tersebut harus diselesaikan juga harus diperhatikan. Pada akhirnya, si pimpinan tersebut harus mengurutkan pekerjaan mana yang harus diselesaikan terlebih dahulu.. Dengan berjalannya waktu, maka ketersediaan sumber daya dapat saja berubah. Dalam hal ini, penjadwalan ulang menjadi penting. Sehingga karenanya, masalah penjadwalan merupakan suatu proses dinamis..

B. TUJUAN PENJADWALAN
Seorang supervisor dapat mengatur pekerjaan dengan berbagai cara. Cara yang paling sederhana ialah dengan mengurutkannya secara acak. Cara lainnya yang lebih sering digunakan ialah dengan menjadwalkan pekerjaan tersebut secara heuristik menggunakan aturan yang telah ditetapkan sebelumnya.
Terdapat berbagai macam tujuan penjadwalan.. Yang paling sering dihadapi ialah meningkatkan utilisasi peralatan atau sumber daya. Yaitu dengan cara menekan waktu menganggur sumber daya tersebut.. Untuk sejumlah pekerjaan, telah diketahui bahwa maksimasi utilisasi sumber daya berbanding terbalik dengan waktu yang diperlukan untuk menyelesaikan seluruh pekerjaan. Waktu tersebut dikenal sebagai makespan atau waktu alir maksimum dari jadwal pekerjaan tersebut.
Tujuan penjadwalan lainnya yang penting untuk diketahui ialah minimasi jumlah barang setengah jadi. Hal ini dilakukan dengan cara meminimasi jumlah pekerjaan yang menunggu dalam antrian sementara sumber daya disibukkan dengan pekerjaan lainnya. Tujuan ini dicapai dengan cara menekan waktu alir rata-rata.
Tujuan penjadwalan lainnya ialah menekan kelambatan. Dalam banyak hal, sejumlah pekerjaan memiliki batas waktu penyelesaian pekerjaan (Due Date) dan apabila pekerjaan selesai setelah Due Date akan dikenakan penalty. Terdapat beberapa tujuan berkenaan dengan kelambatan ini. Tujuan penjadwalan dapat berupa minimasi kelambatan maksimum atau dapat berupa mengurangi jumlah pekerjaan yang terlambat. Tidak ada prosedur umum penjadwalan yang bertujuan menekan kelambatan rata-rata, tetapi ada beberapa metode heuristik yang dapat memberikan hasil cukup baik untuk memecahkan masalah ini.

C. DEFINISI PERISTILAHAN YANG DIGUNAKAN
Sebagian besar istilah penjadwalan dapat dijelaskan dengan mudah. Hanya beberapa istilah yang harus didefinisikan terlebih dahulu.

Tabel 1. Definisi Peristilahan dan Notasi Yang Digunakan Dalam Bab Ini
ISTILAH PENJELASAN
Waktu Pemrosesan
(Processing Time) Perkiraan lama menyelesaikan suatu pekerjaan.
Estimasi ini mencakup waktu set up yang mungkin diperlukan. Dalam bab ini waktu pemrosesan dinotasikan sebagai t i .
Batas Waktu
(Due Date) Batas waktu yang ditetapkan untuk suatu pekerjaan. Jika pekerjaan diselesaikan dengan waktu lebih lama dari due date, maka pekerjaan dianggap terlambat. Diassumsikan bahwa beberapa jenis penalty akan terjadi jika pekerjaan terlambat. Due date dinotasikan sebagai d i .
Kelambatan
(Lateness)
Selisih antara waktu penyelesaian pekerjaan dengan batas waktunya (due date). Suatu pekerjaan dapat memiliki kelambatan positif, dalam hal pekerjaan selesai setelah batas waktunya; atau kelambatan negatif, dimana pekerjaan selesai sebelum batas waktu yang ditetapkan. Lateness dinotasikan sebagai L i .
Ukuran Kelambatan
(Tardiness) Ukuran kelambatan positif. Jika pekerjaan selesai lebih awal dari batas waktu, pekerjaan ini akan memiliki Lateness negatif tetapi Tardiness positif. Tardiness dinotasikan sebagai T i dimana T i ialah maksimum (0,Li).
Kelonggaran
(Slack) Ukuran selisih antara waktu yang tersisa antara saat selesainya pekerjaan dengan batas waktu yang ditetapkan. Slack dinotasikan sebagai SL i =d i – t i .
Waktu Penyelesaian
(Completion Time) Rentang antara awal pekerjaan pada pekerjaan pertama, dimana pekerjaan dinotasikan sebagai t = 0 dan saat dimana pekerjaan ke-i diselesaikan. Rentang ini dinotasikan sebagai C i.
Waktu Alir
(Flow time) Rentang waktu antara saat suatu pekerjaan dapat dimulai dan saat pekerjaan selesai dikerjakan. Sehingga flow time sama dengan waktu pemrosesan ditambah dengan waktu menunggu sebelum diproses. Waktu alir dinotasikan sebagai F i .

Sumber :
David D. Bedworth dan James E. Bailey, Integrated Production Control System : Management, Analysis, Design, John Wiley and Sons, New York, 1982, Hal.299-300.

D. NOTASI MATEMATIS PENJADWALAN SATU PROSESOR
Masalah penjadwalan yang paling sederhana muncul apabila ada sekumpulan pekerjaan menunggu untuk dikerjakan dan hanya tersedia satu prosesor untuk mengolahnya. Waktu pemrosesan dan batas waktu penyelesaian pekerjaan itu diassumsikan diketahui dan tak tergantung pada urutan pekerjaan yang akan dikerjakan. Masalah penjadwalan dalam kasus semacam ini ialah memutuskan pekerjaan mana yang akan dikerjakan terlebih dahulu, pekerjaan apa yang harus dikerjakan pada urutan kedua, ketiga dan selanjutnya.
Pemilihan urutan pekerjaan yang akan dikerjakan itu akan berpengaruh pada saat/ waktu selesainya pekerjaan yang bersangkutan.

Konsep pertama yang harus dijelaskan ialah makespan.. Dalam penjadwalan satu processor, makespan yang diperlukan untuk menyelesaikan seluruh pekerjaan akan tetap besarnya untuk berbagai macam urutan penjadwalan yang akan dihasilkan. Makespan ialah jumlah waktu pemrosesan yang dibutuhkan untuk menyelesaikan seluruh pekerjaan.

n
M s =  t i ( 1 )
i = 1

Dimana :
M s = Makespan untuk seluruh n pekerjaan dalam jadwal
t i = Waktu pemrosesan pekerjaan ke-i .

Jika diassumsikan semua pekerjaan siap dikerjakan pada saat jadwal dimulai (yaitu pada t = 0), maka waktu alir atau flow time untuk tiap pekerjaan sama dengan waktu penyelesaiannya (Completion Time).

F i,s = C i,s ( 2 )

Di mana:
F i,s = Waktu alir (flow time) pekerjaan i dalam jadwal S
C i,s = Waktu penyelesaian (Completion Time) pekerjaan i dalam jadwal S ialah :

Dan waktu alir rata-rata (Mean Flow Time) dari jadwal S ialah :
n
F s = 1  F i,s ( 3 )
n i = 1

Jika diassumsikan bahwa seluruh batas waktu (due date) diukur dari t = 0, maka kelambatan (lateness) dan ukuran kelambatan (tardiness) tiap pekerjaan dinyatakan dalam persamaan berikut :

L i,s = C i,s – d i ( 4 )
Ti,s = max (0,C i,s-d i )  i  n ( 5 )

Sehingga karenanya, kelambatan rata-rata (mean lateness) dan ukuran kelambatan rata-rata (mean tardiness) dapat didefinisikan sebagai :
n
L s = 1  L i,s ( 6 )
n i = 1
n
T s = 1  T i,s ( 7 )
n i = 1

Sementara itu, jumlah pekerjaan yang terlambat dinyatakan dalam persamaan berikut :
n
NT =   i ( 8 )
i = 1
 i = 1 jika T i > 0 ;  i = 0 lainnya.
Lebih jauh lagi, barangkali kita akan tertarik pada jumlah kelambatan maksimum (Maximum Lateness) atau ukuran kelambatan maksimum (Maximum Tardiness) yang dinyatakan dalam persamaan berikut :

T max = max {0, L max }  i  n ( 9 )

L max = max {L i,s }  i  n (10)

Seperti telah disebutkan, makespan penjadwalan satu prosesor selalu konstan besarnya. Walaupun penjadwalan satu prosesor tidak akan berpengaruh terhadap besarnya makespan, tetapi pengurutan pekerjaan akan sangat berpengaruh pada waktu alir rata-rata (Mean Flow Time), kelambatan rata-rata (Mean Lateness) atau ukuran kelambatan rata-rata (Mean Tardiness).



E. ATURAN – ATURAN PENJADWALAN SATU PROSESOR

1. ATURAN SPT (WAKTU PEMROSESAN TERKECIL)
Pada saat menjadwalkan suatu kumpulan pekerjaan di sebuah prosesor, maka dengan aturan SPT pekerjaan diurutkan mulai dari waktu pemrosesan (Processing Time) terkecil sampai dengan pemrosesan yang terbesar.
Aturan SPT ini berguna untuk meminimasi waktu alir rata-rata (Mean Flow Time) dan meminimasi kelambatan rata-rata (Mean Lateness) pada sebuah prosessor tunggal yang harus mengerjakan sekumpulan pekerjaan.

Contoh Soal 1:
Jadwalkan pekerjaan-pekerjaan berikut agar Mean Flow Time-nya minimum :
Pekerjaan 1 2 3 4 5 6 7 8
Waktu Pemrosesan (jam) 5 8 6 3 10 14 7 3

Dengan menggunakan aturan SPT, maka urutan pekerjaan yang paling awal dijadwalkan ialah 4, selanjutnya 8 dan berturut-turut 1,3,7,2,5,6.
Waktu Alir Rata-rata (Mean Flow Time) dari persamaan (3) dapat disederhanakan menjadi :

Fs = 1 [ n t {1} + (n-1) t {2} + … + 2 t {n-1} + t {n} ] (11)
n

Waktu alir rata-ratanya ialah :

F s =1/8 ((8x3)+(7x3)+(6x5) + (5x6) + (4x7) + (3x8) + (2x10) + (1x14))
=1/8(24+21+30+30+28+24+20+14)
= 23,875 jam.

Sumber :
David D. Bedworth dan James E. Bailey, Integrated Production Control System : Management, Analysis, Design, John Wiley and Sons, New York, 1982, Hal. 304-305.


Sebagai tambahan, aturan SPT juga akan meminimasi kelambatan rata-rata (mean lateness) sehingga mengakibatkan minimasi waktu menunggu rata-rata (Mean Waiting Time), rata-rata jumlah pekerjaan yang menunggu dalam jumlah antrian (Mean Task Waiting in the queue ) dan meminimasi persediaan barang setengah jadi ( In process inventory). Perhatikan contoh soal berikut :

Contoh soal 2 :
Jadwalkan pekerjaan – pekerjaan berikut agar mean latenessnya minimum :
Pekerjaan 1 2 3 4 5 6 7 8
Waktu Pemrosesan (jam) 5 8 6 3 10 14 7 3
Batas Waktu (Due Date) 15 10 15 25 20 40 45 50

Dengan menggunakan aturan SPT, maka urutan pekerjaan yang dihasilkan ialah 4-8-1-3-7-2-5-6. Kelambatan (lateness) dari penjadwalan di atas dapat dihitung sebagai berikut:

Pekerjaan 4 8 1 3 7 2 5 6
Saat Selesai(Completion Time) jam 3 6 11 17 24 32 42 56
Batas Waktu (Due Date) 25 50 15 15 45 10 20 40
Kelambatan (Lateness) -22 -44 -4 +2 -21 22 22 16

Kelambatan rata-ratanya adalah –3,625 jam.

Suatu hal yang harus diperhatikan ialah urutan. Jika pekerjaan-pekerjaan cenderung muncul terus menerus, aturan SPT akan cenderung menghindari pekerjaan dengan waktu pemrosesan yang lama/ panjang. Dengan kata lain, aturan ini akan lebih mementingkan pekerjaan-pekerjaan dengan waktu yang lebih singkat, walaupun pekerjaan-pekerjaan itu muncul belakangan. Karenanya, aturan SPT akan menyebabkan waktu alir rata-rata (Mean Flow Time) yang lebih panjang untuk pekerjaan dengan waktu pemrosesan yang panjang.. Solusi untuk masalah di atas ialah dengan cara mengamati secara periodik untuk pekerjaan-pekerjaan yang telah menunggu terlalu lama. Pekerjaan yang telah menunggu lama harus dijadwalkan segera sebelum muncul lagi pekerjaan dengan waktu yang lebih pendek. Atau cara lainnya ialah dengan menganggap sekumpulan pekerjaan sebagai satu kelompok dan menjalankan pekerjaan-pekerjaan tersebut seluruhnya sebelum pekerjaan-pekerjaan baru muncul yang akan dikelompokkan ke dalam kelompok berikutnya.

2. ATURAN BOBOT SPT
Suatu variasi dari aturan SPT adalah aturan penjadwalan dengan menggunakan bobot. Aturan ini digunakan jika tingkat kepentingan dan prioritas tiap pekerjaan bervariasi. Semakin besar bobotnya, maka semakin besar pula prioritasnya. Dengan membagi waktu pemrosesan (Processing Time) dengan bobotnya, terdapat kecenderungan pergeseran pekerjaan yang lebih penting akan dijadwalkan terlebih dahulu.. Dalam hal ini, Rata-rata Waktu Alir Terbobot (Weighted Mean Flow Time) dapat dihitung dengan menggunakan persamaan :
n
 w i F i (12)
F w, s = i = 1
n
 w i
i = 1

Pada saat menjadwalkan n pekerjaan pada sebuah prosesor tunggal di mana tiap pekerjaan i memiliki bobot relatif w , maka rata-rata waktu alir terbobot (Weighted Mean Flow Time) akan diminimasi dengan cara mengurutkan berdasarkan aturan berikut :

t [ 1 ] t [ 2 ] t [ n ]
< < . . . < ( 13 )
w [ 1 ] w [ 2 ] w [ n ]

Contoh Soal 3 :
Pekerjaan 1 2 3 4 5 6 7 8
Waktu Pemrosesan 5 8 6 3 10 14 7 3
Bobot Relatif 1 2 3 1 2 3 2 1
t/w 5 4 2 3 5 4.7 3.5 3

Urutan yang dihasilkan ialah 3-4-8-7-2-6-5-1. Waktu alir rata-rata ialah 27 jam (bandingkan dengan SPT yang hanya menghasilkan 23,875 jam). Sementara itu Waktu Alir Rata-rata Terbobot ialah 27,47 jam.

Sumber :
David D. Bedworth dan James E. Bailey, Integrated Production Control System : Management, Analysis, Design, John Wiley and Sons, New York, 1982, Hal. 306 .

3. ATURAN EARLIEST DUE DATE (EDD)
Aturan lainnya yang perlu diketahui ialah aturan EDD. Aturan ini menyebutkan bahwa pengurutan pekerjaan berdasarkan Batas Waktu (Due Date) tercepat. Pekerjaan dengan saat jatuh tempo paling awal harus dijadwalkan terlebih dahulu daripada pekerjaan dengan saat jatuh tempo belakangan.
Aturan ini bertujuan untuk meminimasi kelambatan maksimum (Maximum Lateness) atau meminimasi ukuran kelambatan maksimum (Maksimum Tardiness) suatu pekerjaan. Buruknya, aturan ini akan menyebabkan jumlah pekerjaan yang terlambat akan menjadi besar serta akan menambah ukuran kelambatan rata-rata (Mean Tardiness). Perhatikan contoh soal di bawah ini dan bandingkan hasil penjadwalannya dengan contoh soal 2 di bagian awal.

Contoh Soal 4 :
Jadwalkan pekerjaan-pekerjaan berikut agar Maximum Lateness-nya minimum :
Pekerjaan 1 2 3 4 5 6 7 8
Waktu Pemrosesan (jam) 5 8 6 3 10 14 7 3
Batas Waktu (Due Date) 15 10 15 25 20 40 45 50

Dengan menggunakan aturan SPT, maka urutan pekerjaan yang dihasilkan ialah 4-8-1-3-7-2-5-6. Jumlah pekerjaan yang terlambat ialah 4 (empat) dengan rata-rata kelambatan sebesar –3,625 jam dan maksimum kelambatan sebesar 22 jam. Dengan menggunakan aturan EDD, maka urutan penjadwalan pekerjaannya ialah 2-1-3-5-4-6-7-8.
Berdasarkan aturan EDD, dapat dihitung kelambatan pekerjaan-pekerjaan berikut:


Pekerjaan 2 1 3 5 4 6 7 8
Waktu Pemrosesan (jam) 8 5 6 10 3 14 7 3
Waktu Alir (jam) 8 13 19 29 32 46 53 56
Batas Waktu (Due Date) 10 15 15 20 25 40 45 50
Kelambatan (Lateness) -2 -2 4 9 7 6 8 6

Dengan menggunakan aturan EDD, jumlah pekerjaan yang terlambat bertambah dari 4 (empat ) menjadi 6 (enam) dengan rata-rata kelambatan sebesar –3,625 jam menjadi 4,5 jam. Walaupun demikian, kelambatan maksimum dapat ditekan dari 22 jam menjadi tinggal 9 jam.

Sumber :
David D. Bedworth dan James E. Bailey, Integrated Production Control System : Management, Analysis, Design, John Wiley and Sons, New York, 1982, Hal. 308.

4. ALGORITME HODGSON
Misalkan penalty atas pekerjaan-pekerjaan yang terlambat sama untuk seluruh pekerjaan dan tak tergantung pada seberapa lama tingkat keterlambatannya.. Aturan EDD akan memberikan hasil yang terbaik jika dan hanya jika terdapat hanya satu atau nol pekerjaan yang terlambat. Jika terdapat lebih dari satu pekerjaan terlambat, algoritme heuristik yang dikembangkan oleh Hodgson akan memberikan hasil yang lebih baik. Algoritma Hodgson adalah sebagai berikut :

Step 1 : Susun seluruh pekerjaan dengan menggunakan aturan EDD. Jika hanya nol atau satu pekerjaan yang terlambat (memiliki ukuran kelambatan yang positif), maka stop. Selain dari itu, ke step kedua.

Step 2 : Mulailah dari awal urutan yang dihasilkan aturan EDD dan lihatlah jadwal tersebut sampai akhir. Tandai pekerjaan pertama yang terlambat. Jika tidak ada pekerjaan berikutnya yang terlambat, ke step 4 lainnya ke step 3.

Step 3 : Misalnya pekerjaan yang terlambat tersebut berada di posisi ke-1 dalam urutan penjadwalan yang dihasilkan. Periksa pekerjaan – pekerjaan lainnya yang tidak terlambat dan berada di posisi sebelum posisi ke-i . Tandai pekerjaan dengan waktu pemrosesan terbesar. Pindahkan pekerjaan itu dan ulangi lagi perhitungan waktu penyelesaian seluruh pekerjaan setelah pemindahan. Kembali ke step 2.

Step 4 : Letakkan semua pekerjaan yang dipindahkan tadi dalam urutannya semula di akhir penjadwalan.

Untuk menggambarkan algoritme di atas, perhatikan data pada contoh-contoh soal sebelumnya.

Contoh Soal 5 :
Jadwalkan pekerjaan-pekerjaan berikut agar jumlah pekerjaan yang terlambatnya minimum.
Pekerjaan 1 2 3 4 5 6 7 8
Waktu Pemrosesan (jam) 5 8 6 3 10 14 7 3
Batas Waktu (Due Date) 15 10 15 25 20 40 45 50

Dengan menggunakan aturan EDD (Step 1), maka urutan penjadwalan pekerjaannya ialah 2-1-3-5-4-6-7-8, dengan enam pekerjaan yang terlambat (lihat lagi contoh soal 4). Kita beranjak ke step 2 dan 3 seperti berikut ini.
Pekerjaan 2 1 3 5 4 6 7 8
Waktu Pemrosesan (jam) 8 5 6 10 3 14 7 3
Waktu Penyelesaian 8 13 19 29 32 46 53 56
Batas Waktu (Due Date) 10 15 15 20 25 40 45 50
Kelambatan -2 -2 4 9 7 6 8 6

Pekerjaan nomor 3 adalah pekerjaan pertama yang terlambat. Pekerjaan 2 memiliki waktu pemrosesan terpanjang dari 3 pekerjaan pertama, maka pekerjaan itu disisihkan. Hasilnya ialah :
Pekerjaan i 1 3 5 4 6 7 8
Waktu Pemrosesan (jam) 5 6 10 3 14 7 3
Waktu Penyelesaian 5 11 21 24 38 45 48
Batas Waktu (Due Date) 15 15 20 25 40 45 50
Kelambatan -10 -4 1 -1 -2 0 -2

Pekerjaan 5 adalah pekerjaan pertama yang terlambat. Dan dari tiga pekerjaan yang berada pada urutan pertama, kedua dan ketiga; pekerjaan 5 memiliki waktu pemrosesan terpanjang. Oleh karenanya pekerjaan 5 disisihkan. Hasilnya ialah :

Pekerjaan i 1 3 4 6 7 8
Waktu Pemrosesan (jam) 5 6 3 14 7 3
Waktu Penyelesaian 5 11 14 28 35 38
Batas Waktu (Due Date) 15 15 25 40 45 50
Kelambatan -10 -4 -11 -12 -10 -12

Tidak ada satu pun juga pekerjaan yang terlambat. Oleh karenanya pekerjaan 2 dan 5 yang tadi disisihkan ditambahkan lagi di akhir jadwal yang terbentuk. Dengan menggunakan aturan SPT untuk penambahan kedua pekerjaan itu ke dalam jadwal, didapatkan urutan 1-3-4-6-7-8-2-5. Penjadwalan tersebut menghasilkan :

Pekerjaan
i Waktu Penyelesaian
ci Batas Waktu
di Kelambatan
Li
1 5 15 -10
3 11 15 -4
4 14 25 -11
6 28 40 -12
7 35 45 -10
8 38 50 -12
2 46 10 36
5 56 20 36

Algoritma Hodgson ini menghasilkan jumlah pekerjaan yang terlambat sebesar dua pekerjaan. Kelambatan rata-rata 1,625 jam (bandingkan dengan hasil aturan SPT yang menghasilkan kelambatan –3,626 jam). Kelambatan maksimum ialah sebesar 36 jam ( bandingkan dengan aturan EDD yang menghasilkan kelambatan maksimum sebesar 9 jam ).
Sumber :
David D. Bedworth dan James E. Bailey. Integrated Production Control System : Management, Analysis, Design, John Wiley and Sons, New York, 1982, Hal. 309-310.
5. ALGORITMA WILKERSON IRWIN

Tujuan yang paling sukar untuk dipenuhi adalah minimasi kelambatan rata-rata. Hal ini terjadi jika penalty atas kelambatan suatu pekerjaan sama besarnya dan berbanding lurus dengan lamanya kelambatan. Tidak ada metode yang mudah untuk menyelesaikan masalah ini. Dalam situasi-situasi khusus terdapat aturan sebagai berikut :

a. Jika terdapat hanya satu atau nol pekerjaan yang terlambat, maka aturan EDD akan meminimasi ukuran kelambatan rata-rata (mean tardiness).
b. Jika seluruh pekerjaan memiliki batas waktu (due date) yang sama, atau jika aturan SPT menghasilkan seluruh pekerjaan terlambat; maka aturan SPT akan meminimasi ukuran kelambatan rata-rata (mean tardiness).
c. Aturan minimasi kelonggaran (Slack Time) juga memiliki kecenderungan untuk meminimasi ukuran kelambatan rata-rata, tetapi tidak dapat diterapkan untuk sebuah kasus.

Untuk itu Wilkerson Irwin mengemukakan satu algoritma heuristik yang dapat meminimasi ukuran kelambatan rata-rata.

Algoritma Wilkerson Irwin dapat dijelaskan sebagaimana uraian di bawah ini :

Step 1 : Susun urutan pekerjaan berdasarkan aturan EDD. Bandingkan dua pekerjaan pertama di daftar tersebut.. Sebut kedua pekerjaan ini sebagai a dan b. Jika max (ta dan tb) < max (da, db), tempatkan pekerjaan a ke kolom alpha dan pekerjaan b ke kolom betha. Jika kondisi di atas tidak terpenuhi, maka tempatkan pekerjaan dengan waktu pemrosesan terpendek ke kolom alpha dan lainnya ke kolom betha. Pekerjaan ketiga dalam urutan EDD itu ditempatkan dalam kolom gamma.

Step 2: Bandingkan betha dan gamma untuk melihat apakah betha akan dapat dijadwalkan bersama dengan alpha. Jika t beta < t gamma atau jika F alpha + max { t betha, t gamma} < max {d betha , d gamma}, pindahkan pekerjaan di kolom beta ke kolom alpha dan pekerjaan gamma ke kolom beta. Pekerjaan selanjutnya di dalam daftar EDD akan menjadi ditempatkan di kolom gamma. Jika tidak ada lagi pekerjaan di dalam daftar EDD, tambahkan pekerjaan di kolom alpha dan beta ke dalam jadwal dan stop. Jika tidak ulangi step 2 (dua). JIKA KEDUA KONDISI YANG DISEBUTKAN DI ATAS TAK TERPENUHI maka kerjakan step 3 (tiga).

Step 3: Kembalikan pekerjaan di kolom beta ke dalam daftar EDD dan pindahkan pekerjaan di kolom Gamma ke dalam kolom beta. Bandingkan alpha dan beta untuk melihat apakah beta akan dijadwalkan bersama dengan alpha.. Jika t alpha < t beta atau jika F alpha – t alpha + max {t alpha, t beta } < max { d alpha , t beta } pindahkan pekerjaan di kolom beta ke kolom alpha dan pilih dua pekerjaan berikutnya dalam daftar EDD sebagai beta dan gamma yang baru. Ulangi step 2 ( dua ). JIKA KONDISI DI ATAS TIDAK DIPENUHI maka kerjakan Step 4 ( empat ).

Step 4: Pindahkan pekerjaan di kolom alpha kembali ke daftar EDD dan tempatkan pekerjaan terakhir yang masuk ke dalam jadwal sebagai alpha yang baru. Kembali ke Step 3 (tiga ).
Jika tidak ada pekerjaan yang telah dijadwalkan, letakkan beta ke dalam jadwal dan dua pekerjaan pertama dalam daftar EDD menjadi beta dan gamma. Kembali ke step 2 (dua).

Untuk aplikasi Algoritme Wilkerson – Irwin perhatikan contoh soal 6 berikut ini :
Contoh Soal 6 :

Jadwalkan pekerjaan-pekerjaan berikut agar ukuran kelambatan rata-rata (mean tardiness-nya) minimum !

Pekerjaan 1 2 3 4 5 6 7 8
Waktu Pemrosesan (jam) 5 8 6 3 10 14 7 3
Batas Waktu (Due Date) 15 10 15 25 20 40 45 50

Dengan menggunakan aturan EDD, maka urutan penjadwalan pekerjaannya ialah 2-1-3-5-4-6-7-8.


Step 1 : Pekerjaan a ialah 2, pekerjaan b ialah 1.
Max { t a , t b } = Max { t 2 , t 1 } = Max { 8 , 5 } = 8
Max { d a , d b } = Max { d 2 , d 1 } = Max { 10 , 15 } = 15

Karena 8 < 15 maka pekerjaan a ( = pekerjaan 2 ) diletakkan di kolom alpha dan pekerjaan b (= pekerjaan 1) diletakkan di kolom beta. Pekerjaan selanjutnya ( = pekerjaan 3 ) diletakkan di kolom gamma.

Step – step selanjutnya perhatikan tabel berikut :

Step    Kondisi 1 Kondisi 2
2 2 1 3 8 + 6 < 15 Y 5 < 6 Y
2 1 3 5 13 + 10 < 20 T 6 < 10 Y
2 3 5 4 19 + 10 < 25 T 10 < 3 T
3 3 4 - 19 – 6 + 6 < 25 Y 6 < 3 T
2 4 5 6 22 + 14 < 40 Y 10 < 14 Y
2 5 6 7 32 + 14 < 45 T 14 < 7 T
3 5 7 - 32 – 10 – 10 < 45 Y 10 < 7 T
2 7 6 8 39 + 14 < 50 T 14 < 3 T
3 7 8 - 39 – 7 + 7 < 50 Y 7 < 3 T

Urutan penjadwalan = 2-1-3-4-5-7-8-6.

Catatan : Kondisi Pengujian ialah sebagai berikut .


Step 2 Step 3

Hasil penjadwalan di atas memberikan ukuran kelambatan sebagai berikut :



Pekerjaan
i Waktu Penyelesaian
c i Batas Waktu
d i Ukuran Kelambatan
T i
2 8 10 0
1 13 15 0
3 19 15 4
4 22 25 0
5 32 20 12
7 39 45 0
8 42 50 0
6 56 40 16

Yang akan menghasilkan ukuran kelambatan rata-rata ( Tardiness) sebesar 4 jam, yang ternyata ialah harga paling minimum. Dari seluruh 40.320 kemungkinan kombinasi urutan ke delapan pekerjaan itu, hanya empat yang memiliki ukuran kelambatan rata-rata sebesar 4 jam.
Hasil tersebut di atas perlu pula dibandingkan dengan metode lain. Metode yang paling mudah dan sering digunakan ialah aturan Shortest Slack Time. Kelonggaran (Slack) didefinisikan sebagai selisih antara batas waktu ( due date) dengan waktu pemrosesan (processing time). Hasil perhitungan kelonggaran disajikan berikut ini :

Pekerjaan
i Waktu Penyelesaian
c i Batas Waktu
d i Kelonggaran
SL i
1 5 15 10
2 8 10 2
3 6 15 9
4 3 25 22
5 10 20 10
6 14 40 26
7 7 45 38
8 3 50 47

Urutan penjadwalan yang dihasilkan ialah 2-3-1-5-6-4. Urutan ini akan menghasilkan rata-rata ukuran kelambatan (Mean Tardiness) sebesar 5 jam.
Jelas sekali bahwa algoritme Wilkerson – Irwin menghasilkan solusi yang lebih layak dibandingkan dengan Shortest Slack Time. Tetapi perlu dikaji ulang solusi algoritme Wilkerson – Irwin ini dengan menggunakan sebuah test sederhana. Hitung periode kelambatan tiap pekerjaan (waktu antara batas waktu pekerjaan tersebut [ Due Date] dengan saat penyelesaian pekerjaan itu). Perhatikan periode kelambatan tersebut. Jika periode kelambatan itu tidak saling tumpang tindih ( dalam arti kata : tidak ada dua pekerjaan yang terlambat pada saat yang bersamaan ), maka solusi yang dihasilkan akan meminimasi ukuran kelambatan (Mean Tardiness) rata-rata.

Sumber :
David D. Bedworth dan James E. Bailey, Integrated Production Control System : Management, Analysis, Design, John Wiley and Sons, New York, 1982, Hal. 311-314.

KESIMPULAN
Dalam tulisan ini kita telah mendiskusikan masalah penjadwalan n pekerjaan di satu prosesor. Semua pekerjaan diassumsikan diketahui di awal periode penjadwalan, seluruh waktu pemrosesan diketahui dan dianggap tak tergantung dari urutan yang dipilih.

Tujuan menjadwalkan pekerjaan dapat bermacam-macam. Tujuan menekan makespan dapat dicapai dengan seluruh metode yang telah disebutkan, karena makespan tidak tergantung dari urutan pekerjaan yang dihasilkan dalam jadwal. Tujuan penjadwalan lainnya dan teknik yang sesuai untuk menghasilkan solusi penjadwalan yang memenuhi tujuan tersebut ialah :
a. Minimasi Waktu Alir Rata-rata (Mean Flow Time) ialah dengan menggunakan aturan SPT.
b. Minimasi Waktu Alir Rata-rata Terbobot (Weighted Mean Flow Time) ialah dengan menggunakan aturan WSPT.
c. Minimasi Kelambatan Rata-rata (Mean Lateness) ialah dengan menggunakan aturan SPT.
d. Minimasi Ukuran Kelambatan Maksimum (Maximum Tardiness) ialah dengan menggunakan aturan EDD.
e. Minimasi Jumlah Pekerjaan Yang Terlambat ialah dengan menggunakan Algoritme Hodgson.
f. Minimasi Ukuran Kelambatan Rata-rata (Mean Tardiness) dapat menggunakan aturan Shortest Slack Time atau Algoritme Wilkerson – Irwin.

SOAL LATIHAN
PEKERJAAN WAKTU PROSES BOBOT RELATIF BATAS WAKTU
DATA A
1 1 3 10
2 10 2 20
3 5 1 15
4 2 1 10
5 8 4 10
6 7 2 25
7 8 3 15
8 4 3 25
9 3 2 10
10 6 4 20
DATA B
1 5 3 30
2 6 2 30
3 11 1 40
4 8 3 80
5 12 2 100
6 14 1 70
7 7 3 90
8 10 2 80
9 6 1 40
10 12 3 90





PERTANYAAN:

Gunakan data A.
1. Cari jadwal dengan waktu alir rata-rata minimum. Berapa waktu alir rata-rata yang paling minimum tersebut ?
2. Cari jadwal yang meminimasi waktu alir rata-rata terbobot. Berapa waktu alir rata-rata terbobot jadwal tersebut ?
3. Hitung jadwal yang akan meminimasi kelambatan rata-rata.
4. Hitung jadwal yang akan meminimasi kelambatan maksimum.
5. Hitung jadwal yang akan meminimasi jumlah pekerjaan yang terlambat.
6. Hitung jadwal dengan aturan “ Kelonggaran Terkecil “ ( Minimum Slack ).
7. Gunakan Algoritme Wilkerson Irwin untuk meminimasi kelambatan rata-rata. Apakah urutan penjadwalan yang dihasilkan benar-benar meminimasi kelambatan rata-rata.
8. Bandingkan kelambatan rata-rata, waktu terlambat maksimum, dan jumlah pekerjaan yang terlambat dari soal 4,5 dan 6.


Gunakan Data B :
Misalkan waktu pemrosesan dalam data B ialah perkiraan menit eksekusi untuk sepuluh program komputer. Tujuan si programmer ialah meminimasi waktu untuk menjalankan program tersebut.
1. Berdasarkan hasil yang anda peroleh dari soal di atas, misalnya tingkat kepentingan program-program itu dapat dikategorikan menjadi tiga. Dengan aturan apakah penjadwalan program harus dilakukan dan bagaimanakah jadwal yang akan dihasilkan.
2. Misalkan pekerjaan di data B ialah prakiraan waktu kerja seorang drafter. Waktu pemrosesan mencerminkan besarnya usaha si drafter ( dalam satuan hari ). Misalnya terdapat kelambatan sebesar $ 100 per hari kelambatan setelah batas waktu ( due date ). Bagaimana pekerjaan harus dijadwalkan agar meminimasi total ongkos ?
3. Misalnya setiap komponen si drafter tersebut meminta agar seluruh pekerjaan diselesaikan segera, bagaimanakah anda menjadwalkan pekerjaan yang harus dilakukan.