理工学部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 | 2022 |
| 授業コード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.
The goal of this course is to learn typical problems and solution methods in the field of scheduling theory.
After each class, students will be expected to spend four hours to understand the course content.
Your overall grade in the class will be decided based on term-end examination: 100%.
授業で使用する言語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
授業形態/methods of teaching：対面/face to face
※各回の授業形態は予定です。教員の指示に従ってください。
第1回[対面/face to face]：スケジューリング理論への誘い
全体を通して利用する用語の説明と，各種評価関数を紹介する．
第2回[対面/face to face]：スケジューリング問題の分類
機械特性と台数，ジョブの特性，評価関数を用いて，スケジューリング問題を分類する方法を紹介する．
第3回[対面/face to face]：1機械スケジューリング（1）
重み付きSPT (Shortest Processing Time) ルールと，EDD (Earliest Due Date) ルールを紹介する．また，交換議論による証明法を紹介する．
第4回[対面/face to face]：1機械スケジューリング（2）
Lawlerのアルゴリズムを紹介し，その正当性を背理法により示す．
第5回[対面/face to face]：1機械スケジューリング（3）
Mooreのアルゴリズムを紹介し，その正当性を帰納法により示す．
第6回[対面/face to face]：1機械スケジューリング（4）
動的計画法によるアルゴリズムを講義する．
第7回[対面/face to face]：NP困難性（1）
問題の複雑さに関連して，NP困難，NP完全などの概念を講義する．
第8回[対面/face to face]：NP困難性（2）
NP困難性の証明例を示す．
第9回[対面/face to face]：複数機械のスケジューリング（1）
多項式時間で解ける場合を紹介する．元問題をネットワーク上の問題へと帰着することで，効率良く解ける例を紹介する．
第10回[対面/face to face]：複数機械のスケジューリング（2）
ネットワーク上の最大流を求めることで，効率よく最適スケジュールが求まる例を紹介する．
第11回[対面/face to face]：2機械フローショップ（1）
Johnsonのアルゴリズムを紹介する．
第12回[対面/face to face]：2機械フローショップ（2）
Johnsonアルゴリズムが最適スケジュールを出力することを示す．
第13回[対面/face to face]：その他のスケジューリング
全ての仕事が過不足なく納期を満たすスケジューリング問題を紹介する．
第14回[対面/face to face]：試験・まとめと解説
理解度の確認をする．
授業時間外の学習（準備学習・復習・宿題等）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
効率よくアルゴリズムを実装するためのデータ構造について，実装面も含めて説明する．