7. MINIMIZING THE NUMBER OF TARDY JOBS

7. MINIMIZING THE NUMBER OF TARDY JOBS

Jika job selesai melampaui tanggal jatuh tempo, maka disebut tardy job, lainnya disebut non-tardy job. Di banyak organisasi, punya tujuan untuk meminimalkan jumlah tardy job.

Jika hasil urutan EDD nol tardy, atau menghasilkan tepat hanya satu tardy job, maka itu adalah urutan yang optimal untuk meminimalkan jumlah tardy job (NT), Jika menghasilkan lebih dari satu tardy job, urutan EDD tidak mungkin menghasilkan solusi optimal. Di bawah ini adalah sebuah algoritma yang tepat untuk kasus yang sifatnya umum.The final sequence consists of two streams of jobs as given below:
(a) First, a set (E) of early jobs, in EDD order.
(b) Then, a set (L) of late jobs, in any order.
This algorithm gives optimal sequence, which will result in minimum number of tardy jobs (NT).
Urutan final terdiri dari dua aliran job sebagai berikut :
(a) Pertama, satu set (E) job awal, dalam rangka EDD.
(b) Kemudian, satu set (L) job akhir, dalam urutan apapun.
Algoritma ini memberikan urutan yang optimal, yang menghasilkan jumlah minimum tardy job (NT).

HODGSON’S ALGORITHM TO MINIMIZE NT

Langkah 1 : Atur job dalam urutan EDD dan asumsikan ini, sebagai set E. Biarkan L tetap kosong.

Step 2: If no jobs in E are late, then stop. Find the union of E and L (Note: The remaining jobs in E should be in EDD order. But the jobs in L can be in any order); otherwise, identify the first late job in E. Let it be job K.
Langkah 2 : Jika tidak ada job di E yang terlambat, berhentilah. Temukan gabungan E dan L (Catatan: job yang tersisa di E harus dalam urutan EDD. Tetapi job di L bisa dalam urutan apapun.), jika tidak, identifikasikan job terlambat yang pertama di E. Biarlah job K.
Langkah 3 : Identifikasi job terpanjang, antara job K pertama dalam urutan. Hapus pekerjaan ini dari E dan tempatkan di L. Revisi waktu penyelesaian job yang tersisa di E dan kembali, ke Langkah 2.
Algoritma ini ditunjukkan dengan contoh soal sebagai berikut.

ILUSTRASI 4 Sebuah sistem komputer milik sebuah perusahaan konsultan di kontrak untuk melaksanakan tujuh proyek, semua dengan deadliness yang kan dipastikan dalam beberapa hari ini. Para konsultan ini adalah kelompok kecil dan mereka bekerja sama dalam setiap proyek, sehingga proyek akan dimulai dan diselesaikan secara berurutan. Menurut ketentuan kontrak, konsultan akan menerima Rp. 4.000.0000 untuk setiap proyek selesai tepat waktu, tetapi mereka akan dikenakan denda Rs. 8.000.000 di  untuk setiap proyek terlambat. Setiap proyek memiliki durasi, yang merupakan jumlah hari sudah diantisipasi yang dibutuhkan untuk melaksanakan proyek seperti yang ditunjukkan di bawah ini.

Bagaimana seharusnya proyek akan diurutkan dalam rangka untuk memaksimalkan pendapatan bersih?

SOLUSI : Dari pernyataan masalah, dapat mengidentifikasi bahwa tujuannya adalah untuk memaksimalkan pendapatan bersih. Hal ini dapat dicapai dengan hanya mendapatkan urutan, yang akan meminimalkan jumlah tardy job (NT), karena itu, kami menerapkan algoritma Hodgson untuk meminimalkan NT.
Langkah 1: Urutan earliest due date order ditunjukkan di bawah ini:

Tempatkan urutan proyek-proyek di atas yang ada dalam order  EDD di set E. Maka,
Set E = (1, 2, 5, 6, 4, 7,3)
Set L = (Kosong).
Langkah 2 : Lateness proyek diperiksa seperti yang ditunjukkan di bawah ini:

Dalam tabel di atas, pada baris terakhir, 0 berarti bahwa proyek adalah non-lambat dan 1 berarti bahwa proyek ini tardy.
Sesuai urutan di set E, ada lima proyek tardy. Proyek tardy pertama adalah 5, yang berada di posisi ketiga [3].

Langkah 3 : Proyek dengan durasi terlama di antara proyek pertama-tiga dalam urutan adalah 5.
Hapus proyek ini dan pindahkan ke set L. Maka

L = {5}
E = {1, 2, 6, 4, 7, 3}.
Waktu penyelesaian proyek-proyek di E set direvisi seperti yang ditunjukkan di bawah ini:

Langkah 2 : Dari Langkah 3, jelas bahwa ada tiga tardy proyek. Tardy Proyek pertama adalah 4, yang berada di posisi keempat dari urutan di set E.

Langkah 3 : Proyek dengan durasi terpanjang di antara yang proyek pertama-empat adalah 6. Hapus
Proyek-6 dari E set dan pindahkan ke set L. Maka
E = {1, 2, 4, 7, 3}
L = {5, 6}.
Waktu penyelesaian proyek-proyek di E set direvisi ditunjukkan dibawah ini :

Langkah 2 : Dari tabel pada Langkah 3 diketahui bahwa ada dua tardy proyek. Tardy proyek pertama adalah 7, yang berada di posisi keempat di set E.

Langkah 3 : Proyek dengan durasi terpanjang. Di antara proyek yang pertama-empat proyek di set E adalah 7.
Hapus pekerjaan ini dari E set dan pindahkan ke L. set
E = {1, 2, 4, 3}
L = {5, 6, 7}.
Waktu penyelesaian dari proyek yang direvisi seperti yang ditunjukkan di bawah ini :

Langkah 2 : Dari tabel di langkah sebelumnya, jelas bahwa semua proyek adalah non-tardy job.
Oleh karena itu, kita mencapai urutan optimal dalam E.
Sekarang gabungkan E dan L untuk mendapatkan urutan lengkap.

Dalam urutan yang optimal di atas, jumlah tardy proyek  adalah 3, yang merupakan nilai minimum.