CPM dan Pert

2.1         CPM(Critical Path Method)dan PERT (Project Evaluation and Review Technique)

PERT dan CPM dikembangkan pada tahun 1950-an unutk membantu para manajer membuat penjadwalan, memonitor, dan mengendalikan proyek besar dan kompleks. CPM muncul terlebih dahulu, di tahun 1957 sebagai alat yang dikembangkann oleh J. E. Kelly dari Remington Rand dan M. R. Walker dari DuPont untuk membantu pembangunan dan pemeliharaan pabrik kimia di DuPont Secara terpisah, PERT dikembangkan di tahun 1958 oleh Booz, Allen, dan Hamilton untuk U. S. Navy (Angkatan Laut Amerika). (Heizer, Jay dan Render, Barry, 2006).

Meskipun PERT dan CPM berbeda pada beberapa hal dalam terminologi dan pada konstruksi jaringan, tujuan mereka sama. Analisis yang digunakan pada kedua teknik ini sangat mirip. Perbedaan utamanya adalah bahwa PERT menggunakan tiga perkiraan waktu untuk tiap kegiatan. Perkiraan waktu ini digunakan untuk menghitung nilai yang diharapkan dan penyimpangan standar untuk kegiatan tersebut. CPM membuat asumsi bahwa waktu kegiatan diketahui pasti, hingga hanya diperlukan satu faktor waktu untuk setiap kegiatan.

CPM dan PERT merupakan metode yang berorientasi pada waktu arti keduanya mengarah pada penentuan sejumlah jadwal. Terdiri 3 tahap dasar yaitu perencanaan, penjadwalan, dan pengendalian. Tahap perencanaan dimulai dengan memecahkan proyek kedalam beberapa kegiatan yang berbeda. Estimasi waktu untuk kegiatan-kegiatan ini lalu ditentukan dan diagram panah dikembangkan dengan panah mewakili satu kegiatan. Keseluruhan diagram panah tersebut memberikan representasi grafik dari ketergantungan diantara kegiatan-kegiatan dalam proyek tersebut. Pengembangan diagram panah sebagai suatu tahap perencanaan memiliki keuntungan berupa dipelajarinya tugas-tugas yang berbeda secara terinci sambil kemungkinan menyarankan perbaikan-perbaikan sebelum proyek tersebut dilaksanakan. Yang lebih penting lagi adalah penggunaanya untuk mengembangkan sebuah jadwal untuk proyek tersebut.

2.2         Pengertian CPM dan PERT

CPM adalah suatu metode yang dirancang untuk mengoptimalkan biaya proyek dimana dapat ditentukan kapan pertukaran biaya dan waktu harus dilakukan untuk memenuhi jadwal penyelesaian proyek dengan biaya seminimal mungkin. CPM merupakan suatu metode perencanaan dan pengendalian proyek-proyek yang merupakan sistem yang paling banyak digunakan diantara semua sistem yang memakai prinsip pembentukan jaringan. Dengan CPM, jumlah waktu yang dibutuhkan untuk menyelesaikan berbagai tahap suatu proyek dianggap diketahui dengan pasti, demikian pula hubungan antara sumber yang digunakan dan waktu yang diperlukan untuk menyelesaikan proyek.(Handoko, 2000)

PERT adalah suatu metode analisis yang dirancang untuk membantu dalam penjadwalan dan pengendalian proyek-proyek yang kompleks, yang menuntut bahwa masalah utama yang dibahas yaitu masalah teknik untuk menentukan jadwal kegiatan beserta anggaran biayanya sehingga dapat diselesaikan secara tepat waktu. PERT memiliki asumsi bahwa proyek yang akan dilaksanakan adalah baru, tidak ada contoh sebelumnya. Berdasarkan atas asumsi itu, maka orientasi dari metode PERT adalah mengoptimalkan waktu penyelesaian proyek dan belum menekankan soal minimisasi biaya. Oleh karena belum ada pengalaman sebelumnya, maka waktu penyelesaian pekerjaan tertentu yang ada dalam proyek bersifat probabilistik.(Handoko, 2000)

