離散最適化基礎論
電気通信大学大学院情報理工学研究科情報・ネットワーク工学専攻
2024年度後学期
火曜2限 (10:40-12:10)
教室:未定
岡本 吉央
テーマ:ジョブ・スケジューリングのアルゴリズム
注意:内容は毎年変わります
ショートカット:
講義資料 |
コメント |
レポート課題 |
公式シラバス |
スケジュール |
参考文献 |
関連リンク |
過去の講義
実施形態
この授業はハイブリッド形式で行います.授業は教室からZoom配信します.スライドはZoomで共有し,板書も教室の黒板では行わず,Zoomで共有したスライドの上から行います.教室では,Zoomの画面をプロジェクタで投影します.そのため,教室で受講することのメリットは (1) ライブ感,時空間共有感覚を持てる,(2) 質問を口頭で即座にできる,(3) ネットワークトラブルに影響されない,などといった点にあります.授業は録画し,あとで公開します.
学生の皆さんの受講形態としては,「教室で授業を受ける」形を推奨しますが,自宅や研究室等からオンラインでリアルタイム受講しても構いませんし,オンデマンド型の受講をしても構いません.ただ,オンデマンド型では,質問をする機会が限られることにご注意ください.
内部シラバス (学務情報システムから見ることができるシラバス) で,Google Classroomのコードを確認し,参加をしてください.
講義資料
コメント
レポート課題
公式シラバス
スケジュール (予定)
- 10/1 (1) スケジューリング問題の分類
- 10/8 休み (出張)
- 10/15 休み (体育祭)
- 10/22 (2) 整列による解法
- 10/29 (3) 動的計画法
- 11/5 (4) NP困難性と計算量の分類
- 11/12 (5) 計算複雑性による問題の分類
- 11/19 (6) リスト・スケジューリング
- 11/26 (7) 先行制約:基礎
- 12/3 休み (秋ターム試験)
- 12/10 (8) 先行制約:多機械 (オンデマンドになるかもしれない)
- 12/17 (9) 先行制約:他の半順序
- 12/24 (10) ショップ・スケジューリング:機械数が定数
- 12/31 休み (冬季休業)
- 1/7 (11) ショップ・スケジューリング:機械数が可変
- 1/14 (12) 近似可能性と近似不可能性
- 1/21 (13) 多項式時間近似スキーム
- 1/28 (14) まとめ
- 2/4 なし
参考書,参考文献
この講義は以下の書籍・文献を参考にして構成されています.
- Michael L. Pinedo,
Scheduling: Theory, Algorithms, and Systems,
6th Edition.
Springer, 2022.
https://doi.org/10.1007/978-3-031-05921-6
- Peter Brucker,
Scheduling Algorithms,
4th Edition.
Springer, 2007.
https://doi.org/10.1007/978-3-540-69516-5
- Bo Chen,
Chris N. Potts,
and
Gerhard J. Woeginger,
A Review of Machine Scheduling: Complexity, Algorithms and Approximability.
In: D.-Z. Du, P.M. Pardalos (eds.),
Handbook of Combinatorial Optimization, Volume 3,
Kluwer Academic Publishers, pp. 21-169,
1998.
https://doi.org/10.1007/978-1-4613-0303-9_25
- Eugene L. Lawler,
Jan Karel Lenstra,
Alexander H.G. Rinnooy Kan,
and
David B. Shmoys,
Sequencing and Scheduling: Algorithms and Complexity.
In: S.C. Graves, A.H.G. Rinnooy Kan, P.H. Zipkin (eds.),
Handbooks in Operations Research and Management Science, Volume 4,
Elsevier, 1993.
https://doi.org/10.1016/S0927-0507(05)80189-6
- David R. Karger,
Cliff Stein,
and
Joel Wein,
Scheduling Algorithms.
In: M.J. Atallah, M. Blanton (eds.),
Algorithms and Theory of Computation Handbook, Volume 2,
2nd Edition,
CRC Press, 2010.
https://dl.acm.org/doi/10.5555/1882723.1882743
-
他にも参考になるものはこちらに追加します.
関連リンク
過去の講義
[Teaching Top]
[Top]
okamotoy@uec.ac.jp