Download - PENJADWALAN MESIN (SCHEDULING)
-
Anggota :Anggun Sri Harmelia (1310932005)Angga Listio (1310931005)Windy Fitri Annisa (1310931058)
*
-
1. Algoritma SPT (Shortest Process Time)Algoritma meminimkan mean flow time pada mesin paralelLangkah 1. Urut semua jobs dengan urutan SPTLangkah 2. Jadwalkan job tersebut satu per satu pada mesin yang memiliki beban minimum. Bila beban mesin sama, pilih sembarang mesin
*Urutan SPT
Sheet1
JobWaktuBobot
proses
1515
2824Makespan = 56
3632
4313
5102548137256
61434.7
7723.5
8313
Job
3326618
143399
18331212
273.571938
22482754
364.66666666671441123
11554646
2551056112
15216412
2727.4666666667
JobBobotWaktuFlow timeWeighted
Flow time
336618
41399
8131212
7271938
2282754
631441123
1154646
521056112
Total15Total216412
Rata-rata2727.4666666667
JobWaktuDue dateSaatLatenesss
Selesaic-d
28108-2
151513-2
3615194
51020299
4325327
61440466
7745538
8350566
Total36
Rata-rata4.5
Sheet2
i13467825Mean FlowWeightedMeanMaximumNo. ofMean
5631473810RuleTimeMean FlowLatenessLatenessTardyTardiness
511142835384656TimeJobs
1515254045501020SPT23,87529-3,6252247,75
-10-4-11-12-10-123636WSPT2727,467-0.536410,625
EDD32317334,5965
Slack32,12531,1334,625965
Hodgson29,12529,8671,6253629
Wilkerson28,87530,6671,3751634
i12345678910
5638723542
Sheet3
MBD00081B50.unknown
MBD00095FDF.unknown
Sheet1
JobWaktuBobot
proses
1515
2824Makespan = 56
3632
4313
5102548137256
61434.7
7723.5
8313
Job
3326618
143399
18331212
273.571938
22482754
364.66666666671441123
11554646
2551056112
15216412
2727.4666666667
JobBobotWaktuFlow timeWeighted
Flow time
336618
41399
8131212
7271938
2282754
631441123
1154646
521056112
Total15Total216412
Rata-rata2727.4666666667
JobWaktuDue dateSaatLatenesss
Selesaic-d
28108-2
151513-2
3615194
51020299
4325327
61440466
7745538
8350566
Total36
Rata-rata4.5
Sheet2
i13467825Mean FlowWeightedMeanMaximumNo. ofMean
5631473810RuleTimeMean FlowLatenessLatenessTardyTardiness
511142835384656TimeJobs
1515254045501020SPT23,87529-3,6252247,75
-10-4-11-12-10-123636WSPT2727,467-0.536410,625
EDD32317334,5965
Slack32,12531,1334,625965
Hodgson29,12529,8671,6253629
Wilkerson28,87530,6671,3751634
i61037918254
2233455678
Sheet3
MBD00081B50.unknown
MBD00095FDF.unknown
-
*M1M2M331529106784Algoritma SPT (Shortest Process Time)Gantt ChartMs=18
Sheet1
JobWaktuBobot
proses
1515
2824Makespan = 56
3632
4313
5102548137256
61434.7
7723.5
8313
Job
3326618
143399
18331212
273.571938
22482754
364.66666666671441123
11554646
2551056112
15216412
2727.4666666667
JobBobotWaktuFlow timeWeighted
Flow time
336618
41399
8131212
7271938
2282754
631441123
1154646
521056112
Total15Total216412
Rata-rata2727.4666666667
JobWaktuDue dateSaatLatenesss
Selesaic-d
28108-2
151513-2
3615194
51020299
4325327
61440466
7745538
8350566
Total36
Rata-rata4.5
Sheet2
i13467825Mean FlowWeightedMeanMaximumNo. ofMean
5631473810RuleTimeMean FlowLatenessLatenessTardyTardiness
511142835384656TimeJobs
1515254045501020SPT23,87529-3,6252247,75
-10-4-11-12-10-123636WSPT2727,467-0.536410,625
EDD32317334,5965
Slack32,12531,1334,625965
Hodgson29,12529,8671,6253629
Wilkerson28,87530,6671,3751634
i61037918254
2233455678
Sheet3
MBD00081B50.unknown
MBD00095FDF.unknown
-
*Makespan (Ms) = 18Rata-rata flow time (Fs) = (8,75+6.67+8.67)/3 = 8,03 M1M2M3Algoritma SPT (Shortest Process Time)
Sheet1
M16784
M21092
M3315
JobWaktuFlow timeJobWaktuFlow timeJobWaktuFlow time
6221022333
735946158
851026125715
4818
Total352026
Rata-rata8.756.66666666678.6666666667
Sheet2
Sheet3
-
Algoritma yang meminimumkan tardiness (positif lateness) pada mesin paralelLangkah 1: Urutkan job berdasarkan aturan slack Langkah 2: Jadwalkan job tersebut satu per satu pada mesin yang memiliki beban minimum. Bila beban mesin sama, pilih sembarang mesin
Urutan yang diperoleh berdasarkan slack adalah 1-2-6-4-5-7-8-10-3-9*
TaskProcessing time tiDue Date diSlack time SLii158326933314114812457114625373858510594151110275
-
*Makespan = 1616123
-
Konsep flowshop: semua job diproses secara berurutan pada beberapa mesin; Urutan pemrosesan n job di seluruh mesin adalah sama, yaitu mulai dari mesin 1 mesin ke-nMasalah: job mana yang harus dijadwalkan terlebih dahuluKriteria: minimasi makespanFlow shop 2 mesin: Algoritma Johnson (1956), optimalFlow shop m mesin: Algoritma Campbell, Dudek dan Smith (CDS)Panjang makespan ditentukan dengan membuat Gantt chart untuk jadwal terpilih: Setiap job hanya diproses di satu mesin pada saat yang sama, dan setiap mesin hanya memproses sebuah job pada saat yang sama *
-
*Alternatif 1Alternatif 2Jika job memiliki waktu proses terkecil di mesin 1, maka job tsb dijadwalkan di awal;Dan jika waktu proses Terkecil ada di mesin 2,Maka job tsb dijadwalkan di akhir;
M1j1j2j3j4M2j1j2j3j4
M1j4j2j3j1M2j4j2j3j1
-
Langkah 1. Tentukan waktu proses yang terpendek di antara seluruh job dalam daftar job yang akan diprosesLangkah 2a. Bila waktu proses terpendek berada di mesin M1, maka jadwalkan job dengan waktu terpendek itu pada posisi paling kiri pada urutan yang dimungkinkan, dan lanjutkan ke Step 3. Langkah 2b. Bila waktu proses terpendek berada di mesin M2, maka jadwalkan job dengan waktu terpendek itu pada posisi paling kanan pada urutan yang dimungkinkan, dan lanjutkan ke Langkah 3.*
-
Langkah 2c. Bila terdapat beberapa nilai waktu proses terpendek, maka pilih sembarang; dan jadwalkan job dengan waktu proses terpilih di posisi paling kiri atau kanan sesuai dengan keberadaan waktu proses terpilih tersebut. Langkah 3. Keluarkan job yang sudah dijadwalkan dari daftar job. Bila masih ada job yang belum dijadwalkan, maka kembali ke Step 1. Bila seluruh job sudah dijadwalkan maka stop.*
-
*Jobtj1tj2Job1Job2Job3Job4Job53516762265Job3Job1Job4Job5Job2314522541324M=24UrutanWaktu tungguM1M2
-
Algoritma Johnson : untuk penggunaan 2 mesin
Algoritma Campbel, Dudek dan Smith (CDS) :Digunakan untuk menyelesaikan n job di m mesin.
*
-
Step 1. Set K=1. Hitung
m = jumlah mesin; K = indeks (pencacah)
Step 2. Gunakan Algoritma Johnson untuk penentuan urutan pekerjaan, yang mana:
*
- Step 3. Hitung makespan untuk urutan tersebut. Catat jadwal dan makespan yang dihasilkanStep 4. Jika K=m-1 maka pilih jadwal dengan makespan terpendek sebagai jadwal yang digunakan, lalu stop. Jika K
-
*Jika jumlah mesin adalah 3 maka untuk K = 1:
Untuk K = 2:
Sheet1
Job iK=1K=2
Mesin 1Mesin 2Mesin 1Mesin 2
1
2
3
4
5
6
Job iMesin 1Mesin 2Mesin 3
1435
2334
3216
4532
5647
6183
Sheet2
Sheet3
-
*Jika jumlah mesin 3 (m=3) maka untuk K = 1 Step 1 :
Step 2 :
Sheet1
Job iK=1K=2
Mesin 1Mesin 2Mesin 1Mesin 2
1
2
3
4
5
6
Job iMesin 1Mesin 2Mesin 3
1435
2334
3216
4532
5647
6183
Sheet2
Sheet3
-
*Jika jumlah mesin 3 (m=3) maka untuk K = 2 Step 1 :
Step 2 :
Sheet1
Job iK=1K=2
Mesin 1Mesin 2Mesin 1Mesin 2
1
2
3
4
5
6
Job iMesin 1Mesin 2Mesin 3
1435
2334
3216
4532
5647
6183
Sheet2
Sheet3
-
*Data Awal:Perhitungan:Untuk K=1
Job iK=1K=2t*i,1t*i,2t*i,1t*i,2145782346732637452855671011613911
Job 1Job 2Job 3Job 4Job 5Job 6t*i,1432561t*i,2546273
Urutan:Job 6Job 3Job 2Job 1Job 5Job 4
Sheet1
Job iK=1K=2
Mesin 1Mesin 2Mesin 1Mesin 2
1
2
3
4
5
6
Job iMesin 1Mesin 2Mesin 3
1435
2334
3216
4532
5647
6183
Sheet2
Sheet3
-
*Urutan pada K = 1 adalah 6-3-2-1-5-4, dan K = 2 adalah 3-2-1-6-5-4
-
Makespan K = 1 adalah 36 jam
Makespan K = 2 adalah 33 jam
Dengan demikian jadwal yang terbaik adalah Jadwal K = 2 dengan urutan 3-2-1-6-5-4*
-
Flow shop: aliran kerja unidirectional; setiap job memiliki routing yang samaJob shop: aliran kerja tidak unidirectional; setiap jaob tidak memilik routing yang sama
*MkIn process jobsIn process jobsNew jobsCompleted jobs
-
Flow shop: Indeks (i, j)*JobM1M2MmJ1J2JnWaktu prosesJob shop: Indeks (i, j, k)Waktu proses job i, operasi ke j untuk pemrosesan di mesin kjoboperasimesintijktij:Waktu proses job i di mesin j
-
*t233 = 4t31=331 =t431
Sheet1
M16784
M21092
M3315
JobWaktuFlow timeJobWaktuFlow timeJobWaktuFlow time
6221022333
735946158
851026125715
4818
Total352026
Rata-rata8.756.66666666678.6666666667
Rata-rata8.0277777778
Makespan18
Waktu ProsesRouting
Operasi 1Operasi 2Operasi 3Operasi 1Operasi 2Operasi 2
Job J1432Job J1123
Job J2144Job J2213
Job J3323Job J3321
Job J4331Job J4231
Sheet2
Sheet3
Sheet1
M16784
M21092
M3315
JobWaktuFlow timeJobWaktuFlow timeJobWaktuFlow time
6221022333
735946158
851026125715
4818
Total352026
Rata-rata8.756.66666666678.6666666667
Rata-rata8.0277777778
Makespan18
Waktu ProsesRouting (Urutan proses)
Operasi 1Operasi 2Operasi 2M1M2M3
Job J1432Job J1123
Job J2144Job J2213
Job J3323Job J3321
Job J4331Job J4231
Sheet2
Sheet3
-
Geser-kiri lokal (local left-shift)Pergeseran (mempercepat) waktu mulai (starting time) suatu operasi tanpa mengubah urutanGese-kiri global (global left-shift)penyesuaian sehingga suatu operasi dimulai lebih cepat tanpa menyebabkan delay operasi lain
*
-
Jadwal semiaktifadalah satu set jadwal yang tidak memungkinkan lagi untuk melakukan geser-kiri lokal adalah satu set jadwal yang tidak memiliki superfluous idle timeSuperfluous idle time terjadi pada jadwal yang apabila suatu operasi dimulai lebih awal tidak menyebabkan perubahan urutan pada mesin manapun
*
-
*M1M2M3Asumsi: urutan job adalah 4-3-2-1 pada setiap mesin:
Sheet1
M16784
M21092
M3315
JobWaktuFlow timeJobWaktuFlow timeJobWaktuFlow time
6221022333
735946158
851026125715
4818
Total352026
Rata-rata8.756.66666666678.6666666667
Rata-rata8.0277777778
Makespan18
Waktu ProsesRouting
Operasi 1Operasi 2Operasi 3Operasi 1Operasi 2Operasi 2
Job J1432Job J1123
Job J2144Job J2213
Job J3323Job J3321
Job J4331Job J4231
Sheet2
Sheet3
Sheet1
M16784
M21092
M3315
JobWaktuFlow timeJobWaktuFlow timeJobWaktuFlow time
6221022333
735946158
851026125715
4818
Total352026
Rata-rata8.756.66666666678.6666666667
Rata-rata8.0277777778
Makespan18
Waktu ProsesRouting
Operasi 1Operasi 2Operasi 2Mesin 1Mesin 2Mesin 3
Job J1432Job J1123
Job J2144Job J2213
Job J3323Job J3321
Job J4331Job J4213
Sheet2
Sheet3
-
*433344222111M1M2M3Geser-kiri lokal tidak bisa dilakukan (menggeser saat mulai tanpa mengubah urutan)Saat mulai operasi (1,1,1) bisa digeser lebih awal tanpa menyebabkan delay pada operasi lain (tapi harus mengubah urutan)111111
************************