Penjadwalan tugas pada mesin tunggal dengan kriteria promptness dan lateness
View/ Open
Date
2000Author
Andarwulan, Lestari
Nurdiati, Sri
Supriyo, Prapto Tri
Metadata
Show full item recordAbstract
Masalah penjadwalan merupakan masalah penentuan urutan barisan tugas yang tidak melanggar setiap aturan yang berlaku dengan memperhatikan kriteria yang digunakan pada masalah tersebut. Sedangkan masalah penjadwalan pada mesin tunggal adalah masalah penjadwalan dengan ketentuan bahwa mesin yang memproses tugas tersebut hanya dapat menangani satu tugas dalam satu waktu.
Misalkan terdapat sejumlah tugas yang akan diproses oleh suatu mesin tunggal. Setiap tugas mempunyai target waktu mulai proses dan target waktu selesai proses. Selain itu, tiap tugas juga mempunyai waktu pemrosesan, yaitu lamanya tugas diproses. Dalam setiap jadwal fisibel yang dihasilkan, terdapat tugas yang mulai diproses sebelum target waktu mulai proses atau selesai diproses setelah target waktu selesai proses. Selisih antara target waktu mulai proses dengan waktu mulai proses yang sebenarnya disebut promptness, sedangkan selisih antara waktu selesai proses yang sesungguhnya dengan waktu selesai proses yang ditargetkan disebut lateness. Promptness dan
lateness digunakan sebagai kriteria yang ditulis dalam fungsi F (Pmaks maks), yaitu fungsi objektif gabungan yang tidak turun di setiap variabelnya. Masalah penjadwalan yang dimaksud dalam tulisan ini adalah masalah penjadwalan pada mesin tunggal yang dapat meminimumkan nilai maksimum promptness dan maksimum lateness secara bersamaan, sehingga jadwal optimal pada masalah ini adalah jadwal fisibel yang meminimumkan
fungsi yang diberikan, yaitu F (Pmakas maks). Masalah tersebut dinotasikan sebagai berikut: Inmit | F(mats, Lats), dengan karakteristik pemrosesan nmit (no machine idle time). Untuk menyelesaikan masalah 1 mit | F (Pmakr, Lmaks) digunakan teori optimal Pareto, yaitu
teori yang digunakan untuk masalah optimasi dengan multi kriteria. Strategi yang digunakan ialah menentukan himpunan titik optimal Pareto (P, L) untuk (Pmake, maks) yang tiap titiknya berhubungan dengan jadwal fisibel tertentu. Langkah awal penentuan titik tersebut ialah mengurutkan tugas berdasarkan aturan MTST (Minimum Target Start Time), sehingga diperoleh nilai P yang pertama. Setelah itu, dengan memperhatikan nilai release date untuk tiap tugasnya, disusun jadwal fisibel yang mempunyai nilai maksimum promptness dan maksimum lateness sebagai titik (P, L) yang pertama. Titik optimal lain, sebut (P', L') diperoleh dengan menukarkan tugas-tugas yang belum terurut berdasarkan aturan EDD (Earliest Due Date), sehingga akan diperoleh nilai P' yang lebih besar dari nilai P sebelumnya. Nilai L' diperoleh dengan cara yang sama dengan cara sebelumnya, yaitu dengan memperhatikan release date tiap tugasnya. Proses penentuan nilai P' terus berulang sampai diperoleh
nilai P' yang sama dengan nilai P sebelumnya.
Banyaknya titik optimal Pareto (P, L) yang diperoleh tidak lebih dari banyaknya tugas yang diproses. Dari himpunan titik (P. L) yang diperoleh, ditentukan titik yang meminimumkan fungsi F(Pmakas Lmaks) Jadwal fisibel yang berhubungan dengan titik yang meminimumkan F (Pmaks, Lmaks) adalah jadwal optimal untuk masalah penjadwalan ini.
Collections
- UT - Mathematics [1408]