Teorema Penjadwalan Mesin Tunggal tanpa Pre-emption

Teorema 2: In the basic single-machine problem, schedules without preemption constitute a dominant set. (Pada kasus mesin tunggal, jadwal tanpa preemsi merupakan suatu set yang dominan)
Bukti:
Untuk memverifikasi bahwa suatu set D adalah sebuah set jadwal yang dominan untuk ukuran performansi reguler, dibutuhkan beberapa persyaratan sebagai berikut:
1. Pertimbangkan sebuah jadwal S (dengan completion time Cj) yang tidak termasuk dalam D.
2. Tunjukkan bahwa terdapat jadwal S’ Є D dimana Cj’ ≤ Cj untuk semua j
3. Dengan demikian maka Z’≤ Z untuk semua ukuran reguler, sehingga S’ sebaik S..
4. Karena itu untuk mencari suatu jadwal yang optimum, maka perlu untuk hanya mempertimbangkan jadwal-jadwal pada D.
Untuk membuktikan teorema ini adalah sebagai berikut:
1. Misal S adalah sebuah jadwal yang memiliki preemsi. Misalnya dengan S tersebut mesin mengalami preemsi untuk beberapa interval {a, b}.
2. Misal S’ adalah jadwal yang identik dengan S melalui waktu a, dan pada semua pemrosesan yang terjadi dalam S setelah waktu b bergerak maju dengan jumlah waktu b – a. Maka setiap job untuk Cj ≤ a pada jadwal S akan memiliki Cj’ = Cj pada jadwal S’. Dan setiap job j dimana Cj > a di bawah jadwal S akan memiliki Cj’ = Cj – (b – a) di bawah jadwal S’. Sehingga Cj’ ≤ Cj untuk semua j.
3. Juga Z’ ≤ Z untuk setiap ukuran performansi reguler Z; sehingga Z mengeluarkan preemsi dan tidak akan menyebabkan performansi yang lebih buruk.
4. Dengan demikian jadwal tanpa preemsi membentuk sebuah set yang dominan.