2.3         Perkiraan Waktu CPM dan PERT

Persyaratan urutan pengerjaan harus diperhatikan, karena berbagai aktivitas tidak dapat dimulai sebelum aktivitas-aktivitas lainnya yang dapat dilaksanakan secara bersamaan dan/ atau tidak saling tergantung. CPM mengenal beberapa waktu mulai dan waktu berakhir, antara lain (Handoko, 2000):

a.   Earliest Start Time (ES) adalah waktu paling awal (tercepat) suatu aktivitas dapat dimulai, dengan memperhatikan waktu aktivitas yang diharapkan dan persyaratan ururtan pengerjaan.

b.   Latest Start Time (LS) adalah waktu paling lambat untuk dapat memulai suatu aktivitas tanpa penundaan keseluruhan proyek.

c.   Earliest Finish Time (EF) adalah waktu paling awal (tercepat) suatu aktivitas dapat diselesaikan, atau sama dengan ES + waktu aktivitas yang diharapkan.

d.   Latest Finish Time (LF) adalah waktu paling lambat untuk dapat menyelesaikan suatu aktivitas tanpa penundaan penyelesaian proyek secara keseluruhan, atau sama dengan LS + waktu kegiatan yang diharapkan.

Memperkirakan waktu yang diperlukan untuk masing-masing kegiatan seperti menit, jam, hari, minggu atau bulan adalah unit umum yang biasa digunakan waktu untuk penyelesaian suatu kegiatan. Sebuah fitur yang membedakan PERT adalah kemampuannya untuk menghadapi ketidakpastian di masa penyelesaian kegiatan. Untuk setiap aktivitas, model biasanya mencakup tiga perkiraan waktu (Soeharto, 2002):

a.   Waktu Optimis, yaitu perkiraan waktu yang paling singkat bagi penyelesaian aktivitas.

b.   Waktu Perkiraan Paling Mungkin, waktu penyelesaian yang memiliki probabilitas tertinggi (berbeda dengan : waktu yang diharapkan).

c.   Waktu Pesimis, yaitu waktu terpanjang yang mungkin diperlukan suatu kegiatan.

2.4         Sistem CPM dan PERT

Sistem CPM dan PERT adalah salah satu model yang digunakan dalam penyenggaraan produksi proyek yang produknya adalah informasi mengenai kegiatan-kegiatan yang ada dalam sistem CPM dan PERT yang bersangkutan. Informasi tersebut mengenai sumber daya yang digunakan oleh kegiatan yang bersngkutan dan informasinya mengenai jadwal pelaksanaannya.

Meskipun sistem CPM dan PERT termasuk sistem informasi dalam menyelenggaraan produksi proyek, tetapi tidak semua informasi bisa diberikan pada sistem CPM dan PERT untuk diproses dan tidak semua informasi dilaporkan oleh sistem CPM dan PERT. Informasi yang ada kaitannya dengan sistem CPM dan PERT hanya menyangkut kegiatan yang ada dalam sistem CPM dan PERT hanya menyangkut kegiatan yang ada dalam sistem CPM dan PERT saja.

Input berupa preseden diagram (network diagram) mutlak diperlukan untuk menerapkan sistem CPM dan PERT. Network diagram menunjukan gambar grafis seluruh aktivitas yang diperlukan untuk membuat produk beserta hubungan ketergantungannya. Model ini harus lengkap dan sesuai dengan kondisi nyata. Dalam praktik, akan terdapat kegiatan-kegiatan yang berdasarkan pertimbangan tertentu tidak termasuk dalam network diagram. Di samping informasi kegiatan, masih diperlukan informasi sumber daya, yang bertujuan memberi informasi yang tepat agar sumber daya yang dibutuhkan selalu dalam keadaan siap pakai. Kedua hal terakhir ini perlu di desain modelnya, agar sistem CPM dan PERT berhasil.

2.5         Perbedaan CPM dan PERT

Pada prinsipnya yang menyangkut perbedaan PERT dan CPM adalah sebagai berikut :

