2. CONCEPT OF SINGLE MACHINE SCHEDULING

2. CONCEPT OF SINGLE MACHINE SCHEDULING

Single machine scheduling problem pada dasarnya dalam karakter dengan kondisi sebagai berikut :

1. Satu set mesin yang independen, single-operation jobs yang siap pakai pada time zero (awal jam kerja).
2. Set up time setiap job adalah independen (bebas tidak tergantung proses lain) di posisinya dalam job sequence-nya. Jadi, waktu set-up time dari setiap job ikut masuk ke processing time-nya.
3. Deskripsi Job diketahui/dibuat lebih dulu di awal.
4. Satu mesin selalu siap dan tidak pernah menganggur atau menunggu 
5. Tiap job diproses sampai selesai tanpa jeda.

Dengan kondisi tersebut, orang dapat melihat korespondensi satu-satu antara urutan pekerjaan n dan permutasi dari indeks pekerjaan 1 2, ... n. Total jumlah urutan dalam basic single machine problem adalah n! yang merupakan jumlah perberbedaan dari permutasi n elemen. Berikut ini adalah tiga data dasar yang diperlukan untuk menggambarkan job dalam suatu problem scheduling mesin tunggal yang deterministic (deterministic single machine-scheduling problem).

Processing time (tj) : Waktu proses yang diperlukan untuk memproses job j. Waktu proses, tj biasanya akan mencakup processing time and set-up time.
Ready time (rj) : Waktu siap ini adalah waktu di mana job j yang siap diproses. Ready time untuk suatu pekerjaan adalah selisih antara waktu kedatangan pekerjaan itu dengan waktu di saat pekerjaan diambil masuk proses. Pada dasarnya, untuk setiap kondisi I, rj = 0 untuk semua job. 

Due date(dj) : Tanggal jatuh tempo ini adalah waktu di mana job j akan selesai.
Completion time (Cj) : Waktu penyelesaian  ini adalah waktu di mana job j selesai secara berurutan. Ukuran kinerja untuk mengevaluasi jadwal biasanya adalah fungsi Completion time . Beberapa, sampel ukuran kinerja adalah Flow time, Lateness, Tardiness,dll.
Flow time (Fj) : Waktu alir ini adalah jumlah waktu job j yang ditempuh dalam sistem. Waktu alir adalah ukuran, yang menunjukkan waktu tunggu job dalam suatu sistem. Hal ini pada gilirannya memberikan beberapa masukan tentang in-process inventory. Ini adalah selisih antara Completion time dan Ready time dari job j. yaitu Fj = Cj - rj.
Lateness  (Lj) : Keterlambatan ini adalah jumlah waktu dimana completion time job j berbeda dari tanggal jatuh tempo (Lj = Cj - d). Lateness adalah ukuran yang memberikan gambaran tentang kesesuaian job dalam schedule terhadap tanggal jatuh tempo atas job. Lateness dapat berupa positive lateness atau negative lateness. positive lateness dari job berarti pekerjaan selesai setelah jatuh tempo. Negative lateness dari job berarti pekerjaan selesai sebelum jatuh tempo. Positive lateness adalah ukuran layanan yang jelek. Negative latenessa dalah ukuran pelayanan yang baik. Dalam banyak hal, pinalty dan cost lainnya terkait dengan positive lateness, tetapi umumnya tidak ada benefit terkait dengan negative lateness. Oleh karena itu, diharapkan positive lateness saja yang dioptimalkan.
Tardiness (Tj): Tardiness adalah lateness job j jika gagal memenuhi tanggal jatuh tempo-nya, atau nol, jika
             Tj = max {O, Cj - dj}
                 = Max {O, Lj}.