Shortest Processing Time (SPT)

Bukti 1:
SPT meminimumkan Mean Flow Time (t(1) ≤ t(2) ≤ …≤ t(n) )
Terdapat sebuah sekuen S yang bukan merupakan urutan SPT. Di dalam sekuen S tersebut harus ada sepasang job yang saling berdekatan, i dan j, dengan j mengikuti i, dan ti > tj. Kemudian dibuat sebuah sekuen baru, S’, dimana job i dan j saling bertukar tempat dalam sekuen dan semua job lainnya selesai pada waktu yang bersamaan sebagaimana pada sekuen S.

Gambar Pertukaran berpasangan dari 2 job yang berdekatan

tB menunjukkan titik waktu dimana job i dimulai pada sekuen S dan waktu dimana job j dimulai pada sekuen S’. B menunjukkan satu set job yang mendahului job i dan job j pada kedua skeduler, dan A menunjukkan satu set job yang mengikuti i dan j pada kedua skeduler. Digunakan notasi Fk(S) untuk menunjukkan flowtime job k pada skedul S. Kemudian digunakan ∑_(k-1)^n▒F_k sebagai sebuah kriteria, karena berbeda dengan F dalam pembagian oleh sebuah konstanta. Untuk ini akan ditunjukkan bahwa ∑_(k=1)^n▒F_k lebih kecil pada S’ dibandingkan pada S.

Dengan kata lain, pertukaran job i dan j mengurangi nilai dari F. Dengan demikian, sebuah sekuen yang bukan merupakan sekuen SPT dapat diperbaiki dengan memperhitungkan F yang mempertukarkan tempat antara sepasang job yang berdekatan. Sekuen SPT sendiri adalah optimal.
Bukti 2:
SPT meminimumkan Mean Lateness (t(1) ≤ t(2) ≤ …≤ t(n) )
Mean Lateness ditunjukkan pada persamaan berikut:


Dimana d adalah rata-rata dari serangkaian due date yang ditentukan dan bersifat konstan. Karena L berbeda dari F dengan sebuah konstanta sekuen yang independen (d), maka sekuen yang meminimalkan L akan menggantikan sekuen yang meminimalkan F. Sekuen ini dihasilkan dengan menggunakan SPT.