1.   PERT digunakan pada perencanaan dan pengendalian proyek yang belum pernah dikerjakan, sedangkan CPM digunakan untuk menjadwalkan dan mengendalikan aktivitas yang sudah pernah dikerjakan sehingga data, waktu dan biaya setiap unsur kegiatan telah diketahui oleh evaluator.

2.   Pada PERT digunakan tiga jenis waktu pengerjaan yaitu yang tercepat, terlama serta terlayak, sedangkan pada CPM hanya memiliki satu jenis informasi waktu pengerjaan yaitu waktu yang paling tepat dan layak untuk menyelesaikan suatu proyek.

3.   Pada PERT yang ditekankan tepat waktu, sebab dengan penyingkatan waktu maka biaya proyek turut mengecil, sedangkan pada CPM menekankan tepat biaya.

4.   Dalam PERT anak panah menunjukkan tata urutan (hubungan presidentil), sedangkan pada CPM tanda panah adalah kegiatan.

2.6         Simbol-simbol CPM dan PERT

Simbol-simbol yang digunakan dalam menggambarkan suatu networkadalah sebagai berikut (Hayun, 2005) :

1.   (anak panah/busur), mewakili sebuah kegiatan atau aktivitas yaitutugas yang dibutuhkan oleh proyek. Kegiatan di sini didefinisikan sebagai halyang memerlukan duration (jangka waktu tertentu) dalam pemakaiansejumlah resources (sumber tenaga, peralatan, material, biaya). Kepala anakpanah menunjukkan arah tiap kegiatan, yang menunjukkan bahwa suatukegiatan dimulai pada permulaan dan berjalan maju sampai akhir dengan arahdari kiri ke kanan.

2.   (lingkaran kecil/simpul/node), mewakili sebuah kejadian atauperistiwa atau event. Kejadian (event) didefinisikan sebagai ujung ataupertemuan dari satu atau beberapa kegiatan. Sebuah kejadian mewakili satutitik dalam waktu yang menyatakan penyelesaian beberapa kegiatan dan awalbeberapa kegiatan baru. Kegiatan-kegiatan yang berawal dari saat kejadian tertentutidak dapat dimulai sampai kegiatan-kegiatan yang berakhir pada kejadianyang sama diselesaikan. Suatu kejadian harus mendahulukan kegiatan yangkeluar dari simpul/node tersebut.

3.   (anak panah terputus-putus), menyatakan kegiatan semu ataudummy activity. Setiap anak panah memiliki peranan ganda dalam mewakilikegiatan dan membantu untuk menunjukkan hubungan utama antara berbagaikegiatan. Bedanya dengan kegiatan biasa ialahbahwa kegiatan dummy tidak memakan waktu dan sumbar daya, jadi waktukegiatan dan biaya sama dengan nol.

d. (anak panah tebal), merupakan kegiatan pada lintasan kritis.

2.7         Rumus-rumus Perhitungan CPM dan PERT

Rumus-rumus perhitungan yang digunakan dalam modul CPM dan PERT ini terdiri dari beberapa rumus seperti dibawah ini:

·      Untuk CPM mengunakan Lintasan Kritis / diagram network .

 

Gambar 2.1 aktivitas Dummy          Gambar 2.2 lingkaran kejadian untuk              perhitungan

 

Gambar 2.3 Diagram Network CPM

·      Untuk PERT mengunakan slope, waktu ekspektasi (te), varians dan probabilitas penyelesaian proyek.

Rumus probabilitas penyelesaian proyek:

 

Keterangan:

C_c   = Biayadipercepat       t_p          = Waktupesimis

C_n   = Biaya normal           t_m         = Wakturealistis

T_n    = Waktu normalTD     = Waktuproyek (dijadwalkan)

T_c    = Waktudipercepatσ_TE                = Deviasistandaruntuk TE(Jalurkritis)

t_o     = WaktuoptimisTE      = Waktuproyekdiselesaikan

      

DAFTAR PUSTAKA

Hani T, Handoko. 2000. DASAR-DASAR MANAJEMEN PRODUKSI DAN OPERASI.Edisi pertama. Yogyakarta: BPFE-Yogyakarta.

