理工学部Faculty of Science and Engineering
PRI300XF（情報学基礎 / Principles of informatics 300）スケジューリング論Scheduling Theory
千葉 英史Eishi CHIBA
授業コードなどClass code etc
| 学部・研究科Faculty/Graduate school | 理工学部Faculty of Science and Engineering |
| 添付ファイル名Attached documents | |
| 年度Year | 2021 |
| 授業コードClass code | H6553 |
| 旧授業コードPrevious Class code | |
| 旧科目名Previous Class title | |
| 開講時期Term | 秋学期授業/Fall |
| 曜日・時限Day/Period | 水4/Wed.4 |
| 科目種別Class Type | |
| キャンパスCampus | 小金井 |
| 教室名称Classroom name | |
| 配当年次Grade | |
| 単位数Credit(s) | |
| 備考（履修条件等）Notes | |
| 他学部公開科目Open Program | |
| 他学部公開（履修条件等）Open Program (Notes) | |
| グローバル・オープン科目Global Open Program | |
| 成績優秀者の他学部科目履修制度対象Interdepartmental class taking system for Academic Achievers | |
| 成績優秀者の他学部科目履修（履修条件等）Interdepartmental class taking system for Academic Achievers (Notes) | |
| 実務経験のある教員による授業科目Class taught by instructors with practical experience | |
| SDGsCPSDGs CP | |
| アーバンデザインCPUrban Design CP | |
| ダイバーシティCPDiversity CP | |
| 未来教室CPLearning for the Future CP | |
| カーボンニュートラルCPCarbon Neutral CP | |
| 千代田コンソ単位互換提供（他大学向け）Chiyoda Campus Consortium | |
| カテゴリー＜理工学部＞Category |
経営システム工学科 学科専門科目 |
すべて開くShow all
すべて閉じるHide All
Outline (in English)
In order to compute a schedule which efficiently processes given jobs, we learn scheduling theory and scheduling algorithms.
授業で使用する言語Default language used in class
日本語 / Japanese
授業の概要と目的（何を学ぶか）Outline and objectives
限られた資源を利用して，与えられた仕事を効率良く処理するスケジュールを求めるために，スケジューリングの理論とスケジューリングアルゴリズムを学ぶ．
到達目標Goal
目標は，スケジューリング問題の定式化，定式化した問題に対する解法，それらの解法を効率的に実行するアルゴリズム，それらのアルゴリズムを実際にプログラミングするためのデータ構造を理解して利用できるようになることである．
この授業を履修することで学部等のディプロマポリシーに示されたどの能力を習得することができるか（該当授業科目と学位授与方針に明示された学習成果との関連）Which item of the diploma policy will be obtained by taking this class?
ディプロマポリシーのうち、「DP1」と「DP2」と「DP4」に関連
授業で使用する言語Default language used in class
日本語 / Japanese
授業の進め方と方法Method(s)（学期の途中で変更になる場合には、別途提示します。 /If the Method(s) is changed, we will announce the details of any changes. ）
講義形式で授業は進行するが，必要に応じて講義内容の理解を深めるために演習・課題を行う．課題に対しては，適宜講評する．演習・課題は学期末試験の対策になる．
アクティブラーニング（グループディスカッション、ディベート等）の実施Active learning in class (Group discussion, Debate.etc.)
なし / No
フィールドワーク（学外での実習等）の実施Fieldwork in class
なし / No
授業計画Schedule
※各回の授業形態は予定です。教員の指示に従ってください。
第1回：スケジューリング理論への誘い
全体を通して利用する用語の説明と，各種評価関数を紹介する．
第2回：スケジューリング問題の分類
機械特性と台数，ジョブの特性，評価関数を用いて，スケジューリング問題を分類する方法を紹介する．
第3回：1機械スケジューリング（1）
重み付きSPT (Shortest Processing Time) ルールと，EDD (Earliest Due Date) ルールを紹介する．また，交換議論による証明法を紹介する．
第4回：1機械スケジューリング（2）
Lawlerのアルゴリズムを紹介し，その正当性を背理法により示す．
第5回：1機械スケジューリング（3）
Mooreのアルゴリズムを紹介し，その正当性を帰納法により示す．
第6回：1機械スケジューリング（4）
動的計画法によるアルゴリズムを講義する．
第7回：NP困難性（1）
問題の複雑さに関連して，NP困難，NP完全などの概念を講義する．
第8回：NP困難性（2）
NP困難性の証明例を示す．
第9回：複数機械のスケジューリング（1）
多項式時間で解ける場合を紹介する．元問題をネットワーク上の問題へと帰着することで，効率良く解ける例を紹介する．
第10回：複数機械のスケジューリング（2）
ネットワーク上の最大流を求めることで，効率よく最適スケジュールが求まる例を紹介する．
第11回：2機械フローショップ（1）
Johnsonのアルゴリズムを紹介する．
第12回：2機械フローショップ（2）
Johnsonアルゴリズムが最適スケジュールを出力することを示す．
第13回：その他のスケジューリング
全ての仕事が過不足なく納期を満たすスケジューリング問題を紹介する．
第14回：試験・まとめと解説
理解度の確認をする．
授業時間外の学習（準備学習・復習・宿題等）Work to be done outside of class (preparation, etc.)
【本授業の準備・復習等の授業時間外学習は、4時間を標準とする】アルゴリズムやプログラムに関する基本的な内容を仮定して，授業は進められる．そのため必要に応じて，自ら勉強する必要がある．
テキスト（教科書）Textbooks
特になし．
参考書References
1: P. Brucker, Scheduling Algorithms, Springer, 1995.
2: M. L. Pinedo, Scheduling: Theory, Algorithms, and Systems, Fourth Edition, Springer, 2012.
成績評価の方法と基準Grading criteria
学期末試験の成績（100%）によって評価する．
学生の意見等からの気づきChanges following student comments
効率よくアルゴリズムを実装するためのデータ構造について，実装面も含めて説明する．