ジョブ到着時刻バースト時間

スケジューリングってなんだ？
－やり方ひとつで大きく変わる
県立広島大学経営情報学部
経営情報学科小川仁士
平成20年8月19日
平成20年度高大連携公開講座
1
目次
1.
スケジューリングとは

2.
製造工場などにおける作業スケジューリング



3.



平成20年8月19日
ガントチャート
PERT（Program Evaluation and Review Technique）
平準化
多重プログラミングにおけるCPUスケジューリング

4.
目的と意義
先着順サービス方式（FCFS）
最短ジョブ優先方式（SJF）
最小残り時間優先方式（SRTF）
巡回スケジューリング方式（RR）
まとめ
平成20年度高大連携公開講座
2
スケジューリングとは

目的と意義
スケジュールを決め、担当者と責任者を明確に
して作業を進める
 多数の作業が複雑に組み合わさって出来上が
る仕事（プロジェクト）に対して、個々の作業が全
体のどの部分に当たるかを明確にし、全体から
見た無駄な部分や効率の悪い部分を改善する
ことができる
 資源や時間を有効に活用することができる

平成20年8月19日
平成20年度高大連携公開講座
3
製造工場などにおける作業スケジューリング

ガントチャート
製造工場における生産スケジュールの時間的な進行を示す方
法
 縦軸に各作業、横軸に時間（または日付）をとり棒グラフで表す
 予定と実績のグラフを上下に並べると、作業の進捗状況が良く
分かる
 作業工程管理以外にも一般のプロジェクト管理にも用いられる

図１．生産工程のガントチャートの例
平成20年8月19日
平成20年度高大連携公開講座
4
製造工場などにおける作業スケジューリング

PERT（Program Evaluation and
Review Technique）





平成20年8月19日
工程計画・管理手法の1つ
仕事（プロジェクト）全体を構成する各作業の相
互依存関係をネットワーク図で示す
各作業の日程計画を作成できる
仕事全体の所要時間が算出できる
クリティカルパスを明らかにして所要時間の短縮
を図ることができる
平成20年度高大連携公開講座
5
製造工場などにおける作業スケジューリング

PERTの大まかな手順
各工程の作業（タスク）を明確にする
2. 各工程が完了するのに必要な所要日数を見積もる
1.

3.
工程の実行順序・工程同士の前後関係を明確にする

4.
平成20年8月19日
アローダイアグラムの作成
仕事全体の所要日数を算出して、完了時期を明らかにする

6.
作業一覧表の作成
各工程をつなぎ合わせ、ネットワーク図を作成する

5.
作業日数の見積もり方法 → 一般に三点見積もりを採用
最早結合点時刻、最遅結合点時刻の算出
クリティカルパスを対象として、所要時間短縮を検討する
 クリティカルパスの発見と対策
平成20年度高大連携公開講座
6
製造工場などにおける作業スケジューリング

作業一覧表

各作業の所要日数と前後関係を明確にした表
表１．作業一覧表の例
平成20年8月19日
平成20年度高大連携公開講座
7
製造工場などにおける作業スケジューリング

アローダイアグラム（作業ネットワーク図）





各作業を矢線で、作業同士の接続点を結合点で示す
各作業の所要日数は矢線上の数値で示す
2つの結合点を結ぶ矢線は1本（1つの作業）に限る
開始点と終了点は、それぞれ1つとする
直接関係しない別の作業の終了時刻に、作業開始時刻を合わせる必
要があるときは、所要日数0のダミー作業（破線で矢線を引く）を入れる
図２．アローダイアグラムの例
平成20年8月19日
平成20年度高大連携公開講座
8
製造工場などにおける作業スケジューリング

最早結合点時刻、最遅結合点時刻の算出



ある結合点に流入する矢線で示される作業が全て完了していなければ、
その結合点から出発する矢線の作業を開始することはできない →
開始点から調べていくことで各結合点の最早結合点時刻が分かる
終了点の最早結合点時刻が仕事全体の完了時刻である
逆に終了点から開始点に向かい、各結合点の遅くとも通過しなければ
ならない時刻を調べていくことで各結合点の最遅結合点時刻が分かる
19
21
0
0
4
4
11
11
26
28
36
36
16
16
10
11
28
28
16
16
上段：最早結合点時刻
下段：最遅結合点時刻
図３．最早／最遅結合点時刻の算出例
平成20年8月19日
平成20年度高大連携公開講座
9
製造工場などにおける作業スケジューリング

クリティカルパスの発見と対策




