「Shortest Job First(SJF)」は、OSのプロセススケジューリング用アルゴリズムの一つ
ですが、
意外と実生活にも活用可能かも?というお話です。
まず、ジョブを一つづつしか処理できないマシンに対して、処理完了時間が、
60分のジョブA、3分のジョブB、30分のジョブC、1分のジョブD の4つが
ほぼ同時に到着したとします。(なおI/O時間等は無視)
これらを上記の順番で処理したとすると、
60 + 3 + 30 + 1 =
94分後にすべての処理を終えることになります。
短いジョブ優先の
SJF方式(D,B,C,Aの順)で処理したとしても、
1 + 3 + 30 + 60 =
94分後にすべての処理を終えることになり、その点までは
全く一緒です。
このとき、
各ジョブ開始までの平均待ち時間を考えて見ます。
最初の処理方式では、
ジョブA = 0分
ジョブB = 60分(60)
ジョブC = 63分(60+3)
ジョブD = 93分(60+3+30)
となり、(0+60+63+93)/4 =
54分が平均待ち時間となります。
それに対し、
SJF方式では、
ジョブD = 0分
ジョブB = 1分(1)
ジョブC = 4分(1+3)
ジョブA = 34分(1+3+30)
となり、(0+1+4+34)/4 =
9.75分が平均待ち時間となります。
ということで、
SJF を使うと、全体の平均待ち時間が大きく改善することがわかります。
(なお、平均処理完了時間で比較しても、前者77分、後者33分となり、大きく改善します)
さて、これを
日常生活に応用すると、
「
お客さんや他のメンバが、受付開始や処理完了を待っているような仕事については、 (入れ替え可能な仕事の場合は)早く終わりそうなものから処理すると、平均の お待たせ時間を最小にしやすい」という話になります。
(ただし、待たせる時間平均を最小にすることが、そのまま
顧客満足度の合計を最大 にすることに等しいとは限らないので、念のため)
余談ですが、個人的には、病院などの待ち行列で病院側に活用してほしいアルゴリズム
だったりします。
補足ですが、大昔のバッチ処理全盛の時代とOSと違い、今時のOSでは
「ジョブ開始時に処理完了時間が判明しないこと」「プリエンプティブ・マルチタスクであること」という2点から、素のままの SJF を採用している例は、たぶん無いと思います。
わかりやすい図があったので載せておきます。
https://scalingsoftwareagility.wordpress.com/2010/04/08/prioritizing-features/