スケジューリングってなんだ？ －やり方ひとつで大きく変わる

Presentation on theme: "スケジューリングってなんだ？ －やり方ひとつで大きく変わる"— Presentation transcript:

1 スケジューリングってなんだ？ －やり方ひとつで大きく変わる
スケジューリングってなんだ？ 　－やり方ひとつで大きく変わる 県立広島大学　経営情報学部 経営情報学科　小川仁士 平成20年8月19日 平成20年度　高大連携公開講座

2 目次 スケジューリングとは 製造工場などにおける作業スケジューリング 多重プログラミングにおけるCPUスケジューリング まとめ 目的と意義
ガントチャート PERT（Program Evaluation and Review Technique） 平準化 多重プログラミングにおけるCPUスケジューリング 先着順サービス方式（FCFS） 最短ジョブ優先方式（SJF） 最小残り時間優先方式（SRTF） 巡回スケジューリング方式（RR） まとめ 平成20年8月19日 平成20年度　高大連携公開講座

3 スケジューリングとは 目的と意義 スケジュールを決め、担当者と責任者を明確にして作業を進める
多数の作業が複雑に組み合わさって出来上がる仕事（プロジェクト）に対して、個々の作業が全体のどの部分に当たるかを明確にし、全体から見た無駄な部分や効率の悪い部分を改善することができる 資源や時間を有効に活用することができる 平成20年8月19日 平成20年度　高大連携公開講座

4 製造工場などにおける作業スケジューリング
ガントチャート 製造工場における生産スケジュールの時間的な進行を示す方法 縦軸に各作業、横軸に時間（または日付）をとり棒グラフで表す 予定と実績のグラフを上下に並べると、作業の進捗状況が良く分かる 作業工程管理以外にも一般のプロジェクト管理にも用いられる 図１．生産工程のガントチャートの例 平成20年8月19日 平成20年度　高大連携公開講座

5 製造工場などにおける作業スケジューリング
PERT（Program Evaluation and Review Technique） 工程計画・管理手法の1つ 仕事（プロジェクト）全体を構成する各作業の相互依存関係をネットワーク図で示す 各作業の日程計画を作成できる 仕事全体の所要時間が算出できる クリティカルパスを明らかにして所要時間の短縮を図ることができる 平成20年8月19日 平成20年度　高大連携公開講座

6 製造工場などにおける作業スケジューリング
PERTの大まかな手順 各工程の作業（タスク）を明確にする 各工程が完了するのに必要な所要日数を見積もる 作業日数の見積もり方法　→　一般に三点見積もりを採用 工程の実行順序・工程同士の前後関係を明確にする 作業一覧表の作成 各工程をつなぎ合わせ、ネットワーク図を作成する アローダイアグラムの作成 仕事全体の所要日数を算出して、完了時期を明らかにする 最早結合点時刻、最遅結合点時刻の算出 クリティカルパスを対象として、所要時間短縮を検討する クリティカルパスの発見と対策 平成20年8月19日 平成20年度　高大連携公開講座

7 製造工場などにおける作業スケジューリング
作業一覧表 各作業の所要日数と前後関係を明確にした表 表１．作業一覧表の例 平成20年8月19日 平成20年度　高大連携公開講座

8 製造工場などにおける作業スケジューリング
アローダイアグラム（作業ネットワーク図） 各作業を矢線で、作業同士の接続点を結合点で示す 各作業の所要日数は矢線上の数値で示す 2つの結合点を結ぶ矢線は1本（1つの作業）に限る 開始点と終了点は、それぞれ1つとする 直接関係しない別の作業の終了時刻に、作業開始時刻を合わせる必要があるときは、所要日数0のダミー作業（破線で矢線を引く）を入れる 図２．アローダイアグラムの例 平成20年8月19日 平成20年度　高大連携公開講座

9 製造工場などにおける作業スケジューリング
最早結合点時刻、最遅結合点時刻の算出 ある結合点に流入する矢線で示される作業が全て完了していなければ、その結合点から出発する矢線の作業を開始することはできない　→　開始点から調べていくことで各結合点の最早結合点時刻が分かる 終了点の最早結合点時刻が仕事全体の完了時刻である 逆に終了点から開始点に向かい、各結合点の遅くとも通過しなければならない時刻を調べていくことで各結合点の最遅結合点時刻が分かる 図３．最早／最遅結合点時刻の算出例 4 11 10 19 21 16 28 26 36 上段：最早結合点時刻 下段：最遅結合点時刻 平成20年8月19日 平成20年度　高大連携公開講座