Hayun, Anggara. 2005. “Perencanaan dan Pengendalian Proyek dengan Metode PERT-CPM : Studi Kasus Fly Over Ahmad Yani, Karawang.” Journal The Winners, Vol. 6, No.2, h. 155-174.

Heizer, Jay dan Render, Barry. 2006. Manajemen Operasi (Edisi 7). Salemba Empat, Jakarta.

Penjadwalan

1.     Penjadwalan Flow Shop Dengan Metode Johnson Algoritma

Misalnya, mesin dengan urutan proses M1, M2, dan M3. Semua job mempunyai urutan pengerjaan yang sama. Waktu proses job 1 pada mesin j disimbolkan dengan tij. Algoritma Johnson untuk dua mesin dapat diaplikasikan pada problem n job tiga mesin bila memenuhi :

Min  > = max   atau

Min  > = max

Dengan kata lain, minimal waktu proses pada semua job pada mesin 1 dan 3 harus lebih besar dari waktu proses terpanjang pada mesin 2. Untuk mengaplikasikan algoritma Johnson, waktu proses 3 mesin dirancang ulang menjadi 2 mesin (M1’, M2’) dengan aturan : waktu proses job pada M1’ = ti1+ti2 dan waktu proses job pada M2’ = ti3+ti2, kemudian algoritma Johnson diaplikasikan pada M1’ dan M2’.

Contoh Soal :

Dapatkan urutan optimal untuk 6 job berikut, dimana keenam job tersebut harus diproses pada mesin M1, M2, dan M3 dengan urutan tersebut!

Job	Waktu proses pada mesin
	M1	M2	M3
1	4	3	9
2	6	0	5
3	5	4	7
4	8	3	3
5	5	2	2
6	7	1	8

Jawab :

            Test Kondisi :

·         Minimal waktu proses di mesin 1 = 4 menit

·         Maksimal waktu proses di mesin 2 = 4 menit

·         Minimal waktu proses di mesin 3 = 2 menit

Ternyata syarat untuk dapat diterapkannya algoritma Johnson terpenuhi. Kemudian berikutnya waktu proses ketiga mesin tersebut disusun ulang menjadi 2 mesin sebagai berikut.

Job	Waktu proses pada mesin
	M1'	M2'
1	7	12
2	6	5
3	9	11
4	11	6
5	7	4
6	8	9

Dengan algoritma Johnson didapatkan iterasi sebagai berikut.

Iterasi 1

Job	Waktu proses pada mesin
	M1'	M2'
1	7	12
2	6	5
3	9	11
4	11	6
5	7	4
6	8	9

J5

Iterasi 2

Job	Waktu proses pada mesin
	M1'	M2'
1	7	12
2	6	5
3	9	11
4	11	6
6	8	9

J2

J5

Iterasi 3

Job	Waktu proses pada mesin
	M1'	M2'
1	7	12
3	9	11
4	11	6
6	8	9

J4

J2

J5

Iterasi 4

Job	Waktu proses pada mesin
	M1'	M2'
1	7	12
3	9	11
6	8	9

J1

J4

J2

J5

Iterasi 5

Job	Waktu proses pada mesin
	M1'	M2'
3	9	11
6	8	9

J1

J6

J4

J2

J5

Maka urutan penjadwalan yang optimal adalah sebagai berikut :

J1

J6

J3

J4

J2

J5

2.     Penjadwalan Flow Shop Dengan Metode  CDS (Campbell Dudek and Smith)

Metode heuristik yang paling penting untuk problem make-span adalah metode Campbell, Dudek and Smith (CDS). Metode CDS ini memiliki kelebihan dalam dua hal, yaitu :

1.     Pemakaian aturan Johnson dalam sebuah cara heuristic,

2.     Biasanya menghasilkan beberapa jadwal yang dapat dipilih sebagai yang terbaik.

Algoritma Johnson merupakan suatu algoritma yang digunakan untuk mendapatkan optimal sequence (pengurutan penjadwalan yang optimal) untuk jenis flow shop. Adapun tahapan-tahapan dari algoritma Johnson adalah sebagai berikut.