最遅結合点時刻から最早結合点時刻を引いた値が通過時刻の余裕を示す
余裕が0の結合点を連ねた作業経路をクリティカルパス（隘路）と呼ぶ
クリティカルパス上の作業に遅れが生じれば、完了時刻が確実に遅延することに
なるから、それらの作業は遅れないよう重点管理が必要である
クリティカルパス上の作業の作業時間を短縮できれば、全体の作業時間を短縮
できる（ただし、そうすることによって別の経路がクリティカルパスになる可能性が
高いので、前のステップに戻って再確認することを怠ってはならない）
2
0
0
0
2
0
0
0
1
0
図４．クリティカルパスと作業の余裕の例
平成20年8月19日
平成20年度高大連携公開講座
10
製造工場などにおける作業スケジューリング

平準化



平成20年8月19日
実際の作業を行うにあたっては、各作業に使用する加工
機械や搬送機械、必要な作業員数などを知りそれらを確
保しなければならない
経営的な観点からは、これらの機械や人員の稼働率を高
め、製造コストの上昇が製品の原価に跳ね返ることを極
力避けなければならない
平準化という作業は、PERTで求めた作業ネットワーク上
の日程の余裕を使い、余裕のある作業を意図的に遅くす
るなどして、必要な機械や人員の変動を抑え、稼働率を
高める目的で行う
平成20年度高大連携公開講座
11
製造工場などにおける作業スケジューリング

日程変更前の作業一覧表の例

各作業の作業日、所要日数、余裕日数、作業員数
表２．作業一覧表の例（当初の日程）
平成20年8月19日
平成20年度高大連携公開講座
12
製造工場などにおける作業スケジューリング

ガントチャートと作業員数の山積み表で表すと・・・
稼働率は、
498÷
（23×36）
≒0.5894
図５．ガントチャートと作業員の山積み表の例（当初の日程）
平成20年8月19日
平成20年度高大連携公開講座
13
製造工場などにおける作業スケジューリング

日程変更後の作業一覧表の例

各作業の作業日、所要日数、余裕日数、作業員数
表３．作業一覧表の例（変更後の日程）
平成20年8月19日
平成20年度高大連携公開講座
14
製造工場などにおける作業スケジューリング

ガントチャートと作業員数の山積み表で表すと・・・
稼働率は、
498÷
（18×36）
≒0.7531
図６．ガントチャートと作業員の山積み表の例（変更後の日程）
平成20年8月19日
平成20年度高大連携公開講座
15
多重プログラミングにおけるCPUスケジューリング

多重プログラミングとは？

簡単な計算機システムで二つのジョブA,Bを実行すると・・・
図７．多重プログラミング機構の無い場合のジョブ実行
CPUが使用されている状態（実線部分）と入出力要求などに
よりCPUが使用されていない状態（破線部分）が存在する
 一つのジョブの実行が終了するまで他のジョブの実行が待
たされるのでCPUの使用率が低くなる

平成20年8月19日
平成20年度高大連携公開講座
16
多重プログラミングにおけるCPUスケジューリング

多重プログラミングとは？

一つのジョブが待ち状態のとき、オペレーティングシステム
がCPUをそのジョブから解放して、他のジョブの実行に割り
当てることによりCPUの使用率を高める
図８．多重プログラミング機構の有る場合のジョブ実行
平成20年8月19日
平成20年度高大連携公開講座
17
多重プログラミングにおけるCPUスケジューリング

スケジューラの役割
CPUが実行中のジョブで占有されているとき、実行要求の
あったジョブ（新たに到着したジョブ）を待ち列に加える
 実行中のジョブが終了（もしくは中断）したとき、待ち行列か
ら一つのジョブ選び、CPUを割り当てる
 ジョブのバースト時間（処理時間とほぼ同義と考えてよい）
は長短さまざまで、実行前に完全に予測することは困難で
ある（通常、指数分布で近似されることが多いが・・・）


平成20年8月19日
どのような方法（スケジューリングアルゴリズム）で行うか、
バースト時間の分布が実際にどうなっているかで、計算機シ
ステムの性能が大きく左右される
平成20年度高大連携公開講座
18
多重プログラミングにおけるCPUスケジューリング

CPUスケジューリングアルゴリズムの性能基準