10 製造工場などにおける作業スケジューリング
クリティカルパスの発見と対策 最遅結合点時刻から最早結合点時刻を引いた値が通過時刻の余裕を示す 余裕が0の結合点を連ねた作業経路をクリティカルパス（隘路）と呼ぶ クリティカルパス上の作業に遅れが生じれば、完了時刻が確実に遅延することになるから、それらの作業は遅れないよう重点管理が必要である クリティカルパス上の作業の作業時間を短縮できれば、全体の作業時間を短縮できる（ただし、そうすることによって別の経路がクリティカルパスになる可能性が高いので、前のステップに戻って再確認することを怠ってはならない） 図４．クリティカルパスと作業の余裕の例 1 2 平成20年8月19日 平成20年度　高大連携公開講座

11 製造工場などにおける作業スケジューリング
平準化 実際の作業を行うにあたっては、各作業に使用する加工機械や搬送機械、必要な作業員数などを知りそれらを確保しなければならない 経営的な観点からは、これらの機械や人員の稼働率を高め、製造コストの上昇が製品の原価に跳ね返ることを極力避けなければならない 平準化という作業は、PERTで求めた作業ネットワーク上の日程の余裕を使い、余裕のある作業を意図的に遅くするなどして、必要な機械や人員の変動を抑え、稼働率を高める目的で行う 平成20年8月19日 平成20年度　高大連携公開講座

12 製造工場などにおける作業スケジューリング
日程変更前の作業一覧表の例 各作業の作業日、所要日数、余裕日数、作業員数 表２．作業一覧表の例（当初の日程） 平成20年8月19日 平成20年度　高大連携公開講座

13 製造工場などにおける作業スケジューリング
ガントチャートと作業員数の山積み表で表すと・・・ 図５．ガントチャートと作業員の山積み表の例（当初の日程） 稼働率は、 498÷（23×36）≒0.5894 平成20年8月19日 平成20年度　高大連携公開講座

14 製造工場などにおける作業スケジューリング
日程変更後の作業一覧表の例 各作業の作業日、所要日数、余裕日数、作業員数 表３．作業一覧表の例（変更後の日程） 平成20年8月19日 平成20年度　高大連携公開講座

15 製造工場などにおける作業スケジューリング
ガントチャートと作業員数の山積み表で表すと・・・ 図６．ガントチャートと作業員の山積み表の例（変更後の日程） 稼働率は、 498÷（18×36）≒0.7531 平成20年8月19日 平成20年度　高大連携公開講座

16 多重プログラミングにおけるCPUスケジューリング
多重プログラミングとは？ 簡単な計算機システムで二つのジョブA,Bを実行すると・・・ 図７．多重プログラミング機構の無い場合のジョブ実行 CPUが使用されている状態（実線部分）と入出力要求などによりCPUが使用されていない状態（破線部分）が存在する 一つのジョブの実行が終了するまで他のジョブの実行が待たされるのでCPUの使用率が低くなる 平成20年8月19日 平成20年度　高大連携公開講座

17 多重プログラミングにおけるCPUスケジューリング
多重プログラミングとは？ 一つのジョブが待ち状態のとき、オペレーティングシステムがCPUをそのジョブから解放して、他のジョブの実行に割り当てることによりCPUの使用率を高める 図８．多重プログラミング機構の有る場合のジョブ実行 平成20年8月19日 平成20年度　高大連携公開講座

18 多重プログラミングにおけるCPUスケジューリング
スケジューラの役割 CPUが実行中のジョブで占有されているとき、実行要求のあったジョブ（新たに到着したジョブ）を待ち列に加える 実行中のジョブが終了（もしくは中断）したとき、待ち行列から一つのジョブ選び、CPUを割り当てる ジョブのバースト時間（処理時間とほぼ同義と考えてよい）は長短さまざまで、実行前に完全に予測することは困難である（通常、指数分布で近似されることが多いが・・・） どのような方法（スケジューリングアルゴリズム）で行うか、バースト時間の分布が実際にどうなっているかで、計算機システムの性能が大きく左右される 平成20年8月19日 平成20年度　高大連携公開講座

19 多重プログラミングにおけるCPUスケジューリング
スループット・・・単位時間当たりに完了したジョブ数 ターンアラウンド時間・・・ジョブの投入から完了までの間隔 待ち時間・・・ジョブの投入から実行されるまでの待ち時間 応答時間・・・対話型のシステムでは、ユーザが要求を出し 終わってから、最初の応答が返ってくるまでの時間 CPU使用率とスループットを最大にし、ターンアラウンド時間と待ち時間、および応答時間は最小にすることが望ましいが、実際には、平均値で考えるのか、最大値あるいは最小値で考えた方が好ましいのかなど種々の評価が存在する 平成20年8月19日 平成20年度　高大連携公開講座