1.      Buatlah daftar waktu proses untuk seluruh pekerjaan-pekerjaan tersebut,baik pada mesin pertama (M-1) dan mesin terakhir (M-2).

2.      Carilah seluruh waktu proses untuk seluruh pekerjaan. Tentukan waktu proses yang minimal (,).

3.      Jika waktu proses minimal berada pada mesin pertama (M-1), tempatkan pekerjaan tersebut paling awal yang mungkin dalam urutan. Jika terletak pada mesin kedua (M-2), tempatkan pekerjaan-pekerjaan tersebut paling akhir yang mungkin dalam urutan!

4.      Hilangkan pekerjaan yang telah ditugaskan (telah ditempatkan dalam urutan dan sebagai hasil dari langkah 3) dan ulangi langkah 2 dan langkah 3 sehingga seluruh pekerjaan telah diurutkan.

Algoritma CDS ini cocok untuk persoalan yang memiliki banyak tahapan (multistage) yang memakai aturan Johnson dan diterapkan pada masalah baru, yang diperoleh dari yang asli dengan waktu proses  dan .

Pada Tahap I

                                          =dan  =

Rumus di atas adalah waktu proses pada mesin pertama (M-1) dan mesin terakhir (M-2).

Pada Tahap II

                                                = + dan=+  

Oleh karena itu, aturan Johnson diaplikasikan pada jumlah dari dua mesin yang pertama (first – two) dan dua mesin terakhir (last – two) waktu proses operasi ke i.

Dimana :

       :  Waktu proses pada job ke i dengan menggunakan mesin pertama

       :  Waktu proses pada job ke i dengan menggunakan mesin terakhir

I           :  (Job) produk yang diproses

m         :  Jumlah mesin

K         :  (Stage) tahapan

Untuk tiap tahap k (k = 1,2, ...., m-1), job yang diperoleh dipakai untuk menghitung sebuah make-span untuk masalah yang sesungguhnya. Setelah tahap demi tahap (m-1) dilakukan, maka dapat diketahui make-span terbaik di antara tahap (m-1).

Langkah-langkah penjadwalan produksi dengan metode CDS (Campbell, Dudek and Smith) adalah sebagai berikut ini.

1.      Menyusun matrik n x m dari tij dimana n = jumlah job, m = jumlah mesin, dan tij = waktu pengerjaan job i pada mesin ke j.

2.      Menentukan jumlah urutan (p) untuk n job 2 mesin, dimana p ≤ m-1.

3.      Memulai penjadwalan dengan tahap 1 (k=1)

4.      Menghitung  (M-1) dan  (M-2)

Dimana :  M – 1 =

                M – 2 =

Dengan bantuan algoritma Johnson, n job two mesin, maka dapat ditentukan urutan job.

5.      Jika k ≠ p, maka perhitungan kembali pada langkah ketiga dengan (k+1), jika k = p, maka perhitungan selesai.

6.      Menghitung make-span (total waktu pengerjaan produk terpanjang yang berada dalam suatu sistem).

7.      Memilih urutan penjadwalan yang memiliki make-span terkecil atau waktu penyelesaian maximum (maximum  completion time)

Campbell, Dudek and Smith mencoba algoritma mereka dan menguji performance-nya pada beberapa masalah. Mereka menemukan bahwa algoritma Campbell, Dudek and Smith (CDS) efektif untuk masalah kecil maupun masalah besar.

Contoh Soal :

Perusahaan X memproduksi 5 macam produk dengan menggunakan 4 mesin. Waktu standar yang dibutuhkan untuk menyelesaikan job pada tiap-tiap mesin terdapat pada tabel berikut ini.

Tabel 1. Waktu Standar Proses Pembuatan Produk Untuk Masing-Masing Job

Machine	Job
	1	2	3	4	5
1	31	19	23	13	33
2	41	55	42	22	5
3	25	3	27	14	57
4	30	34	6	13	19

      Carilah urutan jadwal yang optimal dan make-span serta total flow time terkecil dengan menggunakan penjadwalan Campbell, Dudek and Smith!