平成20年8月19日
CPU使用率・・・0から100%の範囲、大きいほど良い
スループット・・・単位時間当たりに完了したジョブ数
ターンアラウンド時間・・・ジョブの投入から完了までの間隔
待ち時間・・・ジョブの投入から実行されるまでの待ち時間
応答時間・・・対話型のシステムでは、ユーザが要求を出し
終わってから、最初の応答が返ってくるまでの時間
CPU使用率とスループットを最大にし、ターンアラウンド時間
と待ち時間、および応答時間は最小にすることが望ましいが、
実際には、平均値で考えるのか、最大値あるいは最小値で
考えた方が好ましいのかなど種々の評価が存在する
平成20年度高大連携公開講座
19
多重プログラミングにおけるCPUスケジューリング

先着順サービス方式（FCFS）




実行要求した最初のジョブからCPUに割り当てる方法
実行中のジョブがある場合、待ち列の最後尾に付け加える
実行中のジョブが終了すると、待ち列の先頭のジョブにCPUを割り当てる
ジョブの到着順により平均ターンアラウンド時間が大きく変動する
ジョブ
到着時刻
バースト時間
1
0
24
2
0
3
3
0
3
1,2,3の順
の場合
平均TT：
27
2,3,1の順
の場合
平均TT：
13
図９．FCFS方式：ジョブ到着順による実行結果の違い
平成20年8月19日
平成20年度高大連携公開講座
20
多重プログラミングにおけるCPUスケジューリング

最短ジョブ優先方式（SJF）




バースト時間の短いジョブからCPUに割り当てる方法
実行中のジョブがある場合、待ち列中のバースト時間に応じた場所に挿入する
実行中のジョブが終了すると、待ち列の先頭のジョブにCPUを割り当てる
非常に長いバースト時間を持つジョブが永遠に実行されない可能性がある
ジョブ
到着時刻
バースト時間
1
0
6
2
0
3
3
0
8
4
0
7
平均TT：
13
図１０．SJF方式の実行結果


平成20年8月19日
最小の平均待ち時間を与えることに関しては、SJFはおそらく最適である
ただ、バースト時間を知ることは不可能であり、予測の精度が結果を左右する
平成20年度高大連携公開講座
21
多重プログラミングにおけるCPUスケジューリング

最小残り時間優先方式（SRTF）


バースト時間の短いジョブからCPUに割り当てる方法
SJFとの違いは、実行中のジョブがある場合、実行中のジョブよりバースト時間が短
ければ、実行中のジョブを待ち列中のバースト時間に応じた場所に挿入し、新しく到
着したジョブにCPUを割り当てるところである（CPUの横取りを許す）
ジョブ
到着時刻
バースト時間
1
0
8
2
1
4
3
2
9
4
3
5
平均TT：
13
図１１．SRTF方式の実行結果
※SJF方式では平均TT：14.25
平成20年8月19日
平成20年度高大連携公開講座
22
多重プログラミングにおけるCPUスケジューリング

巡回スケジューリング方式（RR）




待ち列の扱いはFCFSと同じだが、ジョブへのCPUの割り当て方が異なる
量子時間もしくは時間刻み（タイムスライス）と呼ばれる小さな時間単位で、待ち列
内のジョブにCPUを割り当てる
割り当て時間内にジョブが終了したときは、待ち列の先頭のジョブにCPUを割り当
てる
単位時間（タイムスライス）CPUを占有したジョブは実行が中断され、待ち列の最後
尾に付け加えられる
ジョブ
到着時刻
バースト時間
1
0
24
2
0
3
3
0
3
平均TT：
15.67
図１２．RR方式の実行結果（タイムスライス=4）


平成20年8月19日
量子時間が短すぎるとジョブの切り替えが頻繁に起こり、効率が落ちる
量子時間が長すぎるとFCFSに近くなる
平成20年度高大連携公開講座
23
多重プログラミングにおけるCPUスケジューリング

各種スケジューリングアルゴリズムの実行結果を調
べてみよう！
以下のジョブ列をプログラムでシミュレートする
ジョブ
到着時刻
バースト時間
A
0
2
B
1
10
C
3
7
D
5
3
 ただし、RR方式のタイムスライスは2とする

平成20年8月19日
平成20年度高大連携公開講座
24
まとめ
スケジューリングの基本概念
 製造工場などにおける作業スケジューリングの各手法

多重プログラミングにおけるCPUスケジューリングの各手法
＜講師からのメッセージ＞

大学ではまず基本原理を教わり、




平成20年8月19日
それを足場に新たな原理を探求したり、
実社会の現象に当てはめ応用するための具体的な方法論を模索し
ます
何事にも興味を持ち、積極的に調べ活用する姿勢を身に着けま
しょう
平成20年度高大連携公開講座
25

Download Report