14. PRIORITY DISPATCHING RULES

14. PRIORITY DISPATCHING RULES

Dalam prosedur lengkap enumeration (pencacahan) atau prosedur bercabang dan terikat, jumlah schedule yang dihasilkan sebelum mencapai jadwal yang optimal akan sangat banyak. Namun, tujuan prosedur heuristik pada dasarnya hanya menghasilkan satu jadwal penuh.

Setiap kali, ada sebuah hubungan (konflik) dalam menyeleksi operasi dari antara operasi yang berlawanan, kita harus menggunakan aturan prioritas. Jika ada hubungan pada tingkat yang berbeda, maka kita perlu lebih dari satu aturan prioritas untuk memecahkan keruwetan yang kusut. Untuk R prioritas aturan, satu heuristik didasarkan pada pembentukan jadwal aktif diberikan di bawah ini:
Heuristic Active Schedule Generation 
Langkah 1 :  t = 0 dan assumsikan Pt = {φ}.
St = {Semua operasi tanpa proses pendahuluan/predecessor}.
Langkah 2 : Tentukan q* = min {qj} dan
                     mesin terkait m* yang q* direalisaikan.
                     j E S.

Langkah 3 :Setiap operasi kepunyaan S, yang membutuhkan mesin * m dan memenuhi kondisi Pj <q *, menjadi identifikasi bagi operasi dengan prioritas tertentu dan tambahkan operasi ini ke PI sedini mungkin, sehingga menciptakan hanya satu jadwal parsial, PI + 1 untuk tahap berikutnya.

Langkah 4 : Setiap jadwal parsial PI yang baru + 1 yang dibuat pada Langkah 3, update set data sbb :
(a) Hapus j operasi dari SI.
(b) Bentuklah SI + I dengan menambahkan successor/penerus langsung j operasi untuk SI.
(c) Increment t tiap satu.
Langkah 5 : Ulangi Langkah 2 ke Langkah 4 untuk setiap PI + 1 yang dibuat pada Langkah 3 dan lanjutkan dengan cara ini sampai semua jadwal aktif bisa dihasilkan.

Demikian pula, heuristik lainnya dapat dibuat dari algoritma pembuatan non-delay schedule dengan mengganti kondisi Pj <q * dengan Pj = p * pada Langkah 3. Dua algoritma heuristik ini (active dispatching dan non-delay dispatching) dapat membangun jadwal yang berbeda. Kualitas dari solusi yang diperoleh oleh heuristik ini terutama tergantung pada efektivitas aturan prioritas yang digunakan di dalamnya.

Contoh set aturan prioritas disajikan di bawah ini:
(a) SPT, shortest processing time (waktu pemrosesan terpendek) :
     Pilih operasi dengan processing time yang minimum.
(b) FCFS, first come first served (pertama datang pertama dilayani) :
     Pilih operasi yang masuk SI paling awal.
(c) MWKR, most work remaining (pekerjaan yang paling tersisa) :
     Pilih operasi dengan job dengan pekerjaan yang paling banyak tersisa untuk diproses.

(d) MOPNR, most operations remaining (operasi yang paling tersisa) :
     Pilih operasi yang memiliki jumlah operasi successor/penerus terbesar.
(e) LWKR, least work remaining (pekerjaan paling yang tersisa) :
     Pilih operasi dengan job dengan pekerjaan yang paling sedikit tersisa untuk diproses.
(f) RANDOM (Acak) :
    Pilih operasi secara acak.