理工学部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
効率よくアルゴリズムを実装するためのデータ構造について,実装面も含めて説明する.