20 多重プログラミングにおけるCPUスケジューリング
先着順サービス方式（FCFS） 実行要求した最初のジョブからCPUに割り当てる方法 実行中のジョブがある場合、待ち列の最後尾に付け加える 実行中のジョブが終了すると、待ち列の先頭のジョブにCPUを割り当てる ジョブの到着順により平均ターンアラウンド時間が大きく変動する ジョブ　　　　到着時刻　　　バースト時間 1　　　　　　　　0　　　　　　　　　24 2　　　　　　　　0　　　　　　　　　　3 3　　　　　　　　0　　　　　　　　　　3 図９．FCFS方式：ジョブ到着順による実行結果の違い 1,2,3の順の場合 2,3,1の順の場合 平均TT： 27 13 平成20年8月19日 平成20年度　高大連携公開講座

21 多重プログラミングにおけるCPUスケジューリング
最短ジョブ優先方式（SJF） バースト時間の短いジョブからCPUに割り当てる方法 実行中のジョブがある場合、待ち列中のバースト時間に応じた場所に挿入する 実行中のジョブが終了すると、待ち列の先頭のジョブにCPUを割り当てる 非常に長いバースト時間を持つジョブが永遠に実行されない可能性がある ジョブ　　　　到着時刻　　　バースト時間 1　　　　　　　　0　　　　　　　　　　6 2　　　　　　　　0　　　　　　　　　　3 3　　　　　　　　0　　　　　　　　　　8 4　　　　　　　　0　　　　　　　　　　7 最小の平均待ち時間を与えることに関しては、SJFはおそらく最適である ただ、バースト時間を知ることは不可能であり、予測の精度が結果を左右する 図１０．SJF方式の実行結果 平均TT： 13 平成20年8月19日 平成20年度　高大連携公開講座

22 多重プログラミングにおけるCPUスケジューリング
最小残り時間優先方式（SRTF） バースト時間の短いジョブからCPUに割り当てる方法 SJFとの違いは、実行中のジョブがある場合、実行中のジョブよりバースト時間が短ければ、実行中のジョブを待ち列中のバースト時間に応じた場所に挿入し、新しく到着したジョブにCPUを割り当てるところである（CPUの横取りを許す） ジョブ　　　　到着時刻　　　バースト時間 1　　　　　　　　0　　　　　　　　　　8 2　　　　　　　　1　　　　　　　　　　4 3　　　　　　　　2　　　　　　　　　　9 4　　　　　　　　3　　　　　　　　　　5 図１１．SRTF方式の実行結果 平均TT： 13 ※SJF方式では平均TT：14.25 平成20年8月19日 平成20年度　高大連携公開講座

23 多重プログラミングにおけるCPUスケジューリング
巡回スケジューリング方式（RR） 待ち列の扱いはFCFSと同じだが、ジョブへのCPUの割り当て方が異なる 量子時間もしくは時間刻み（タイムスライス）と呼ばれる小さな時間単位で、待ち列内のジョブにCPUを割り当てる 割り当て時間内にジョブが終了したときは、待ち列の先頭のジョブにCPUを割り当てる 単位時間（タイムスライス）CPUを占有したジョブは実行が中断され、待ち列の最後尾に付け加えられる ジョブ　　　　到着時刻　　　バースト時間 1　　　　　　　　0　　　　　　　　　24 2　　　　　　　　0　　　　　　　　　　3 3　　　　　　　　0　　　　　　　　　　3 量子時間が短すぎるとジョブの切り替えが頻繁に起こり、効率が落ちる 量子時間が長すぎるとFCFSに近くなる 図１２．RR方式の実行結果（タイムスライス=4） 平均TT： 15.67 平成20年8月19日 平成20年度　高大連携公開講座

24 多重プログラミングにおけるCPUスケジューリング
各種スケジューリングアルゴリズムの実行結果を調べてみよう！ 以下のジョブ列をプログラムでシミュレートする ジョブ　　　　到着時刻　　　バースト時間 A　　　　　　　　0　　　　　　　　　　2 B　　　　　　　　1　　　　　　　　　10 C　　　　　　　　3　　　　　　　　　　7 D　　　　　　　　5　　　　　　　　　　3 ただし、RR方式のタイムスライスは2とする 平成20年8月19日 平成20年度　高大連携公開講座

25 まとめ スケジューリングの基本概念 製造工場などにおける作業スケジューリングの各手法
多重プログラミングにおけるCPUスケジューリングの各手法 ＜講師からのメッセージ＞ 大学ではまず基本原理を教わり、 それを足場に新たな原理を探求したり、 実社会の現象に当てはめ応用するための具体的な方法論を模索します 何事にも興味を持ち、積極的に調べ活用する姿勢を身に着けましょう 平成20年8月19日 平成20年度　高大連携公開講座