平成16年度 スケジューリング REVIEW

経営情報学科 専門科目・2年生以上対象
担当：根本 俊男 （研究室：3号館２階3209研究室）
受講生：約80人（教室：6105）
　 　 　
　 今年度の講義は終了しました．お疲れ様でした． 　
　 　 　

実施した講義内容と配布資料

　 　 オリエンテーション 　 　
Keyword 講義概要
　 　

課題への取り組み方

 　
　 　 　 　 　
　 　 日程計画(その1)　スケジュールを図示しよう
　 Keyword 作業とプロジェクト
　 先行作業，作業リスト
　 ガントチャート，フロー・ダイアグラム，アロー・ダイアグラム
　 トポロジカル順
　 　 　 　 　
　

解説記事：スケジューリング(アロー・ダイアグラム)

↑解説記事は研究室で入手できます
　 　 日程計画（その2）　スケジューリングに必要な特性値を求めよう
　 Keyword 最早イベント開始時刻，最遅イベント開始時刻
最早作業開始時刻，最早作業終了時刻
最遅作業開始時刻，最遅作業終了時刻
プロジェクト完了時刻
余裕，自由余裕，全余裕，従属余裕
クリティカルパス，PERT計算表
演習2-7
解説記事： スケジューリング（PERT)
↑解説記事は研究室で入手できます
　 　 日程計画（その3）　スケジュー ルの作成と管理
　 Keyword 最適化問題としてのスケジューリング
クリティカルパス上の作業とそれ以外の作業
労働力を考慮したスケジューリング
山積み表，ロード，最大ロード
山崩し法
演習3-2

解説記事： スケジューリング（クリティカルパス)

↑解説記事は研究室で入手できます
　 　 日程計画（その4）　作業時間が不確定な場合のスケジューリング
　 Keyword 1点見積もり法，3点見積もり法
楽観値，最可能値，悲観値
正規分布，平均，分散，標準偏差
プロジェクト完了時刻の分布の推定
演習4-1
　 　 費用を考慮した日程計画　CPM
Keyword 最小費用日程計画，CPM (Critical Path Method)
カット，最小カット
プロジェクト完了時刻と短縮費用の関係

解説記事： スケジューリング（CPM，その1)

↑解説記事は研究室で入手できます
逆向きの作業を含むカット，再延長が有利な場合

解説記事： スケジューリング（CPM，その2)

↑解説記事は研究室で入手できます
　 　 最適加工順序問題
Keyword 加工順序問題，ガントチャート，順序の総数（階乗）
組合せ的爆発，コンピュータの速度の限界
最適解を求める困難性，最適性の保証
分枝限定法，近似解法
フローショップ，ジョブショップ，オープンショップ
FMSスケジューリング，グループスケジューリング
　 　 アルゴリズムの比較
Keyword 効率の良い解法と悪い解法
アルゴリズムの効率を計る方法：計算量
計算量の比較方法：漸近計算量
最悪計算(時間)量，計算量の下界，計算量の構造
O（オーダー），入力サイズ，RAM
Horner法，ヒープ
演習2-3
　 　 易しい問題・解きにくい問題
Keyword 計算量による問題の難易度の分類
多項式時間アルゴリズム，指数時間アルゴリズム
クラスNP,クラスP，クラスco-NP
決定問題，NP完全問題(NP-complete)， NP困難(NP-hard)
帰着可能性，P=NP?の未解決問題
問題HALT，巡回セールスマン問題（TSP) ，ナップサック問題
集合分割問題
　

　
　 　 期末試験 　
　 　 講義アンケート 　 　
アンケート集計結果
アンケート内容

IE5以上のブラウザの使用を推奨します．
PDFファイル閲覧にはアドビリーダー が必要です．お持ちでない方はこちらをご覧ください。

更新日時: 2005年2月14日