Penyelesaian :

      P (jumlah urutan proses penjadwalan) = m – 1

                                                                    = 4 – 1

                                                                    = 3

      Jadi, proses penjadwalan CDS dilakukan sebanyak 3 kali dengan memilih salah satu alternatif terbaik dari hasil ke – 3 proses penjadwalan CDS yang dilakukan.

v  Tahap 1 (K = 1)

M – 1 =                                           M – 2 =                                   

M – 1 = M1                                               M – 2 = M4

Tabel 2. Waktu Proses Penjadwalan CDS Stage 1

Machine	Job
	1	2	3	4	5
M-1	31	19	23	13	33
M-2	30	34	6	13	19

Tabel 3. Waktu Standar Proses Pembuatan Produk Untuk Masing-Masing Job

Machine	Job
	1	2	3	4	5
1	31	19	23	13	33
2	41	55	42	22	5
3	25	3	27	14	57
4	30	34	6	13	19

Tabel 4. Hasil Perhitungan Make-span dan Total FlowTime Penjadwalan CDS Stage 1

	Job
	4	2	1	5	3
F1	13	32	63	96	119
F2	35	87	104	101	161
F3	49	90	129	158	188
F4	62	124	159	177	194

Dimana : F (waktu selesainya proses job dikerjakan dengan mesin)

      Urutan Penjadwalan   :  4 – 2 – 1 – 5 – 3  

      Make-span                   :  194 (dari mesin terakhir dan job terakhir)

      Total flow time            :  716 (62 + 124 + 159 + 177 + 194)

v  Tahap 2 (K = 2)

M-1 = M1 + M2                                        M-2 = M3 + M4

Tabel 5. Waktu Proses Penjadwalan CDS Stage 2

Machine	Job
	1	2	3	4	5
M-1	72	74	65	35	38
M-2	55	37	33	27	76

Tabel 6. Waktu Standar Proses Pembuatan Produk Untuk Masing-Masing Job

Machine	Job
	1	2	3	4	5
1	31	19	23	13	33
2	41	55	42	22	5
3	25	3	27	14	57
4	30	34	6	13	19

Tabel 7. Hasil Perhitungan Make-span dan Total FlowTime Penjadwalan CDS Stage 2

	Job
	5	1	2	3	4
F1	33	64	83	106	119
F2	38	105	138	148	141
F3	95	130	141	175	155
F4	114	160	175	181	168

      Urutan Penjadwalan   :  5 – 1 – 2 – 3 – 4

      Make-span                   :  168 (dari mesin terakhir dan job terakhir)

   Total flow time            :  798 (114 + 160 + 175 + 181 + 168)

v  Tahap 3 (K = 3)

M-1 = M1 + M2 + M3                                          M-2 = M2 + M3 + M4

Tabel 8. Waktu Proses Penjadwalan CDS Stage 3

Machine	Job
	1	2	3	4	5
M-1	97	77	92	49	95
M-2	96	92	75	49	81

Tabel 9. Waktu Standar Proses Pembuatan Produk Untuk Masing-Masing Job

Machine	Job
	1	2	3	4	5
1	31	19	23	13	33
2	41	55	42	22	5
3	25	3	27	14	57
4	30	34	6	13	19

Tabel 10. Hasil Perhitungan Make-span dan Total FlowTime Penjadwalan CDS Stage 3

	Job
	4	2	1	5	3
F1	13	32	63	96	119
F2	35	87	104	101	161
F3	49	90	129	158	188
F4	62	124	159	177	194

Dimana : F (waktu selesainya proses job dikerjakan dengan mesin)

      Urutan Penjadwalan   :  4 – 2 – 1 – 5 – 3 

      Make-span                   :  194 (dari mesin terakhir dan job terakhir)

      Total flow time            :  716 (62 + 124 + 159 + 177 + 194)

      Sehingga, dari jadwal-jadwal yang terbentuk, maka urutan jadwal yang paling optimal adalah 4 – 2 – 1 – 5 – 3  dengan make-span 194 dan total flow time 716.