シラバス参照
|
シラバス参照
|
| 講義概要/Course Information |
| 科目基礎情報/General Information |
| 授業科目名 /Course title (Japanese) |
離散最適化基礎論 | ||
|---|---|---|---|
| 英文授業科目名 /Course title (English) |
Foundation of Discrete Optimization | ||
| 科目番号 /Code |
|||
| 開講年度 /Academic year |
2024年度 | 開講年次 /Year offered |
全学年 |
| 開講学期 /Semester(s) offered |
後学期 | 開講コース・課程 /Faculty offering the course |
博士前期課程 |
| 授業の方法 /Teaching method |
講義 | 単位数 /Credits |
2 |
| 科目区分 /Category |
大学院専門教育科目 - 専門科目Ⅰ | ||
| 開講類・専攻 /Cluster/Department |
情報・ネットワーク工学専攻 | ||
| 担当教員名 /Lecturer(s) |
岡本 吉央 | ||
| 居室 /Office |
西4-206 (West-4 Bldg, Room 206) | ||
| 公開E-mail |
okamotoy followed by @uec.ac.jp | ||
| 授業関連Webページ /Course website |
http://dopal.cs.uec.ac.jp/okamotoy/lect/2024/sched/ | ||
| 更新日 /Last update |
2024/03/09 01:20:55 | 更新状況 /Update status |
公開中 /now open to public |
| 講義情報/Course Description |
| 主題および 達成目標（2,000文字以内） /Themes and goals（up to 2,000 letters） |
離散最適化における1つのトピックを集中的に学ぶ．今年度は「ジョブ・スケジューリングのアルゴリズム」を題材とする．ジョブ・スケジューリングは離散最適化の重要なトピックであるが，まとめて扱われる機会が (特に日本では) あまりないので，この機会に紹介したい．学部・学域において学んだアルゴリズムの設計技法，例えば，整列 (ソーティング) や動的計画法，そして，グラフのアルゴリズムや計算複雑性といった知識や技法を総動員して取り組むことができるよい題材でもある．この講義では，その基礎に関して，概念と手法を理解し，例に対して応用が可能となることを達成目標とする． The course provides intensive discussion on a single topic of discrete optimization. The topic of this academic year is "Algorithms for Job Scheduling." This is not a typical topic taught in Japan, and this will be a unique and exciting occasion to learn this subject. This is also a good topic in the sense that we will need knowledge and techniques that we have already been acquainted with, such as sorting, dynamic programming, graph algorithms and computational complexity. The learning objective is to understand the concepts and methods, and to apply them to examples. |
|---|---|
| 前もって履修 しておくべき科目（1,000文字以内） /Prerequisites（up to 1,000 letters） |
離散数学，アルゴリズム論第一，(特に，オーダー記法) Discrete Mathematics，Algorithms I (the Big-O notation) |
| 前もって履修しておくこ とが望ましい科目（1,000文字以内） /Recommended prerequisites and preparation（up to 1,000 letters） |
オペレーションズ・リサーチ基礎，アルゴリズム論第二，グラフとネットワーク Introduction to Operations Research, Algorithms II, Graphs and Networks |
| 教科書等（1,000文字以内） /Course textbooks and materials（up to 1,000 letters） |
教科書： なし．講義資料を毎回用意するので，講義webページより各自入手すること． 参考書，参考文献： 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 その他の参考文献は講義中に挙げる． Textbook: None. The course materials will be provided through the course webpage. Supplementary Books and Surveys: 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 The related materials will be referred to in the class. |
| 授業内容と その進め方（2,000文字以内） /Course outline and weekly schedule（up to 2,000 letters） |
英語タイプ：Cc (日本語で説明し，日本語の教材・資料を使う) 授業計画： 1. スケジューリング問題の分類 2. 整列による解法 3. 動的計画法 4. NP困難性と計算量の分類 5. 計算複雑性による問題の分類 6. リスト・スケジューリング 7. 先行制約：基礎 8. 先行制約：多機械 (オンデマンドになるかもしれない) 9. 先行制約：他の半順序 10. ショップ・スケジューリング：機械数が定数 11. ショップ・スケジューリング：機械数が可変 12. 近似可能性と近似不可能性 13. 多項式時間近似スキーム 14. 最近の話題 15. まとめ 進め方： 教室で講義を行うが，リアルタイムでZoom中継も行う．録画した講義を後で見直せるようにする．「遠隔授業に関する情報」に記載されているGoogle Classroomに参加すること． English Type: Cc (delivered in Japanese, materials prepared in Japanese) Plan: 1. Classification of scheduling problems 2. Algorithms based on sorting 3. Algorithms based on dynammic programming 4. NP-hardness and computational complexity 5. Classification of problems based on computational complexity 6. List scheduling 7. Precedence constraints: Basics 8. Precedence constraints: Multiple machines 9. Precedence constraints: Other partial orders 10. Shop scheduling: a few machines 11. Shop scheduling: a lot of machines 12. Approximability and inapproximability 13. Polynomial-time approximation schemes 14. Recent topics 15. Summary Format: Lectures will be delivered at a lecture room, but at the same time broadcast via Zoom. Lecture videos will be made public. Students are supposed to join Google Classroom described in "Distance learning information". |
| 実務経験を活かした 授業内容 (実務経験内容も含む) /Course content utilizing practical experience |
|
| 授業時間外の学習 （予習・復習等）（1,000文字以内） /Preparation and review outside class（up to 1,000 letters） |
講義動画を用いて復習を行う Recap by lecture videos |
| 成績評価方法 および評価基準 （最低達成基準を含む） （1,000文字以内） /Evaluation and grading （up to 1,000 letters） |
成績評価方法：2回のレポートによって評価を行う． 評価基準： 基本的な概念を理解し，解析手法と例に対する応用ができること． Evaluation: Submission of two reports Evaluation criteria: Understanding of basic concepts, and ability of application of methods to examples |
| オフィスアワー： 授業相談（1,000文字以内） /Office hours（up to 1,000 letters） |
メールにて相談． Appointment by email |
| 学生へのメッセージ（1,000文字以内） /Message for students（up to 1,000 letters） |
スケジューリングは応用範囲が広く，実践的な側面について多く研究されている．一方で，この講義の焦点は理論にあり，特に，アルゴリズムの設計と解析を行う．実践的な側面に興味のある人にとっては，その背後にある理論を理解する重要な機会になる．アルゴリズムに興味がある人にとっては，基本的な技法を組み合わせることで何ができるのか分かる機会になる．講義で扱う内容は主に1980年代ぐらいまでの研究成果であって，その意味ではかなり基礎的なものになる予定である． |
| その他 /Others |
他専攻，他研究科の学生も歓迎する． Students from other departments are welcome to join. |
| キーワード /Keywords |
スケジューリング，スケジュール，完了時刻，遅れ，滞留時間，割込，先行順序，半順序，ジョブ・ショップ，フロー・ショップ，オープン・ショップ，整列，動的計画法，多項式時間アルゴリズム，擬多項式時間アルゴリズム，弱NP完全性，強NP困難性，帰着，クリティカル・パス，多項式時間近似スキーム，全多項式時間近似スキーム |