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.