離散最適化基礎論

岡本 吉央

テーマ：ジョブ・スケジューリングのアルゴリズム

注意：内容は毎年変わります

ショートカット： 講義資料 | コメント | レポート課題 | 公式シラバス | スケジュール | 参考文献 | 関連リンク | 過去の講義

実施形態

学生の皆さんの受講形態としては，「教室で授業を受ける」形を推奨しますが，自宅や研究室等からオンラインでリアルタイム受講しても構いませんし，オンデマンド型の受講をしても構いません．ただ，オンデマンド型では，質問をする機会が限られることにご注意ください．

内部シラバス (学務情報システムから見ることができるシラバス) で，Google Classroomのコードを確認し，参加をしてください．

講義資料

• 1/21 (13) 近似可能性と近似不可能性
  • スライド
  • 講義動画 (整理した後で公開します)
• 1/14 (12) ショップ・スケジューリング：機械数が可変
  • スライド (1/14修正)
  • 講義動画
• 1/7 (11) ショップ・スケジューリング：機械数が定数
  • スライド
  • 講義動画
• 12/24 (10) ショップ・スケジューリング：基礎
  • スライド (12/24修正)
  • 講義動画
• 12/17 (9) 先行制約：他の半順序
  • スライド
  • 講義動画
• 12/10 (8) 先行制約：多機械
  • スライド (12/11修正)
  • 講義動画
  • 補足動画
• 11/26 (7) 先行制約：基礎
  • スライド (11/27修正)
  • 講義動画
  • 補足動画
• 11/19 (6) リスト・スケジューリング
  • スライド (11/20修正)
  • 講義動画
• 11/12 (5) 計算複雑性による問題の分類
  • スライド (11/13修正)
  • 講義動画
  • 補足動画
• 11/5 (4) NP困難性と計算量の分類
  • スライド (11/5修正)
  • 講義動画
  • 補足動画はありません．付録の内容は「講義動画」にて扱っています．
• 10/29 (3) 動的計画法
  • スライド
  • 講義動画
  • 補足動画
• 10/22 (2) 整列による解法
  • スライド (10/23修正)
  • 講義動画
• 10/1 (1) スケジューリング問題の分類
  • スライド
  • 講義動画

• 1/14 (12) ショップ・スケジューリング：機械数が可変
  • 最後に提示された次回以降取り組む課題が興味深かった。
    --ぜひご期待ください :-) 近似可能性や近似不可能性の議論は1990年代に急激に発展して，いまでも活発に研究されています．次回以降はもっと古典的な内容を扱いますが，それが最先端の研究につながっています．
  • 近似比が無限に発散するのに、近似と言って良いのかと思った。
    --たしかにそのような視点はあると思います．一方で，無限に発散するといっても，どのように (どのような増加の仕方で) 発散するのか調べるのは価値があると思います．たとえば，$F \mid\mid C_{\max}$ に対する $m$ 近似というときには，「ジョブ数 $n$ には依存しない近似比が達成できる」という側面も重要だと思います．また，授業でも述べたように，$F \mid\mid C_{\max}$ に対しては (計算理論的なある仮定のもとで) $O(\log^{1-\epsilon} L)$ 近似アルゴリズムが存在しないことが知られています．つまり，$F \mid\mid C_{\max}$ には (その計算理論的な仮定のもとで) 近似比を定数とするアルゴリズムが存在しないわけです．そのような問題の最適値を近似することについて数学的になにかを主張しようとする場合には，無限に発散するような近似比が必然になってしまうことになります．
  • mが定数か定数じゃないかで問題が大きく変わってくるなと改めて感じた回でした...
    --そうですね．$Pm \mid\mid C_{\max}$ が弱NP困難で，$P \mid\mid C_{\max}$ が強NP困難であったことも，改めて思い出してください．
  • 機械数が定数かどうかで計算量が全く減るようなアルゴリズムが作れるというのが面白いと思った。
    --そうですね．一方で，これは「多項式時間アルゴリズム」という概念が「何を定数だと思い，何を入力の一部だと思うか」という，ともすると恣意的な選択に強く依存していることも表しています．皆さんもアルゴリズムを考えるときには，何が入力なのかということをしっかりと意識するようにしてください．
  • O || C_max の近似アルゴリズムの説明において、ジョブが4つで「他で処理中の色は置けない」というので、四色問題を思い出しました
    --たしかにそうですね．ショップ・スケジューリングのように「複数のものの間に資源の競合がある」場合は，グラフの彩色問題を考えて問題の解決をすることがあります (ショップ・スケジューリングの場合は，同じジョブを構成する工程の間に，時間枠という資源の競合があると考えます) ．例えば，$O \mid p_{ij} = 1 \mid C_{\max}$ (オープンショップで，すべての工程の処理時間が1であり，最大完了時刻を最小化する問題) は，二部グラフの辺彩色という考え方を使うと解決できます．
  • 図を用いた説明が大変分かりやすく感じており、ありがたく思っています。しかしふと気になったのですが、図にすることがなかなか困難な状況というのも多いと思います。そのようなときにはこのような戦術をとるとよいというものはありますでしょうか。
    --プレゼンテーションに絞ってお答えします．プレゼンテーション (スライド) においては，文章をだらだらと書かずに，プレゼンテーションの構造をダイアグラム的に示すと効果的です．ダイアグラム的に示すときには，見出しや小見出しをうまく使うことも重要です．それによって，プレゼンテーションの論理構造が分かりやすくなります．なお，「だらだらと書く」ことには，無計画に箇条書きを用いることが含まれます．PowerPointでは，新しいスライドを作ると，ほぼ自動的に箇条書きを使うようなボックスがでてきますが，それを無批判に使うのはよくありません．
  • ここの部屋で彼は，疲れや眠気や頭痛とたたかったのだった．幾晩もシーザーやセノフォンやいろいろな文法や辞書類，数学の問題などで頭を悩まされ，ねばり強く，むきになったり，功名心に燃えたり，時には絶望せんばかりになったりしながら．しかしここで，失われた少年時代のすべての楽しみよりも，はるかに値うちのある数時間を経験することもできたのだ．誇らしさと興奮と勝利感にあふれた夢のような不可思議なこの数時間の間は，学校や試験やいっさいのことを超越して，もっと高い領域を夢み，あこがれたのである．　(ヘルマン・ヘッセ「車輪の下」より引用)
    --『車輪の下』が発表されたのは1905年なのだそうです．120年も前の小説であるのに，現代の青少年と通じる価値観を共有しているところには驚きます．
  • 川は，何事もなかったかのように静かに流れ続ける．彼の命を奪ったその水も，また無言のままだった．　(ヘルマン・ヘッセ「車輪の下」より引用)
    --このようなコメントには学生何でも相談室をご紹介することにしています．また，保健管理センターの栃木先生は精神科医でもあります．大学はいろいろな側面から学生をサポートできます．ぜひ活用してください．
• 1/7 (11) ショップ・スケジューリング：機械数が定数
  • ありがとうございました．
    --こちらこそありがとうございました．
  • 年末年始で色々忘れていて理解が追い付かなかったので復習しようと思いました
    --ぜひ復習をお願いします．授業が始まる前に少し見返しておくだけでも，理解しやすくなると思います．
  • O2||Cmaxのアルゴリズムが理解できた．3分割問題の帰着にようやく慣れてきたと思った.
    --そうですね．慣れてくると，いろいろな考え方が自然に思えてくるかもしれません．
  • 機械数が2の時は、たいていM_1をメインに使ってM_2をサブ的に用いているように思え、右手と左手の関係に似ているように思った。
    --オープンショップの場合は，2つの機械が対等であるはずなのに，そのように思えるのは面白いですね．
  • 我々は力を合わせなければならない．力を合わせれば，どんな困難も乗り越えられる．誰もが自分だけのことだけを考えていては，この島では生き延びることはできないんだ．僕たちには，助けてくれる大人はいない．だからこそ，僕たち自身が手を取り合い，お互いを信じ，支え合うしかないんだ．　(ジュール・ヴェルヌ「十五少年漂流記」より引用)
    --ジュール・ヴェルヌが19世紀の小説家であったということには驚きます．サイエンス・フィクションや冒険小説は賞味期限が短いように思いますが，彼の作品のモチーフは21世紀のいまでも使われ続けているので，通時的な価値を当時から与えていたのだと感じます．
• 12/24 (10) ショップ・スケジューリング：基礎
  • ショップスケジューリングの話でまた新しく、似通った単語が多く、頭がパンクしそうなので、それぞれの性質について整理したいと思いました・・・
    --覚えようとしないことがポイントです．忘れてもよいと思ってください．忘れたときに思い出せるように整理しておいてください．
  • One of the rules of operation scheduling is, operations from the same job cannot be processed at the same time. But at slide 17, in the middle scheduling O-12 is overlapping with O-22. which means that they are processed at the same time. How is this possible?
    --This is impossible, and I was wrong. Thank you for pointing out my mistake. The slide is now corrected.
  • 我々は3分割から逃げられない。
    --3分割問題は強NP困難性を証明するのによく使うので，その意味では逃げられないかもしれません．;-)
  • 3分割問題への帰着が難しいと思った。
    --そうですね．慣れてくると，だんだんと自然に思えてくるかもしれません．授業でもいいましたが，n個の「箱」をうまく作っているところが鍵になっていますね．
  • 最近すごく寒くなってきていて、暖房が手放せない季節を感じました。先生は夏と冬どちらが好きですか？私は今は夏が好きです。
    --どちらもよさがあると思っています．四季折々の風物を楽しむことができるのは，ぜいたくだと思っています．私は日本海側の雪深い地域に1年半ほど住んでいたことがあり，雪かきも体験していますが，それはそれで大変でもある一方で，楽しくも感じられるものです．
  • 汝の新しき主を迎えよ ー それは時と場所によって変わりのない心の持ち主だ．心自身が心の住家で，それ自体地獄を天界ともなし，天界を地獄ともなす．　(ジョン・ミルトン　「失楽園」より引用)
    --数理や物理においては双対性というものが重要だと考えられています．ある対象を観察するときに，ひとつの視点だけではなく，それと対になるような視点を導入して見てみるのです．そうすることで，観察対象の性質がよく分かることがあります．この授業ではその側面を全く出していないのですが，最適化に関して「普通」の勉強をすると，すぐに双対性がでてきます．
• 12/17 (9) 先行制約：他の半順序
  • ありがとうございました
    --こちらこそありがとうございました．
  • そろそろ冬至ですね．今朝，大学に向かう時も，ほぼ満月のような月がきれいでした（まだ日が出てない時間帯だったので…）．
    --寒い季節になってきましたので，体調管理には気をつけてください．
  • My first report submission was graded but also returned, is there anything I have to revise?
    --In case there is something I want to ask, I will contact you directly via Google Classroom. If you don't receive any request from me, there is nothing you are supposed to do for the returned report.
  • 確率論系は図で見てもよく分からないことが多い気がする。ひたすら式をいじっているイメージ。
    --「分かり方」は一通りではないので，まずは自分が分かりやすいと思える分かり方を確立することが大事なのかもしれません．私は図で描くとよく分かるので，図で描くようにしていますし，図で描けるように考えています．その次に，他の人に分かってもらえる分かり方をすることが重要なのだと思います．この授業では，かなり，私の分かり方を皆さんに押し付けているようにも思います．ただ，論文や教科書に書かれている文章をそのまま授業で繰り返すだけなら，そんなに意味はないと思っているので，そこにはない分かり方を提示して，皆さんがいろいろな分かり方をできるようになる助けになれればと思っています．
  • 深さの深い方からジョブを当てはめていくと最適化できる理屈は理解できた
    --アルゴリズム自体は簡単だけれども，それがなぜ正しいのかということを説明するのは，難しいことがあります．今日もあまりうまく説明できた気がしていません．例えば，このアルゴリズムは内向木ではなくて，一般の先行制約に対して必ずしも最適スケジュールを出力するとは限らないわけです (それができてしまったら，NP困難な問題を多項式時間で解いていることになります)．それを考慮すると，直感的に正しそうなアルゴリズムが正しくないこともありうるのだという気がしてくるかもしれません．
  • P|in-tree,pj=1|CmaxとP|out-tree,pj=1|Cmaxは多項式時間で解けると紹介されていたが、in-treeとout-treeのどちらかのみが多項式時間で解けるような問題は存在するのか気になった。
    --結論からいえば，そのような問題はあります．
    Brucker, Garey, Johnsonのこの論文 (1977年)では，次のことが示されています．
    • P|out-tree, r_i, p_i=p|C_maxは多項式時間で解けるが，P|in-tree, r_i, p_i=p|C_maxはNP困難である．(つまり，この場合は内向木の方が難しい．) ここで「p_i=p」というのは，すべてのジョブの処理時間がpに等しいことを意味します．
    • P|in-tree, p_i=p|L_maxは多項式時間で解けるが，P|out-tree, p_i=p|L_maxはNP困難である．(つまり，この場合は外向木の方が難しい．)
    つまり，計算量の階層において，内向木と外向木の間に上下関係がないことが知られていることになります．
  • 任意の直並列グラフに対して，入次数が$0$の頂点や，出次数が$0$の頂点って存在しますか？
    --存在します．直並列グラフでなくても，閉路を持たない有向グラフであれば存在することが言えます (長さがもっとも大きい経路の両端がそのような頂点になります)．
  • 鎖は「さ」って音読みしますけど，何故かグラフ理論の用語は訓読みが入ることが多いですよね…（入次数，出次数，全域木などなど）．
    --鎖は chain の訳なのですが，chain graph というと，chain とは違うものを指すので，それには注意をしてください．
  • 直並列順序以外でも，再帰的に定義できる半順序を考えてみて，それが導く先行制約についてスケジューリングの難しさを考えてみるのは面白そうです．
    --考えている対象を分解することで問題解決を行うことは重要で一般的な方法論です．グラフや半順序の分解にもいろいろな種類のものがあり，いまでも活発に研究されています．
  • 個人的には，見た目を工夫すれば「描かれた直並列グラフを，直並列分解してください」ってパズルは面白そうだと思いました．多項式時間で分解を構成できるアルゴリズムが存在らしいするので，コツがわかるとそんなに面白くないのかもしれないのですが…．
    --面白いと思います．ぜひ作ってください ;-) 簡単かどうかはグラフに描かれ方に依るかもしれません．
  • グラフの性質の特徴づけで「有限個の特定のグラフを，ある意味で含まない（部分グラフだったり，誘導部分グラフだったり色々変わりうる）」って形式のものを見るとワクワクします．
    --そのような定理はグラフの研究において重要であると位置づけられています．含まないというのが部分グラフを考える場合であれば，それらが有限個であれば，すべての可能性を調べることで，入力されたグラフがその性質を持つかどうか多項式時間で判定することが可能になることがただちに分かります．
  • （※突拍子もなく，形式的冪級数に関する話をします）形式的冪級数に対する認識がボヤっとしていたのですが，「環$R$の元の無限列$(f_0,f_1,\dots)$を，$R$係数形式的冪級数という」「環$R$の元の無限列$(f_0,f_1,\dots)$のうち，ある$n' \in \mathbb{N}$が存在して，任意の$n > n'$に対して，$f_n = 0_R$（$0_R$は$R$の加法単位元です）が成り立つものを，$R$係数多項式という」って形で定義している文章を見つけて，急に腑に落ちました．$R$係数形式的冪級数全体が，所謂，多項式の和と積に関して環をなすことを意識すると， $$ \sum_{n \geq 0} x^n = \frac{1}{1-x}$$ というのは，定義でもなんでもなくて，無限列$(1,-1,0,0,0,\dots)$の$R$係数形式的冪級数全体がなす環上の逆元が無限列$(1,1,1,1,1,\dots)$であるってことを言っているのですね．ここまで，代数的な操作しかしてないわけですけど，この議論がある意味で解析学からも正当化されるのは面白いと思いました（むしろそうじゃないと何を意味わからん計算してるんだってことになりかねないわけですが）．
    --分かり方は一通りではないので，いろいろな考え方を通していろいろな分かり方ができることはよいと思います．ただ，無限を扱うときには細かいことを気にしないといけないかもしれないので，注意してください．
  • 力足らざる者は中道にして廃す．今汝は画れり．(本当に力が足りない者なら，途中で力尽きてしまうだろう．お前は自分で自分の力を見限っているだけだ．)　　(孔子　「論語」より引用)
    --マホカンタ
  • おお，弱い者よ，強い者に堪え忍べ　いつの日か，そなたが彼より強くなるから　決意を固めて暴君に対し叫びをあげよ　決意の腕は暴力の手に勝る　唇が渇き，虐げられた者に，笑え，と言え　暴君の歯はいつか抜かれよう　(サアディー　「果樹園」より引用)
    --詩の翻訳というのは難しいと感じました．もとの言語の調べがどれほど保たれているのか気になります．
• 12/10 (8) 先行制約：多機械
  • In P2|prec|Cmax problem using 3-partition problem, if Σa cannot be splitted resulting equal integer, does approximate ratio apply? Because I feel like it's not always possible to find the solution in splitting data into n-partitions with equal Σa.
    --Yes. We can say in each "slot" of length T we can fit at least two jobs of length ai since ai < T/2. This means we can always finish all jobs by time (nT+n-1) plus the sum of n/3 smallest numbers in a1, ... a3n, which is at most (nT+n-1) + nT/6. This means that for those particular inputs, we get the approximation ratio of at most 7/6. But, please also note this approximation ratio only applies to those particular inputs that come from the 3-partition problem. If not, such an approximation ratio is not guaranteed.
  • Coffman-Grahamの部分の証明が難しく感じたので、再度見直して、理解を進めたいと思いました。
    --私の説明が悪かったと思います．すみません．
  • 今日の内容は少し難しいような気がします。もう少し勉強しなければなりません。
    --それは私の説明がよくなかったからだと思います．すみません．
  • Coffman-Grahamの証明で、スライド37ページのn(J) < n(K)となってしまう理由が分からなかった
    --$J$ も $K$ も同じ$\mathcal{S}_j$ に入っていて，その中では，割り当てられた数字の大きい方から順にジョブが左上から右に並べられているからです．
  • スライド31/39において，$M_2$の単調性が崩れるところに着目とありますが，リスト・スケジューリングにおいて，$M_2$に割り当てられた連続した$3$つのジョブの数字が単調増加することはないのでしょうか（あった場合，どうするのだろうと途中まで思ってたのですが，その場合は，$\mathcal{S}$を$M_1$に割り当てられたジョブ$1$つだけからなる集合とすれば問題なさそうか）．
    --はい，そのとおりで，ジョブ1つだけからなる集合を$\mathcal{S}$とします．
  • kasamiさんはCYKアルゴリズムと、P2|prec,pj=1|CmaxのO(n^3)アルゴリズムに携わっていてすごいと思った。どちらも計算量がO(n^3)なのは面白い偶然。
    --Kasamiが嵩先生であると仮定している話なので，その点はご注意ください．嵩先生はCYKアルゴリズムやスケジューリングだけでなくて，オートマトンや符号理論など，いろいろな分野で業績があるので，いろいろな場面で名前を見ます．スケジューリングのアルゴリズムはグラフのマッチングを使っていて，CYKアルゴリズムは動的計画法に基づいているため，O(n^3)がでてくる原理は違うと思ってください．
  • $P$に属しているか$NP$困難であるかが分からない問題が，グラフ同型性問題に帰着できることは，しばしばある印象ですが，$Pm | \mathrm{prec}, p_j=1 | C_{\max}$はそのあたりの事情も分かっていないのでしょうか．
    --私の知る限りでは，その辺りの事情も分かっていないと思います．スケジューリングの問題はグラフ同型性に比べて，計算理論ではマイナーな問題であると思われているように感じます．
  • 月並みですが、計算の自動並列化って難しいんだなと思いました
    --そうですね．ただ，最適スケジュールが本当に必要なのかどうか，という点はしっかりと考えてもよいと思います．この授業では，スケジュールが最適であることと多項式時間で解けることという2つの点を強調していますが，リスト・スケジューリングのように，ある意味で適当ではあるけれども，なんらかのスケジュールを必ず (しかも高速に) 作ってくれるものというのは実用上は役立ちます．考慮すべき状況に合わせて，何を重視すべきか考えて，それに合わせたアルゴリズムを設計することができるとよいと思います．
  • 月並みですが、計算の自動並列化って難しいんだなと思いました
    --同上．
  • 私は、パズル（数理的な問題はその一部にパズル的要素を含んでいることが多いと思っています）に対して、大学に入るまでは結構な苦手意識があったので、いまだにそういう問題に取り組むときには解ける気がしないという強い不安を覚えながら取り組むことが多いです。しかし、難しいとされていないようなものであれば今は解けることも多いので過度に不安に感じる意味もないように思うのですが、不安に感じるというのはむしろ大体の人がそうだったりするものでしょうか。それとも何か別の気の持ちようがあるものでしょうか。
    --私は大体の人を代表できないので，自分の感じ方だけお答えします．
    できないことの不安や焦燥もありますが，それよりも，できたことの喜びが強いと感じています．その喜びを感じることができないと，苦痛であるかもしれません．
    「できないことができるようになる」というのは学びにおいて重要なポイントだと思いますし，そうでないと学ぶ意味はないと思っています．いままで分からなかったことやできなかったことが，経験を積んだ後に，突然分かったりできるようになることは，よくあると思います．誰も始めから箸がうまく使えるわけではありません．経験を通して使えるようになるのです．
    大学というのは「できないことができるようになる」ことをサポートする役割も持つ機関であると思います．「ネット動画で勉強できるから，大学は無意味」と主張する識者のような人がいますが，その人はサポートするという役割を全く見ていません．それはこの講義も同じで，動画が公開されるから授業に出なくてもよいのか，というとそういうものではないと思っています．動画が一般公開されてしまっているからこそ，生身の人間やこのコメント欄が価値あるものになると思っています．
• 11/26 (7) 先行制約：基礎
  • 今日もありがとうございます
    --こちらこそありがとうございました．
  • 今日もありがとうございます
    --こちらこそありがとうございました．
  • （なぜ？）などの補足動画お待ちしてます。ありがとうございます。
    --授業が終わったあとに考えたら，すぐに分かりました．補足動画も作りますが，とりあえず，こちらにて，文章で説明します．
    証明したいことは，$L_{\max}(\sigma^\prime) \leq L_{\max}(\sigma^*)$ です．$d_j \leq d_r$ であることが重要です (これを述べているのに証明で使っていない時点でおかしいと気づくべきでした)．
    $\sigma^*$ において，$J_r$ の後，$J_j$ の前に処理されるジョブ $J_k$ の完了時刻 $C_k$ を見ると，$C_k(\sigma^*) \geq C_k(\sigma^\prime)$ なので，納期ずれも $L_k(\sigma^*) \geq L_k(\sigma^\prime)$ を満たします．同じように，ジョブ $J_j$ についても，$L_j(\sigma^*) \geq L_j(\sigma^\prime)$ が成り立ちます．
    また，ジョブ $J_r$を見てみると，$C_r(\sigma^\prime) = C_j(\sigma^*)$ で，かつ，$d_j \leq d_r$ なので，$L_r(\sigma^\prime) = C_r(\sigma^\prime) - d_r \leq C_j(\sigma^*) - d_j = L_j(\sigma^*)$ が成り立ちます．
    $\sigma^*$ を $\sigma^\prime$ に変えたときに，最大納期ずれが大きくなるとすると，それは $J_r$ の処理が $\sigma^\prime$ において $\sigma^*$ より遅くなるときしかなく (これは場合分けの後で分かります)，そのとき，$L_{\max}(\sigma^\prime) = L_r(\sigma^\prime)$ となります．一方で，$L_r(\sigma^\prime) \leq L_j(\sigma^*) \leq L_{\max}(\sigma^*)$ なので，$L_{\max}(\sigma^\prime) \leq L_{\max}(\sigma^*)$ が成り立つと分かります．
  • 22/24の（なぜ？）の部分は「$\sigma^*$と$\sigma^\prime$で，ずれが大きくなったジョブのずれ増加とずれが小さくなったジョブのずれ減少が相殺されるから」という理解は違ってそうですかね．
    --相殺は総和を考える際にはうまくいきそうですが，最大値はどこか1つのジョブで達成されるので，もう少し違った考え方が必要である気がします．
  • スライド22/44で，$\sigma$の作り方と先行制約がよく効いてるために，$\sigma^*$において，$J_r$を移動させようと思ったら，$J_r$の次から$J_j$までを全て前にずらして，その後に$J_r$を置くしかないのはなるほどと思いました．
    --$J_j$ と $J_r$ だけを交換できないので，注意が必要ですね．
  • For the case of 1|prec|γ, if the job flow is closed loop, where should the first job start? As there are no vertex with in-degree of 0. For example, J1→J2→J3→J1.
    --We assume there is no such closed loop. But if such a closed loop occurs, we cannot start any job in the loop. This is often called a deadlock situation, which must be avoided. There are several methods that break such deadlocks, but this is beyond the scope of this series of lectures.
  • 入次数と出次数を「いりじすう」，「でじすう」と言って，将来誰かに怒られた時は，岡本先生の責任にしてよいとの発言がありました．責任にするのは私の行為ですが，責任をとるという行為は先生が行うことだと考えました．そこで質問です．先生は，責任をとる，という行為をどのように考えているのでしょうか．また，私が将来怒られたとき，実際に責任をとるという行為をして頂けるのでしょうか．気になってお昼寝ができません．
    --この場合は「私を責めてよい」あるいは「私のせいにしてよい」というだけの意味です．法的に責任をとることは想定していませんし，責任をとるという行動をすることも想定していません．分かりにくい言い方をして，お昼寝を阻害してしまったのは，すみません．
  • 有向グラフのアルゴリズムの多くは、グラフにループが存在しないことを条件としているのですか？
    --多くは，ループ (閉路) が存在しないことを仮定しません．応用上は，閉路を持つ有向グラフも多く出てきます．一方で，先行制約として現れる有向グラフは閉路を持たないことが保証され，そのような保証がある場合は，閉路が存在しないことを仮定してアルゴリズムやプログラムを設計します．
  • トポロジカルソートわかりやすくておもしろいです．閉路検出も同時にできるのうれしいです．
    --そうですね．授業の記法でいえば，$S$ が空集合になったとき，$L$ に現れない頂点があれば，どこかに閉路があることになります．
  • トポロジカルってかっこいい響きだと単純に思った
    --トポロジカル順序をなぜ「トポロジカル」と呼ぶのか，ということについて，その起源がよく分かっていないようです．
  • 無閉路有向グラフ$G$と，任意のトポロジカル順序に対して，トポロジカルソート（入次数版，出次数版問わず）において$S$から頂点を取り出すある順番が存在する（つまり，$G$の全てのトポロジカル順序はトポロジカルソートを使って構築可能である）ことは正しいでしょうか．
    --正しいです．トポロジカル順序において，(1) 最初の要素の入次数は0であり，(2) トポロジカル順序から最初の要素 (たとえば $a$ とします) を取り除くと，グラフから頂点 $a$ とそれに接続する辺を取り除いたグラフに対するトポロジカル順序となる，という性質が成り立つことから，質問の内容が正しいことが導けます．
  • 無閉路有向グラフ$G$の頂点集合$V$が，全順序集合の部分集合であるとします．このとき，入次数版のトポロジカルソートで，$S$から頂点を取り出すときに，$V$に関する順序が一番小さいものを取り出すこととします．すると，$G$の全てのトポロジカル順序を$V^{|V|}$($V$を$|V|$個掛けたの直積のつもりです)に関する辞書式順序で順序付けた場合において，一番小さなトポロジカル順序が出てくる，というのは正しいでしょうか（これが正しければ，逆に$S$から頂点を取り出すときに，$V$に関する順序が一番大きいものを取り出せば，一番大きなトポロジカル順序が出てきそう）．
    --全順序集合と言って考えると分かりにくいので，すみませんが，用語を変えます．すべての頂点に異なる番号がついていて，トポロジカル順序どうしには，その番号について，辞書式で順序がついていると考えます．
    その状況で，$S$ から頂点を取り出すときに，番号がもっとも小さいものを必ず取り出すようにすると，その辞書式順序において最小のトポロジカル順序が得られます．番号がもっとも大きいものを必ず取り出すようにすると，最大のトポロジカル順序が得られます．
  • 一般に，単純有向グラフ$\mathcal{P} = (\mathcal{V},\mathcal{A})$では，$|\mathcal{A}| = O(|\mathcal{V}|^2)$なので，$O(|\mathcal{V}| + |\mathcal{A}|)$は$|\mathcal{V}|$に関して，一般には線形にならないですよね…．実は，無閉路単純有向グラフだと$|\mathcal{A}| = O(|\mathcal{V}|)$とかになりましたっけ（これくらいなら頑張って自分で証明してもいい気はしますが…）．
    --$O(|\mathcal{V}| + |\mathcal{A}|)$は$|\mathcal{V}|$に関して，一般には線形になりません．ご指摘は正しいです．以下，補足です．
    (1) 授業で「線形時間」といったときには，入力のサイズに関して線形であることを意味しています．入力のサイズは隣接リストの大きさに相当し，有向グラフにおいては$O(|\mathcal{V}|+|\mathcal{A}|)$ (あるいはそれに$\log |\mathcal{V}|$を掛けたもの) になります．それに関して線形なので，線形時間といっています．(2) $|\mathcal{A}|$のオーダーがオーダー$|\mathcal{V}|^2$より小さくならない例はあります．次の図を見てもらうと，$|\mathcal{A}|$がだいたい$|\mathcal{V}|^2/4$になっています．
    
  • グラフは図だと分かりやすいが、式になると一気に複雑に感じる。
    --ぜひ，図でイメージするようにしてください．
  • データ構造は学域に所属していたころに勉強したはずですが，グラフの話ほど直感が備わってないです．電通大出身なのに(^^;
    --せひ復習をしてください．忘れることを恐れる必要はありません ;-)
  • 先行制約に対して，クリティカル・ジョブの集合って一意に定まりますか？
    --先行制約とジョブの処理時間に対して一意に定まります．クリティカル・ジョブをちゃんと定義していませんが，「処理が遅れる (開始が遅れる，処理時間が長くなる，など) と，全体の最大完了時刻が必ず遅れてしまうジョブ」のことです．これは $C_{\max}$ を最小にするどんなスケジュールでも，開始時刻が同じであるようなジョブであると言い換えられます．
  • クリーク問題での説明が難しかった
    --すみません．もう少し丁寧に説明すればよかったです．
  • 機械数有限の場合は面白そうだなーと思ってたら扱ってくれるとのことで嬉しいです．
    --次回の内容になります．お楽しみに．
  • 共産団になると，この役割は現在の本質をすっかり変えてしまいます．そして，ここで卑劣だったものも，あちらでは賢明なものになる．ここで，現在の状態では不自然なものも，あちらでは，きわめて自然なものになる．万事はすべて，人間がいかなる状況の中に，いかなる環境の中にいるか，で左右されるものです．すべては，環境のいかんに懸かっているので，人間そのものは問題じゃないのです．　(フョードル・ドストエフスキー「罪と罰」より引用)
    --10年ぐらい前，『カラマーゾフの兄弟』がフジテレビの連続ドラマとして放送されていました．舞台を日本に移していますが，重厚な作りだったことを覚えています．吉田鋼太郎や松下洸平をそこで初めて知りました．
  • 今日の服装の先生は，初めて見た気がします．去年以前もその上着を召されていたことってありました？
    --昨日買いました．UNIQLOのカラーバリエーションが減った気がして，残念です．
  • 寒い．風邪ひいたかもしれん…．
    --お大事になさってください．
• 11/19 (6) リスト・スケジューリング
  • コメントありがとうございました．
  • 第1回のレポート課題頑張ります＞＜
    --はい，よろしくお願いします．
  • 今日の知識はずいぶん前に習ったものですが、先生は以前習ったことと同じことを話さなかったので、コース終了後に調べて、以前習ったことの間違いだと気づきました。
    --間違いだと気づけたのはよかったと思います．どの部分のことなのか文面からはよく分かりませんが．
  • ひな形をみてGoogleの画像検索のスマホ版だなあと思っていました．
    --すみません，Googleの画像検索のスマホ版を使ったことがなく，よく分かりません (-_-;
  • 割と着込んだつもりでしたが寒かったです．そろそろカイロの出番ですかね…
    --エジプトの首都はおそらく暑いでしょう．
  • 論文を探す時、被引用数にばかり注目してしまう。
    --わかります．被引用数の多い論文は注目されている (注目されていた) ものであるわけなので，よい論文であるための指標として使えると考えられています．ただ，分野の間では出版される論文の総数や引用・参照の方法に違いがあるので，分野の違う論文の間で被引用数を比較するときには注意が必要です．
  • It is very useful knowing about approximation ratio to be able obtaining semi-optimum scheduling with overcoming computation complexity. By the way, pardon me for out-of-topic question, but I am inspired with your slide design that in every sessions always have regular format. They are very neat and easy to read. Did you create them using specific tools or just manually using powerpoint?
    --For the lecture slides, I'm using Ipe with a presentation style by Jens Schmidt (with my own modification). I've just realized I'm using an older version of Schmidt's style. I should update. I should also note that I'm also using PowerPoint and LaTeX beamer from time to time: the choice depends on situations and audience.
  • スケジュールにおけるアルファ近似とアルゴリズムのアルファ近似の違いがうまく理解しきれなかったです。スケジュールの方はひとつのスケジュールについての話で、アルゴリズムの方はアルゴリズムが出力する全てのスケジュールについての話をしているのでしょうか
    --はい，そのとおりです．
  • 離散的な設定から，根号や自然対数を含む結果が紹介されるとワクワクします．いったいどんな観察をしたのだろうかと．
    --今日はその一端をお伝えしたつもりになっています．ワクワクしますね :-)
  • 研究の関係で，ある最小化問題の最適値の下界をずっと気にしている人です．「下界を如何に見つけるか」「下界を利用して非自明な（面白い）結果を如何に導くか」といったことは難しいですが，とても楽しいです．
    --それは素晴らしいです．ぜひ楽しんでください :-)
  • 「解く」に関する話を聞いていて，「技術的な議論において，用語の定義はコミュニケーションを行うために必要である」ことを改めて思いました（一方で，定義さえすれば十分ではないという厄介な問題もあるのですが…）．
    --はい，技術的な議論においてはそのとおりだと思います．
    一方で，ご指摘のとおり定義さえすれば十分であるわけではないことに注意が必要です．特に，「なぜそのように定義するのか」という根源的なアイディアは，常に気にしておきたいことだと思ってます．今日の話題では，「近似のよさの測り方を比で考える理由」もそうです．与えられたものを当然だと思わずに，他の考え方や定義の仕方はないのか，ということを考えることは重要だと思います．
  • 前回学んだNP困難性を満たし，近似も難しいような問題があれば，すごく難しい問題なんだろうなと思った．
    --そうですね．これについては第13回 (近似可能性と近似不可能性) で扱う予定です．実際，「多項式時間○○近似アルゴリズムが存在すれば，P=NP」というような定理を証明できる場合があります．
  • 近似比が入力に依存しない定数で上から抑えられる（今回紹介されたケースは全て該当する）と，近似比が小さいなという気分はあります．だからと言って，例えば，近似比100万が小さいかと言われると困りますが…（もちろん，近似比を入力サイズを使わないと上から抑えられない場合（オーダーが定数じゃない場合）は，でっかい入力を使えばいずれ100万も超えてしまうのでそれより小さいのはその通りです）．
    --近似アルゴリズムの理論では，多項式時間で動作するという条件のもとで，「α近似アルゴリズム」と言うときのαをどれだけ小さくできるか，ということを考えます．その意味では，αが入力に依存し，正の無限大に発散する可能性がある場合よりも，αが定数である場合の方が「小さい」と見なすことにしています．一方，直前のコメントへの回答にあるように「多項式時間○○近似アルゴリズムが存在すれば，P=NP」という形の定理において，どんな定数を「○○」にいれても，これが正しくなる問題の存在が知られています．そのような問題に対して，多項式時間で保証できる近似比の最小値 (あるいは下限) というものが気になり，それがよく研究されています．
  • LPTが最適にならない例がなかなか思いつかなくて、出てきたときなるほどと思いました。正しそうな解法の間違いを探すの難しく思います。
    --悪い例 (入力) を作るというのはコツが必要かもしれません．問題の構造や証明の仕組みを深く理解する必要がある場合が多く，やみくもに作ろうとしてもうまくいかないかもしれません．
  • 私が人生で最初にぶつかった難問は，美ということだったと言っても過言ではない．父は田舎の素朴な僧侶で，語彙も乏しく，ただ「金閣ほど美しいものは此世にない」と私に教えた．私には自分の未知のところに，すでに美というものが存在しているという考えに，不満と焦燥を覚えずにはいられなかった．美が確かにそこに存在しているならば，私という存在は，美から疎外されたものなのだ．　(三島由紀夫「金閣寺」より引用)
    --京都はよく訪れますが，観光でいっているわけではないためか，金閣寺には一度しかいったことがありません．小学校の修学旅行だったので，かなり昔のことですが，そのころでもかなり混んでいたことを覚えています．改修直後だったので，金箔もまぶしく，庭も含めて美しかったことは印象に残っています．
  • $P||C_{\max}$をLPTでリスト・スケジューリングするところの補題2で，各機械が処理するジョブ数が2以下であることは，背理法を使っているのですね（3つ以上のジョブを処理する機械が存在すると矛盾）．
    --はい，そのとおりです．
  • $P||C_{\max}$をLPTでリスト・スケジューリングするところの補題2で，どうして最適スケジュールになるのかで詰まりかけました．冷静に考えてみると，ジョブ交換論法を使えば良さそうです．
    --はい，ジョブ交換論法を使って説明するようにスライドを作っていたのに，とばしてしまいました．次のコメントの回答で補足します．
  • 補題2の証明が分からなかった
    --ありがとうございます．ここで，文章として証明を書いてみます．また，スライドも少し修正しています．
    まず，$p_j > C_{\max}^*/3$ であるとき，任意の最適解において，どの機械にも割り当てられるジョブは高々 $2$ 個であることを確認します．最適解において，ある1つの機械にジョブが $3$ つ割り当てられていると仮定します．すると，その処理時間の和は $3 \times (C_{\max}^*/3)$ よりも大きくなります．しかし，これは $C_{\max}^*$ よりも大きいので，最適解の最大完了時刻が $C_{\max}^*$ であることに矛盾します．
    この観察から，ジョブ数を $n$，機械数を $m$ とすると，$n \leq 2m$ となることがわかります．
    一方で，LPTで得られるスケジュールにおいても，各機械に割り当てられるジョブは高々 $2$ つであることが次のように分かります (この部分の説明が授業でもスライドでも欠けていたと思います)．仮に，LPTによってある機械にジョブが3つ割り当てられるとします．3つ目のジョブを $J_k$ とすると，それを割り当てる直前まで，どの機械もあるジョブを処理していることになります．すべてのジョブの処理時間は $C_{\max}^*/3$ より大きいので，$J_1$ から $J_{k-1}$ までの処理時間の総和は $m \times (2C_{\max}^*/3)$ よりも大きいことになります．よって，どのように $J_1, \ldots, J_k$ を処理しても (つまり，最適スケジュールでも)，最大完了時刻が $C_{\max}^*$ よりも大きくなってしまい，$C_{\max}^*$ が最適値であることに矛盾します．
    このことから，LPTでは次のようにジョブが処理されることが分かります．まず，$J_1, \ldots, J_{2m-n}$はそれぞれ1台の機械で処理します．そして，各 $i = 1, \ldots, n-m$ に対して，$J_{2m-n+1}$ と $J_{n+1-i}$ を同じ機械で処理することにします．このスケジュールを $\sigma$ とします．
    この $\sigma$ が最適スケジュールになることは，(最適スケジュールでは，各機械で処理するジョブが $2$ つ以下であるという事実を知った後なので) 直感的によく分かると思います．ちゃんと証明するならば，ジョブ交換論法を使えばよいと思います．(議論は難しくないですが，場合がいくつかあるので，ちゃんと書くのは大変です．) ．
• 11/12 (5) 計算複雑性による問題の分類
  • コメントありがとうございました．
  • 今日もありがとうございました
    --こちらこそありがとうございました．
  • ありがとうございました、かなり冷えます。zoo
    --かなり冷える動物園ですね．体調には気をつけてください．
  • 少し教室が肌寒かったのですが、暖房がつく予定はありますか。
    --例年は11月中旬に教室の暖房運転を始めるようです．
  • 長い付録にも慣れてきた。
    --実をいうと，私自身は慣れていません ;-) スライドにいれるべき内容をもっと絞るべきだと思っているのですが，いろいろと考えているうちに多くなってしまい，付録になってしまっています．あまり好ましくないと思っています．
  • 強いNPの難しさとは何なのか、以前は理解できなかったが、今日の内容を学んで急に理解できた。
    --それはよかったです．1つのことがすぐに理解できないことはよくあるので，時間をかけて理解できたことはよいことだと思います．
  • 問題の関係性を論じれる帰結という概念が面白いと思った
    --はい，この考え方はスケジューリングに限らず，問題解決における様々な場面で使えるので，ぜひ身につけて下さい．
  • 前回の問題の帰着でも、計算量のわかっている問題よりも計算量の多い問題に帰着できれば良くなり、証明しやすくなると思った
    --はい，基本的な考え方はご推察どおりです．
  • 計算時間においてある問題をある問題に「帰着する」ところを初めて見ました．楽しいなと思いました．
    --帰着は問題解決においてとても重要な考え方なので，ぜひ慣れて，活かしていってください．
  • 始まった瞬間が納期であるような入力が倫理的であるかどうかは，アルゴリズムを擬人化して，その時の設定次第になりそう．
    --これができるのは Lmax や ΣTj の場合だけで，ΣUj (遅れジョブ数最小化) の場合はうまくいきません (始まった瞬間に納期を満たせないと，ΣUjが必ずnになってしまいます)．ΣUj は割と扱いにくい問題なのではないかと思っています．
  • McNaughton のアルゴリズムにおいて、最長の処理時間max p_jよりC_maxを短くできないというのは、それより短いとどうしても同じ時刻に同じジョブを処理することになってしまうからだと思いますが、これは鳩ノ巣原理の連続版とも見ることができそうだと思いました。
    --理由はそのとおりです．「鳩ノ巣原理の連続版」と見るという視点は面白いですね．そのような視点は私になかったです．
  • McNaughtonのアルゴリズムで，$P | \text{pmtn} |C_{\max}$の最適解と最適値が簡単に求められることは分かりましたが，最適値をそのままに，分割するジョブの個数を最小化する問題や，ジョブの分割回数を最小化する問題は難しくなったりするのでしょうか．
    --分割の回数を少なくするというのは重要だと考えられています．授業の中ではちゃんと言いませんでしたが，McNaughtonのアルゴリズムでは，各ジョブは高々1回しか分割されないことが保証できます．一方で，分割の総数を最小化しようとすると (計算量の意味で) 難しい問題になってしまいます．より正確にいうと，P|pmtn|Cmaxの最適解の中で分割の総数を最小にするものを1つ見つける問題は強NP困難になります．これは前回 (第4回で) 紹介したP||Cmaxに対する強NP困難性の証明と同じ帰着を使うと，P|pmtn|Cmaxの最適解で，どのジョブも分割されないもの (つまり，P||Cmaxの最適解で，すべての機械の完了時刻が同じもの) が存在することと，もとの3分割問題のインスタンスに対する答えが「分割できる」となることが同値になるからです．
  • 絶対に守ってほしいわけではないけど，やんわりと守ってほしい処理順があるときに，重み付き問題としてモデル化するのは，なるほどと思いました．
    --はい，重みをそのように使うことができます．最適化問題として現実問題をモデル化する際には，絶対に守ってほしいものは「制約」として書き，絶対というわけではないものは「目的関数」に組み込むことで考慮する，という方法を使うことが多くあります．専門用語では，絶対に守るべき制約は hard constraint と呼び，できる限り守りたい制約は soft constraint と呼んで区別することがあります．
  • Today's lecture is well-structured so I can understand the big picture about relationship between various configurations of optimization problems. Also, thank you for showing reference of 'schedulingzoo' so I could do some trial and error in comprehending between theory and logical practice. Moreover, related to weighted objectives (wjCj, wjUj and wjTj), I assumed that the weight coefficient wj is a qualitative component that is assigned just by engineer's analysis on jobs priority, please correct if my assumption is wrong.
    --Your assumption on weights is correct. I should still say a remark. We will need a careful choice of weights since we turn a "qualitative" component (job priority) into a "quantative" component (weights that are real numbers) of the problem. There is no unique way of the choice of weights, but it is highly dependent on individual situations. We will need to investigate given situations carefully to determine those weights.
  • 以前の講義で，ジョブ交換論法を図で説明する際に，長方形の高さが全て同じだと強調していたのは，今回の重み付きの場合の理解につなげるためだったのかと腑に落ちました（以前の講義では，同じじゃないとそりゃあ困るじゃんって思ったくらいであまり気にしてなかったので）．
    --強調していたのは，レポート課題にしようと思っていたからかもしれません．記憶があまり定かではありませんが．いずれにせよ．重みを高さとして表現することで，「面積」として理解する方法がそのまま使えるのは面白いと思っています．
  • 口頭では，$L_{\max}$の候補の数直線を実数の数直線って仰られていたと思いますが，その場合でも二分探索ってちゃんと止まるのでしょうか（考える計算モデルにもよる？）．
    --実をいうと，ここは微妙なところで，どんな機械の環境αとジョブの特性βを持ってきても本当に止まるのか，というのは，しっかりと考えていません．一方で，この半年間の授業で扱うような「普通」のαやβであれば，Lmaxとして現れうる数値が数直線の離散的な有限部分集合に限られることが分かり，しかもその部分集合の要素数が入力サイズの指数関数的にしか大きくならないことが分かり，二分探索によって多項式時間アルゴリズムが得られます．しかし，今後，私たちが想定していなかったような機械の環境αやジョブの特性βが発明されることもありえて，それらにおいて必ず止まることが本当に言えるかどうかは分かりません．
  • $R | \text{pmtn} | \sum C_j$が$R || \sum C_j$より難しい（と考えられている）のは，分割可能がゆえに解の自由度が高すぎて，最適性の保証が難しくなってそうなのが関係しているのかなと思いました．
    --R|pmtn|ΣCjの難しさの理由を説明するのは，私にとってなかなか難しいように感じます．私自身も論文に書いてある証明は理解できて，(おそらく) 正しいということは分かるのですが，これはただ単に「R|pmtn|ΣCjが難しいという現象がある」ということを見ているにすぎません．本来は「R|pmtn|ΣCjが難しいという現象が起こる理由」まで理解したいのですが，そこまで私自身が理解できているようには思えません．
  • ああ，余はこの書を見て始めて我地位を明視し得たり．恥ずかしきはわが鈍き心なり．余は我身一つの進退につきても，また我身にかかはらぬ他人の事につきても，決断ありと自ら心に誇りしが，この決断は順境にのみありて，逆境にはあらず．我と人との関係を照さんとするときは，頼みし胸中の鏡は曇りたり．　(森鷗外「舞姫」より引用)
    --むかしベルリンはよく訪れました．ブランデンブルク門からウンター・デン・リンデンを通ってフンボルト大学にいくときは森鷗外の舞姫がいつも頭をかすめました．新しい空港ができてからまだベルリンにいってないので，近々いける機会があるといいな，と思ってます．
  • 前回，「仮定が何とかならないものか」とか書いた人です．色々な思いが読み取れるように書いちゃいました．すみません．数学的に正しいことを述べようと思ったら省けないのはその通りなので，(2)の立場ではなかったです．先生が書かれた回答の中だと(3)の立場が一番近いですが，道具も道筋も無くて「どうしたものか…」って状況にありそうですね…．(1)の立場は難しいですが，興味深いと思います．色々調べてみると，公理系の無矛盾性の強さを比べる理論があるらしいので，もし，独立であることが示されれば，$\mathrm{ZFC} + \mathrm{P} = \mathrm{NP}$と，$\mathrm{ZFC} + \mathrm{P} \neq \mathrm{NP}$で無矛盾性の強さがどちらのほうが強いか（どちらのほうがより矛盾してそうか）は気になります（このあたりの理論の言葉遣いはあまり深く勉強していないので，変なことを言っている気もしますが）．なんか，講義の内容からはどんどん脱線した気がしますが，許してくださいm(__)m
    --講義の内容からどんどん脱線してください．自由なコメントをお待ちしてます．
    公理の強さの比較は数学基礎論においては重要なテーマで，PとNPに関わる問題も数学基礎論の観点から研究するアプローチがあります．数学というものをメタに扱おうとすると，それを営為として行う人間をモデル化する必要がでてきて，それはよく計算主体としてモデル化されることになります．私は，計算理論というものは人間，自然，社会，その他万物をよりよく理解するための理論的枠組みだと思っています．その志は道半ばだと思いますが，そうであっても，理論の有用性は揺るがないと思っています．
  • The Scheduling Zoo で設定できる各問題を頂点として，「頂点$u$が多項式時間で解けるならば，頂点$v$も多項式時間で解ける」という規則で有向辺$(u,v)$を引いたグラフ（ただし，別の辺を使って推移的に鍵括弧内が推移的にわかる場合は辺を引かない）が気になりますね…（手で書くにはデカすぎるけど，プログラムを書けば頑張れる？）
    --元文献として挙げているLagewegらの論文 (1982) が考えているのは，まさにそれで，絵を描くところまで至っていませんが，頭の中ではそれを想定しています．それによって，多項式時間で解ける問題とNP困難である問題の境界を定めることを研究課題として挙げました．これは (下にも挙げている) Complexity results for scheduling problemsに引き継がれて，図の一部を見ることができます．
• 11/5 (4) NP困難性と計算量の分類
  • Thank you for your reference, I'm understand about big O notation now. It is basically a function to yield maximum output from particular input. For this case, big-O notation is used to determine the worst case or maximum number of steps the algorithm needs to solve discrete problem. From this concept, it can be categorized into three polynomial time problem (strong, weak and pseudo). I find this topic will be more interesting, for example I can roughly calculate the computation complexity of encountered problem, and could analyze the best algorithm used for the problem.
    --That's great! Then, please keep in mind that it is also important to learn how to choose the best algorithm for your own problem, and also how to define what's "best" for you.
  • 文字に起こすと理解が難しいものが多いので図にして丁寧に教えていただけて助かってます
    --図にすることには力を入れています．文字だけだと理解しにくいものも，図で見ると当たり前に思えてくるかもしれません．むしろ，文字で書いているものは，図で考えたものを文章化したものだと思ってよいと思います．
  • 講義やら論文で言葉には頻繁に出会うが、今回の講義でちゃんとNP困難性について理解できたと感じる。
    --NP困難性の気持ちはお伝えしましたが，定義は紹介していないので，定義などについては成書を参照してください．
  • NP困難性の定義は知っていたが、NP困難に強弱があることを初めて知った。
    --はい，強弱があります．これは数値を入力として持つ問題を扱うときには，特に重要になってきます．
  • 計算複雑性のお話は（聞く分には）おもしろいです。
    --はい，ぜひ自分でも証明をしてみてください ;-)
  • NP困難であることの証明には他の問題を帰着していましたが、もし帰着できなかった場合は証明不能ということになるのでしょうか
    --帰着できない理由が，我々の能力不足なのか，本当に正しくないのか (NP困難ではないのか)，のどちらであるのか，ということを判断する技術を我々ははっきりと持っているわけではなく，それがこの分野の研究をややこしくしているところです．例えば，NP困難な問題 (例えば P||Cmax) を多項式時間で解ける問題 (例えば 1||ΣCj) に多項式時間で帰着できれば，P||Cmaxを多項式時間で解けることになり，P = NP であることまで言えます．しかし，そのような帰着が存在するかどうか，分からないのです．計算理論というのはそれほど未熟で，分からないことだらけなのです．
  • 帰着するだけでNP困難性を証明できるのは嬉しいことだと思った（それでも難しいが）。
    --帰着というのはNP困難性の証明だけではなく，アルゴリズムの設計技法としても重要です．我々はいろいろなアルゴリズム (ソフトウェア) をブラックボックスとして使っていいます．それは，そのブラックボックスが使えるように，解決すべき問題の入力 (インスタンス) を変換しているわけです．これはまさに帰着で行っていることです．この視点は次回登場します．
  • NP困難性の証明法について今まで考えたことがなく、その方法について初めて知ったので、とてもためになった。また、分割問題が個人的に面白い問題だなと思った。
    --分割問題というのは，見た目が単純な問題なのですが，それでもNP困難であるというのは，気に留めておくとよいかもしれません．分割問題を通じてNP困難性が証明される場合は割とよくあります．
  • （変なことを言っていたら申し訳ないのですが）スライドの『1 | r_j | L_maxの強NP困難性 (4)』というスライドで、「最適値 <= 0 ⇒３分割問題の答えは『できる』」と記載があります。しかし最適値 < 0の場合には処理時間がT未満のセクションがあるということで、必ずしも各分割ごとの和が等しいとは言えないのではありませんか？
    --変なことかどうかは気にせずコメントを書いてください．それは重要です．;-)
    さて，ご質問ですが「最適値 < 0となることはない」というのはおっしゃるとおりです．その意味で，「最適値 <= 0」と「最適値 = 0」は同値になり，一応，スライドに書いてあることは正しいままになります．どちらの書き方が分かりやすいか思案して，「<=」にしましたが (「=」にしかならないことはこのような考察を必要とするので)，その方が分かりにくかったかもしれません．
  • 帰着ってMinecraftみたいですよね．制限された道具で，如何に自分の欲しい機能を作り上げるかというところが．※Minecraftが「制限された環境」であるかは議論の余地があるかもしれません．
    --これは重要な視点で，計算モデルの考え方に通じます．「Minecraft」という計算モデルにおいて，何ができるのか考えると，「Minecraftという計算モデルにおけるアルゴリズム」を考えることができます．そうすると，Minecraftにおける1つのステップが何であるか定めれば，Minecraftにおけるアルゴリズムの計算量を考えることもできます．
    これについては，『数学セミナー』の私の連載をご覧ください．Minecraftについて書いているわけではありませんが，計算モデルというものをどう考えるかということは書いてます．
  • 「ただし，$\mathrm{P} \neq \mathrm{NP}$のもとで」という仮定は何とかならないものですかね．$\mathrm{P} = \mathrm{NP}$がペアノ算術や$\mathrm{ZFC}$から独立だったりすれば，それはそれでありがたいんですけど，Wikipedia(https://en.wikipedia.org/wiki/P_versus_NP_problem)を見るにそれを示すのはもっと大変そうで．
    --仮定が何とかならないものか，ということの真意を分かりかねているので，以下，的外れなことを書くかもしれません．回答は3つあります．
    (1) 仮定をしないという立場は，それを公理として認めるという立場なのかもしれないと思い，その立場から回答します．P≠NPというのは，公理としてよいほど，広く信じられているものではないと感じています．例えば，こちらの記事 (私の講演が文字起こしされたものですが) を参考にしてください．そのため，たとえP = NPであることの真偽がよく公理として用いられる数学的言明と独立であったとしても，それによって，P≠NPであることを公理として認めてよいことにはならないように (今のところ) 感じます．
    (2) いちいちその仮定を書くのが面倒であるという立場なのかもしれないと思い，その立場から回答します．この仮定を書かないと数学的に正しいことを述べていないことになるので，仮定を省くことはできません．また，計算理論において「多項式時間で解けるかどうか」という判別は，大きくそびえる計算複雑性の階層の中の1つの境界に過ぎません．PとNPに関わる問題は大きな研究課題ですが，それだけが計算複雑性において研究されているわけではありません．細かい仮定の違いによって，細かい計算複雑性の分類が行われているという現状があり，それをはっきりさせるためにも，仮定をしっかりと書くことは重要であると思います．
    (3) P≠NPかP=NPであることの早期解決を望むという立場なのかもしれないと思い，その立場から回答します．この問題が近い未来において解決されると，専門家はあまり思っていないように感じます．専門家の中のどの程度の割合がこの問題に取り組んでいるのかも分かりません (なお，私は専門家ではない，という立場です)．解決に向けたリサーチ・プログラムがあるようにも思えません (私が知らないだけかもしれませんが)．この問題に取り組むための，よい手段が今のところはないのだと思います．
  • Pm||Cmax が弱NP困難なのに P||Cmax が強NP困難になるのは少し不思議な感じがするが、 P||Cmax は P1||Cmax を解くアルゴリズム、P2||Cmax を解くアルゴリズム、P3||Cmax を解くアルゴリズム… と無限個のアルゴリズムを持っていなければならない(まったく別の解きかたを考えなければならない) と考えれば納得できた気がする。
    --そうですね．もう1つ重要なことは，多項式時間アルゴリズムが何かということです．例えば，P2||CmaxはO(n²)時間で解けて，P3||CmaxはO(n³)時間で解けて，…となっていて，一般的に，Pm||CmaxがO(n^m)時間で解けるとします．これは，mが定数 (つまり，問題で決まっている) ならば，どれも多項式時間の計算量になっています．しかし，mが入力の一部 (つまり，入力で与えられる) ならば，O(n^m)という計算量は指数時間になります．このような側面もP||Cmaxを難しくしていると思います．
  • 到着時刻が設定されている場合，どのジョブに対しても納期より先に設定されてほしい（現実の問題のモデルとしてみた場合）ですが，ジョブ・スケジューリングの分野において，到着時刻が納期より遅い場合は考慮されているものなのでしょうか．
    --定義上は，到着時刻が納期より遅い場合も考えています．現実に，そのような状況はあまりないかもしれません．
  • やがて彼は左手の小指と無名指と親指の間に挿んだ絵筆の穂を，娘の背にねかせ，その上から右手で針を刺して行った．若い刺青師の霊(こころ)は墨汁の中に溶けて，皮膚に滲んだ．焼酎に交ぜて刺り込む琉球朱の一滴々々は，彼の命のしたたりであった．彼は其処に我が魂の色を見た．　(谷崎潤一郎「刺青」より引用)
    --青空文庫にあって，短編だったので，読んでみました．谷崎潤一郎の小説を読むのははじめてで，小説自体も久しぶりに読みましたが，文章表現は映画のように美しく，内容としても (おそらく一般には倒錯的と見なされると思いますが) どちらの登場人物にも割と共感しました．
• 10/29 (3) 動的計画法
  • I'm finding some trouble understanding several mathematical notations in this lecture, especially like big-O-notations. I think I have to comprehend myself about this in parallel. Do you have any good and easy-to-understand reference to learn about big-O-notations? Thank you.
    --Excuse me, but I wrote the Big-O notation as prerequisites in the syllabus. So, I somehow assumed students were supposed to know it. But, you can still catch up. A short introduction can be found in one of the pages provided by GeeksforGeeks. This should be a good starting point, and in some sense, this is enough for our class. More detail can be found in Wikipedia, but this would be too much as an introduction.
  • 前回の講義で理工学全般においては図にして考えることが有効とあり、納得するのですが、しかしなぜ図にするのが有効なのかということが何気に気になっています。
    --私の考えですが，図に表すと直感が働きやすくことが重要だと思います．今回の授業でもはじめの紹介した動的計画法アルゴリズムでは「2次元の表」を実際に書いて説明しました．しかし，2つめに紹介した動的計画法アルゴリズムは表に書こうとすると「4次元の表」になります．これはうまく書けないと思います．しかし，2次元のときの直感が働いて，4次元の表が想像できるようになると思います．また，データ分析においても，まずは可視化をして (図に表して)，データ全体の傾向を掴むことが重要です．
  • 図を使った説明が丁寧で非常によく理解できました．
    --ありがとうございます．図を描くことは重要視してます．皆さんも自分なりの図を使って考えてください．
  • 具体例を考える重要性は、先輩や先生から何度も言われるのですが、最初から理論的にできれば具体例を考えたことが無駄になってしまうように感じて、つい具体例を考えることがおろそかになってしまいます。具体例を考えることで理論の完成のあとにチェックできるし、理論を考えるときに勘違いのような間違いがなく自信をもって進むことができるなどいいことが多いのはわかるのですがやっぱりめんどくさいです。とくに、自明すぎずに難しすぎない具体例を考えることが難しく億劫です。いい具体例をおもいつくコツのようなものはありますか？具体例を考えることが面倒な人への激励のようなものはありますか？
    --具体例を思いつくことは，その対象を深く理解しているかということの試金石だと思っています．よい例を思いつくことは，自明なことではありません．対象を深く理解していないと，よい例を作れないと思っています．理論というのはある特定の現象 (つまり例) に共通する性質を見抜いて作るものだと思っています．教科書を見ると，そこには何も理由がなく理論が書かれているかもしれませんが，それが作られた背景に例があったことは気に留めておくべきだと思います．
    私たちは，何が正しくて何が間違っているのか，未来のこともよく分からない世界を生きています．世界は教科書ほど整理されていません．例は，整理されていない世界で参考になります．過去の例 (つまり歴史) は同じ過ちを繰り返さないための道標になりますし，未来に対する例 (つまり予測) は現状の緻密な理解に基づきます．
  • 時々，既に知られている命題のshort proofが成果である論文を見かけますが（前回の講義の内容も，それが元になってたと思います），このshortというのは，日常会話における言葉遣いとしてのshortなのでしょうか（私はそう思っています）．実は，何か数学的な基準や定義があったりするのでしょうか．
    --これは数学的な基準や定義があるものではなく，主観的なものであるように思います．日常会話における言葉遣いであると考えてよいように思います．明確な基準がないけれども数学においてよく気にするものには，short の他にも simple や elegant というものがある気がします．ただ，elegantというのは主観が強すぎるので，論文にはあまり書かれない気がします．(なお，じきに『数学セミナー』で私が「エレガントな解答を求む」の出題をします．興味があれば，ご覧ください．)
  • 動的計画法を使っているからか、前回よりもアルゴリズム自体が難しく感じられた。また、再帰的な構造の定め方の重要性を再確認した。dynamic programmingにおける「programming」が表による計算法という意味であるのは意外であったが、納得であった。
    --最適化において「programming」と言うとき，それは「planning」の意味である，という説明もよく見ます．表による計算法というのは，何もかも手計算で行っていたときの考え方で，大昔は数値計算も手でやっていたわけです．それを行う専門職を計算手 (英語でcomputer) と呼んでいて，現在のcomputerの意味とはcomputerという語が違う意味を持っていた歴史があるそうです．
  • 動的計画法はいかに表をうまく使うのかが大切だと思いました。計算の重なりのようなものが削減できる工夫が必要なのですかね？
    --「計算の重なりのようなものが削減できる」というのが動的計画法に基づくアルゴリズムの根幹にはあるように思います．例えば，P2||Cmaxの方では，一方の機械の完了時刻がtであるようにできるかどうか考えて，それをtrue/falseで表したわけですが，そのようなスケジュールがたくさんあったとしても，表に書くのはtrue/falseの1ビットだけになるわけです．これによってうまく「計算の重なり」を削減していることになります．
  • 再帰的な構造と状態に注意しながら動的計画法を考えていきたい。再帰式を作るのはなかなかしんどい。補足動画も合間を見て視聴したい。
    --再帰の考え方はコンピュータサイエンスの核となるものなので，ぜひ使いこなせるようになってください．
  • 前半の内容については大まかにわかったのですが、後半の内容は聞いていて詰まる所があったように感じたので、スライドを見返し、理解を深めたいと思いました。
    --細かいところはややこしいので，まずは全体の流れを理解してみてください．
  • 総納期遅れのアルゴリズムがなぜうまくいくかの理解ができなかった
    --補題Bに書かれている内容をまず理解するのが重要かもしれません．それが分からないと，再帰式も理解できないように思います．
  • 補題Bの証明が難しそうです。補足動画をみますが何がとくにきいていますか？
    --付録を見ると分かるのですが，補題Bを証明するために，別の補題 (補題C) を証明してます．補題Cがややこしくて，補題Cを認めれば，補題Bは割とすんなりと証明できます．最適解が変わらない範囲で，ぎりぎりまで納期を変化させるというのが効いているようで，どうしてこれを思いつくのか，というところまで，私自身が理解できていません．
  • 補題Bの「最適解が変わらない限り」という文言はシンプルだが、中身はすごく難しそうだと感じた。
    --「最適解が変わらない限り」というのは直感に訴える言い回しなのですが，数学的な定義は補題Cに現れます．
  • 単純そうな問題でも証明となると中々難しいんだな、と思いました。
    --そうなんですよね．そのような側面がジョブ・スケジューリングを面白くしているとも見れますし，ややこしくしているとも見れます．
  • 補題Aは，一般的にはうまくいかないEDDが，逆にいつうまくいくのかをよく考えれば思いつくのかもなーと感じました．「一般的にはうまく行かない方法を試してみる」というところに行きつければですが．
    --補題Aは2つのジョブを比較しているだけなので，割と思いつきやすい気がします．証明も前回と同じようなジョブ交換論法を使えばよいので，(場合分けは多いですが) 証明自体も思いつきやすいと思います．
  • 前回添字ごちゃごちゃで質問出した者です。回答で理解できました。今回は前半部分がややむつかしかったので復習しようと思います。後半わかりやすかったです。
    --理解可能な回答ができてよかったです．ありがとうございます．
  • 「自明」な解法では、メモリ（計算のメモ）はどの計算をチェックしたかを記録するので、ジョブ数くらいのメモリで済むと思うのですが、解説であった通り動的計画法ではジョブ数の時間の和くらいメモリが必要だと思います。計算の速さと（空間的な？）計算のしやすさのバランスを考慮することもあるのでしょうか？それともどちらか一方だけを考慮するのが普通でしょうか？
    --いろいろな観点の回答があるので，分けます．
    (1) 動的計画法のアルゴリズムでは，再帰式において二度と参照されないところの値は忘れてもよいことになります．例えば，授業で紹介したP2||Cmaxに対するアルゴリズムでは，f(j,t)を計算するときに，f(j-1,t)とf(j-1,t-p(j))を使っていますが，逆の見方をすると，f(j,t)がf(j+1,t)とf(j+1,t+p(j+1))の計算にしか使われないと考えることもできます．つまり，f(j+1,t+p(j+1))の計算が終わったら，f(j,t)は忘れてよい (捨ててよい) ことになります．そのようにして，メモリ利用を削減することができます．オーダーでいえば，表を全部覚えておくと O(nΣp(j)) の大きさの表をずっと覚えることになりますが，そのように削減すると O(Σp(j)) で済みます．
    (2) 1つの問題を解く際に必要となる時間と空間(メモリ)の両方を考慮することはむしろ普通です．多くの状況では，時間と空間の両方に制限があります．その制限の中で，どのように問題を解くのか考えることが重要で，場合によっては，その制限の中で問題を解くことが難しい場合 (不可能である場合) もあります．その場合は，解くことを諦めて，「解くこと」の意味を変える (緩和する) 必要があります．それらを考慮すると，「自明」なアルゴリズムを使う方が好ましい状況はありえます．
    (3) この授業では，時間の方を主に考えます．理由の一つは，使用する空間 (メモリ) が使用する時間を越えられないことにあります．空間を使用するには，その空間にアクセスする時間がかかるからです．つまり，時間計算量の上界は空間計算量の上界になります．それもあって，時間計算量を考えることで，空間計算量についても (不真面目に) 考えているつもりになっています．
  • 動的計画法は証明を眺めるのは比較的楽だが、自分で証明を考えるのがすごい苦手だった(動的計画法が使えるよと言われてもなかなか思いつかない)。先生の「動的計画法を考えるときの鍵」を参考に色々な証明を見て思いつけるようにしていきたい。
    --問題における再帰的な構造を見出すことが問題解決の鍵になることは多いように思います．問題解決においてよく言われる「困難は分割せよ」というフレーズにおいて，再帰的な構造があれば，分割した後も同じ問題になるので，解決が簡単になるはずです．
  • $1||\Sigma T_j$に対する動的計画法アルゴリズムの気持ちを理解するには，処理時間と納期のプロットがすごく効いているように思いました．自分も資料を作るときは，うまい図解を作れるようにありたいものです．
    --この図は自分で考えて描きました．教科書や論文に描いてあるのをみたことがありません．もしかしたら他の人も使っているのかもしれませんが，一応，自分で考えたつもりになっています．
  • 前回，先生が心配されていた割には，$1||\Sigma T_j$に対する動的計画法アルゴリズムの気持ちは，講義内の説明でも十分飲み込めたように思います（もちろん，きちんと納得するには補題が成り立つことを確認する必要はありますが）．
    --それはよかったです．雰囲気を伝えることに重きを置いたので，一応それは達成できたのかと思います．
  • 補題Bは「補題Aに基づいて問題を分割してみる（動的計画法のプロだったら思いつくのかも？）」「分割する場所を変えてみることを思いつく（つまり，補題Bを証明しようという気になる）」「実際，補題Bが成り立つ」がうまく揃った奇跡の産物に見えます．本当に深く$1||\Sigma T_j$を考えた結果得られたのだろうなーと思いました．
    --現代的な視点から見ると，多くの例を使って (コンピュータで) 試してみると，補題Bが正しそうだということは分かるのかもしれません．一方，これは70年代から知られていたことであって，当時の研究者の洞察には驚かされます．
  • 「天の川．きれいねえ．」駒子はつぶやくと，その空を見上げたまま，また走り出した．ああ，天の川と，島村も振り仰いだとたんに，天の川のなかへからだがふうと浮き上がってゆくようだった．天の川の明るさが島村を掬い上げそうに近かった．旅の芭蕉が荒海の上に見たのは，このようにあざやかな天の川の大きさであったか．裸の天の川は夜の大地を素肌で巻こうとして，すぐそこに降りて来ている．恐ろしい艶めかしさだ．島村は自分の小さい影が地上から逆に天の川へ写っていそうに感じた．　(川端康成「雪国」より引用)
    --まだ北陸新幹線がないころ，北陸に鉄道でいくときに，越後湯沢まで上越新幹線でいって，そこで特急はくたかに乗り換えるという手段を使っていました．越後湯沢に向かうところでトンネルを通ると『雪国』のことを思います．ただ，私は読んだことがありません．
• 10/22 (2) 整列による解法
  • コメントありがとうございました．以下，回答になります．
  • 第2回のスライドp.25, 26の「最大納期遅れ」は「最大納期ずれ」ではないでしょうか？第1回のスライドを見ると、納期遅れはmax{0, C_j(σ) - d_j}となっているので、0より小さくなることはないと思います。
    --はい，そのとおりです．失礼しました．修正しました．私自身が日本語の「納期遅れ」と「納期ずれ」に慣れていないのが原因だと思います．もっぱらtardinessとlatenessという英語でいう方に慣れているため，すみません．なお，一応，そのページの「最大納期遅れ」は最大納期遅れのままでも数学的には正しいです．
  • スライド36/40の図を自分で補う作業（例えば，各スケジュールや各ジョブの納期を表す記号を，添字の順序に気を付けてもう少し補う）をすれば，先生が講義で仰っていた「冷静に考える」って部分は達成できそうな気がします．
    --そのとおりだと思います．ぜひ考えてみてください．
  • 図での説明は文章より直感的でわかりやすく、内容理解の点では嬉しいです。ですが証明の書き方も学びたいので、文章の方も載せていただけませんか。私が証明に慣れて無さすぎるのもあると思いますが、今日の授業であったような置換を定義するというやり方は知りませんでした。
    --文章と図の両方を載せるというのは，分量が多くなりすぎる (つまり，準備に時間がかかる) ので，できれば避けたいと思っています．すみません．文章で証明を書くときには，次を考えてみてください．(1) 解 (スケジュール) をどのように表現するか，(2) その表現において最小化する目的がどのように書くか．
  • 直感的にわかりやすい証明とそうでない証明があった。そうでない方は復習が必要だと思う。
    --証明がわかりにくかったのは，おそらく，私自身が証明をしっかりと理解できていないからだと思います．その点はすみません．教科書や論文に書いてあることについて，まずは正しく理解することが重要ですが，その次に，それを分かりやすく他の人に説明できるようになることが重要です．おそらく，「その次に」というところまで，私が進めていないのだと思います．
  • 各アルゴリズムのアイディアは思いつけるほど単純だったが、証明が意外と複雑だった。
    --まず，「アルゴリズムの正しさは証明すべき事項である」と認識することが重要です．他の授業でそれが強調されることはあまりないのかもしれませんが，それはアルゴリズムやプログラムを設計する際に考えないといけない，基本的なことだと思っています．その際の証明は，考える問題が複雑になるほど，ややこしくなる傾向があります．この授業では，その重要さを感じて，実際に証明を理解することを体験していると思ってください．
  • Moore-Hodgsonのところの補題で置いていかれてしまったので、来週までに理解できるように頑張ります。
    --はい，動画もありますので，ぜひ復習してください．
  • What is more preferable, minimizing Lmax or minimizing number of late jobs? For example, this two cases: A) L1 = 2, L2 = 1 (both are late, Lmax = 2) B) L1 = 4, L2 = -4 (only L1 late, Lmax = 4).
    --It'd depend on the situation, namely, the case that you have in mind. For example, if you earn according to the number of jobs on time, minimizing the number of late jobs is more preferable. If you are punished by Lmax, minimizing Lmax is more preferable. In this course, we will not talk about how to convert real-world problems into the framework of job scheduling, but rather, we will discuss how to solve those job scheduling problems after the conversion. Such conversions are usually called "optimization modelling", which is another research field that we are not going to cover in this course.
  • 1台のスケジューリング問題はjobを連続せずに分割するメリットはないように思いますが、これを簡単に説明できそうでしょうか？「証明をする」という点において引っかかってしまいました。
    --おそらく次のコメントと関係があるので，そちらで答えます．
  • ※自分が考えたことを記述した部分が抜けてました。同じようなコメントを連投してすみません。 1台のスケジューリング問題はjobを連続せずに分割するメリットはないように思いますが、これを簡単に説明できそうでしょうか？「証明をする」という点において引っかかってしまいました。（最大納期ずれの場合は、分割したjobを二つのjobと考えて同じ納期と考えればよい？総完了時刻最小化は分けた方が必ず悪い値になることを示す？）
    --今回の授業で扱った4つの問題については，そのとおりです．一応，分割を可能とする場合には，3つ組記法の真ん中の部分 (βのところ) に「pmtn」か「prmp」と書きますが，つまり，「1||ΣCj」と「1|pmtn|ΣCj」の最適値は同じで，「1||ΣCj」の最適スケジュールでジョブの分割を行わないものがある，ということになります．証明としては，分割する最適スケジュールがあると仮定して，そこから分割しない最適スケジュールを作って，「面積」を比較すればよいです．最大納期ずれの場合も同じように考えるとよいと思います (ただ，コメントにあるように2つのジョブと見なす考え方はややこしいような気がします)．
    一方，ジョブに到着時刻がある場合 (βにrjが書いてある場合) は，1機械であってもジョブの分割によって得をすることがあります．
  • 今回のJobが3つのときの値はp_1 = 9, p_2 13, p_3 = 5, d_1 = 25, d_2 = 22, d_3 = 19だと思うのですが、どこかにまとまっていると復習のときは自分でプログラムを作ったときにその値で試せるので嬉しいです。
    --ありがとうございます．この意見はとりいれるのが簡単なので，今後とりいれようと思います．なお，今回，9ページの例ではp1 = 9, p2 = 13, p3 = 5で，19ページの例では，p1 = 9, p2 = 13, p3 = 5, d1 = 25, d2 = 22, d3 = 19で，28ページの例では，p1 = 9, p2 = 13, p3 = 5, d1 = 25, d2 = 14, d3 = 4 になっています．
  • Moore-Hodsonのアルゴリズムの証明が現時点では理解できなかった。遅れジョブ数最小化のアルゴリズムの例で、Moore-Hodsonのアルゴリズムに沿えば最初に遅らせるジョブはJ_3になるのではないかと思った。
    --おそらく「仮に間に合うジョブ」の説明がよくなかったと思います．すみません，アルゴリズムにて「1. EDD順でジョブを処理しようとする」のですが，ジョブを処理しようとした瞬間には，そのジョブをもう「仮に間に合うジョブ」と見なします．そして，それを処理しようとしたときに間に合わない場合，それも含めて，いままで仮に間に合うジョブとしたものの中から処理時間最大のジョブを遅らせます．
  • Moore-Hodgsonについて、処理時間についてJ_j < J_{i+1}であって，「仮に遅れるジョブ」J_l(l<n)の処理時間がどの納期よりも長く、最適値が1のとき、「仮に間に合うジョブ」で取り除かれる処理時間最大のものJ_k(k<l)とJ_mの二つが取り除かれてしまうのではないかと思いました．
    --添字のつけ方がよく理解できないので，質問の意図とは違う解釈を私がしているかもしれないので，以下，それはご了承ください．処理時間がどの納期よりも長いジョブは，任意のスケジュールにおいて遅れるジョブになるので，任意の最適スケジュールでも遅れるジョブになります．Moore-Hodgsonでも，それを処理しようとしたときに自身の間に合わず，仮に間に合うジョブの中で処理時間最大のものになるので，遅れるジョブになります．
    と，ここまで書いていて，直前のコメントと同様に，「仮に間に合うジョブ」に対する私の説明がよくなかったのではないかと感じました．1つ上のコメントの回答も参考にしてください．
  • 理屈はわかるんですけどいざ証明！ってなると難しかったです 💦
    --そうですね．証明を説明しだすと流れが切れてしまうので，今後は説明の構成や順番を変えてみることも考えます．
  • 別の講義の連続最適化では微分積分や線型代数の要素が多いと感じたが、ジョブスケジューリングではアルゴリズムやプログラミングの色が強いように感じた。
    --これは3つの回答があります．(1) この授業 (半年14回の内容) はそうだと思います．むしろそのようにしています．それは，この14回で1つの内容を (あまり他の知識に依拠しないようにして) 完結させるための工夫だと思ってください．(2) ジョブスケジューリングの最先端の論文を見ると，いわゆる連続最適化の知見を多く使っています．これは連続最適化の知見を応用しているだけなので，連続最適化の研究であるわけではありませんが，ジョブスケジューリングや離散最適化の研究において，連続最適化が使われるのは珍しいことではなく，むしろ王道です．一方で，離散最適化の研究は連続最適化の研究に対する1つの動機を与えているという側面もあって，例えば，連続最適化アルゴリズムのベンチマーク的な問題では，離散最適化に端を発するものが多くあります．(3) ここまでの回答を踏まえた最後の回答ですが，すべての分野はつながっていると考えてください．これは最適化や数学でなくても同じです．世界は一つであって，それを異なる人が異なる視点で見ることで，異なる学問分野 (に見えるもの) ができているのだと考えるのがよいと思っています．同じ世界を見ているのですから，つながっているのは当たり前で，「分野」と呼んでいるものは，人間の都合で分けられただけだと私は思っています．
  • 最適値を動かす発想は「おぉー」って思いました．
    --これはa simple proofにおける鍵だと思います．数学におけるよく知られた定理に対しても，違う発想で見ることで，別の証明が得られることはよくあります．皆さんも教科書や論文を読むときに，自分なりの証明を考えてみるとよいと思います．
  • 教室の黒板に「合言葉 I22」とある．なんだろう．本心ではレポートでも証明は図を用いて押し切りたいところ．
    --すみません，合言葉は前の授業で書いたものが残っていました．
  • 終始私の心を圧えつけていた不吉な塊がそれを握った瞬間からいくらか弛んできたと見えて，私は街の上で非常に幸福であった．あんなに執拗かった憂鬱が，そんなものの一顆で紛らされるーあるいは不審なことが，逆説的な本当であった．それにしても心という奴は何という不可思議な奴だろう．　(梶井基次郎「檸檬」より引用)
    --「丸善」という語を見ると『檸檬』を思い出します．
  • 今の研究が楽しく、博士課程後期に進みたいと思っているのですが、こんな動機で進学しても大丈夫なものか心配でどうしようかと悩んでいます。先生は何をきっかけに博士課程に進みましたか？また、博士課程に進む際に重要なことは何だと思いますか。
    --動機はなんでもよいのではないかと思います．私も「今の研究が楽しい」ということぐらいが動機だったと思います．博士課程に進む際に重要なこと，ではないかもしれませんが，一般論として，自分の意思決定に自分で責任を持つということが重要だと思います．他の人の意見を参考にすることは大事だと思いますが，最後に決めるのは自分であって，その責任を自分で持つという覚悟はどんな場面でも必要だと思います．
  • 岡本先生が教授職をやっていて一番大変だったことは何ですか？
    --あまり考えたことはなかったですが，いまパッと思うのは，「他の人を信頼することと，他の人から信頼されること」です．教授職だから，というわけではないかもしれませんが．
• 10/1 (1) スケジューリング問題の分類
  • コメントをありがとうございました．以下のように掲載されます．
  • 授業の目的をよく理解することが出来ました
    --それはよかったです．目的が達成できるように進めていきますので，見守っていてください．
  • 授業でやることの概要が分かった
    --よろしくお願いします．
  • Overall, the class discusses about optimization for machine-job with specific scheduling cases. I think this class would be good for me to practice critical thinking and analysis that will be useful for future professional tasks.
    --I hope future classes will be beneficial for you.
  • 離散数理工学に続いて，授業を楽しみにしてます！
    --こちらこそよろしくお願いします．
  • 講義資料などの形式がわかりやすく整理されており助かる．二週休みということで間は開くが頑張っていきたい．
    --はい，ぜひ復習をしておいてください．
  • スケジューリング問題はほかの授業でちょっと触れるだけで終わっていたので、半年間じっくりやれるのが楽しみです。
    --シラバスにも書いたのですが，スケジューリングの理論を最適化やアルゴリズムの観点からまとめて説明される機会があまりないと思い，それはよくないと思ったので，今学期のトピックとしてみました．私も楽しみです．
  • 電通大5年目にして初めて授業を受けましたが、あのスピードで話続けられるのがすごいと感じました。単純な疑問ですが、毎年テーマを変えるのはなぜですか。テーマを変えない方が教員的にも楽だと思っています。
    --あのスピードで話続けられないので休憩があるのです :-) それはともかく，テーマを変えるのは，いろいろなテーマを扱いたいからです．過去の内容はスライドや動画がありますので，皆さんも勉強しようと思えば，それらで勉強できるようになっています．毎年テーマを変えると，そのストックが増えていき，結果的に社会の利益になると思っています．
  • 話すスピードがちょうど良く、講義の内容が頭に入ってきやすいです。
    --ありがとうございます．分からないところの確認には動画などを見返してみてください．
  • レポートを出すタイミングは決まっていますか？
    --出題するタイミングは前半の終わりごろと後半の終わりごろです．前半は第6回までだと思ってください，出題の2週間後を提出締切としようと思っています．
  • レポートの分量を大体でいいので知りたいです。
    --レポートの解答の分量は各個人に依存しますので，私が決めるものではないと思っています．レポートの問題の分量は3つ程度の問題を出すことを考えています．解答期限は2週間程度を予定しています．
  • ジョブスケジューリング問題とは少し違うかもしれないが、スケジューリングと言えばアルバイトのシフト作成を思い出した
    --それはシフト・スケジューリングとよく呼ばれています．この授業が扱うジョブ・スケジューリングとは違うものだと考えられていますが，重要なテーマです．
  • 論文サーベイでフライトスケジューリング問題の関する内容のものを見かけた気がしたので授業内容に興味が出てきた。
    --フライト・スケジューリングは航空機のスケジューリングですね．例えば，滑走路を機械だと思い，離陸させるべき航空便をジョブだと思うと，ジョブ・スケジューリングのような設定の問題がでてくると思います．
  • 競技プログラミングで区間スケジューリング問題を知っていましたがそれより複雑かつ広い範囲の問題を扱いそうに見えます。最大完了時刻最小化問題と聞いてAHC(Atcoder Heurisitic Contest)の第25回をなんとなく思い出しました。https://atcoder.jp/contests/ahc025/tasks/ahc025_a
    --区間スケジューリングは，各ジョブにおいて，納期と到着時刻の差がちょうど処理時間と等しくなっていて，どのジョブの処理にも遅れがあってはならない状況を考えていることになります．
  • 砂のがわに立てば，形あるものは，すべて虚しい．確実なのは，ただ，一切の形を否定する砂の流動だけである．しかし，薄い板壁一枚へだてた向うでは，相も変らず，砂掻きをつづける女の動作がつづいていた．あんな女の細腕で，いったい何ができるというのだろう．まるで，水をかきわけて，家を建てようとするようなものじゃないか．水の上には，水の性質にしたがって，船をうかべるべきなのだ．(安部公房「砂の女」より引用)
    --「砂の女」とスケジューリングを関連付けるなら，無限スケジューリングや周期的スケジューリングというものを想起します．建物や装置の監視をずっと続けなければならないときに，それをどのようなタイミングで行うのか，というようなことを考えます．砂を掻き続けなければ埋もれてしまうのです．
  • スケジューリング問題は興味があったので今後の授業が楽しみです。
    --ぜひ楽しみにしていてください :-)
  • それぞれの最適化の目的が，どういう考えで何を重視したいのかがわかりやすかったです．
    --スケジューリングに限らず，何かの意思決定をするときには，「誰にとっての最適なのか」ということをしっかりと考える必要があります．最適化の考え方を適用しようとするときにはぜひ気に留めてください．
  • 自分の研究では最適化としてMDPを定式化して価値反復法で最適解を導出するが、この授業の内容を応用できる問題もあるため、スケジューリング問題の基礎的な内容に関して理解を深めたい。
    --MDPというのはMarkov decision process (マルコフ決定過程) ですね．第3回で登場する動的計画法はMDPと深く関係しています．授業の内容がご自身の研究に活かせるかもしれないという気持ちで授業を受けていると，新しい発見があるかもしれません．
  • どのジョブをどのマシンがいつ処理するかについて表現する必要があるので、解の表現が複雑になりそうに思った。
    --本来，解の表現は割と気にする必要があります．この授業では「Ganttチャート」が解の表現であると思ってもらってよいです．そのためには，分割可能でない場合 (non-preemptiveの場合)，各ジョブを処理する機械とその開始時刻を定めれば十分です．一方で，分割可能であると (preemptiveの場合であると)，ジョブがいくつにも分割される可能性があるので，分割後のピースのそれぞれに対して，処理する機械と開始時刻を定めねばなりません．また，そのピースの数が有限に収まらないかもしれません．
  • 講義内では，全ての機械に対して，全てのジョブの処理時間が割り当てられていたので，暗に全ての機械は全てのジョブを処理可能であることが仮定されているように思いました．機械によって処理できないジョブが存在する場合， 1. 一般にスケジューリングで扱われることがあるのか 2. 一般にスケジューリングで扱われる場合，今回の講義で扱う範疇にあるのか が気になりました．
    --「暗に全ての機械は全てのジョブを処理可能であることが仮定されている」というのはそのとおりです．機械によって処理できないジョブが存在するような状況を扱うことはあります．その場合，2つの方法があります．1つは今回の講義で扱う範疇で取り扱う方法があり，それは「処理時間を∞とする (あるいはとても大きな数とする)」ことで表すものです．もう1つの方法は，そのような状況をジョブの特性 (3つ組記法では $\beta$ の箇所) に書くことです．これはよく $M_j$ と書くことで表され，machine eligiblity restriction と呼ばれるようです．ふつうは後者で扱います．
  • 巡回セールスマン問題がスケジューリング問題として扱えるときいて、自分がアルゴリズムが思いつかなくて実装できなかったアプリにもスケジューリング問題とみなせるものがありそうだなと思いました
    --普通の巡回セールスマン問題は最終完了時刻最小化を目的としていると考えられるのですが，スケジューリング問題だと思うと，他の目的の場合も気になります．実際，総完了時刻最小化を考えた場合は，minimum latency problemと呼ばれたりして，研究されています．
  • スライドと説明、とても分かり易かったです!25ページに出てきたpjは、ジョブjに与えられている処理時間という認識でいいのでしょうか?
    --はい，pjはジョブjに与えられている処理時間という認識でよいです．
  • 今回のスライドでは機械数mが1や2、3となっていましたが、一般的な問題ではどのくらいの値が与えられますか。
    --どの機械数の問題も現実にはよくでてきます．その意味で，どの機械数が一般的であるのかということを述べるのは難しいか，あるいは，適切ではないように感じます．一方で，どこまで大きくなりうるか，ということについては考えることができます (ただし，時代背景で異なることはあります)．例えば，ハイパフォーマンスコンピューティングででてくるように，ノードにジョブを割り当てるような場面では，ノードが機械に対応することになります．つまり，ノード数が機械数です．理研の富岳では，ノード数が158,976なので，それを全部同時に使おうとすれば (そんなことができるかどうかはともかく) 機械数は158,976になります．
  • 今年もコメントの季節を迎えることができて嬉しいです．
    --コメントの季節というのがあるのですね．あまりそういう認識を私は持っていませんでした ;-)
  • この入力欄を大きくしてほしいです
    --すみません，Google Formsにて入力欄の大きさを変更する方法が (調べた限りでは) 分かりません．入力欄が小さくて不便かもしれませんが，例えば (PCで入力しているなら) テキストエディタでコメントを作成して，それを入力欄にコピー＆ペーストすることで入力するのはどうでしょうか．
  • コンピュータへのペンでの書き込みには何のハードウェア製品を利用されているのでしょうか
    --いま手元に実物がないので間違っているかもしれませんが，おそらく，XP-PENのArtist 12 Proです．
  • 岡本先生は離散系の話は大体わかるのでしょうか？
    --「離散系の話」と「大体わかる」の正確な意味に依存しますが，大体も分からないというのが個人的な感覚です．「離散系」といってもその内容は多岐に渡ります．例えば，AMS (米国数学会) が2020 Mathematics Subject Classification (MSC2020) というものを作っていますが，その中で「離散系」と見てよさそうなものは，「05 Combinatorics」，「06 Order, lattices, ordered algebraic structures」，「39 Difference and functional equations」のdifference equationsの方，「52 Convex and discrete geometry」，「68 Computer science」で，他のものの中にも「離散系」に関わるものは多くあります．私がそれらの全てをカバーしているわけではありません．ただ，それらの文献を読む時間があれば，正しさを確認することはできると思います．それは「離散系の話が大体わかる」とは関係なく，論理的に考える能力を鍛えてきたからだと思います (むしろ，数学の論文や書物というのは論理的に考えることができさえすれば理解できるように書かれている必要があるものだと思っています)．
  • 今朝，電通大前の交番近くで，落ち葉に擬態した虫（蛾の一種？）を見かけました．落ち葉が蠢いているので，落ち葉の下に何かいるのかと思ってよく見たら，落ち葉に顔が付いていたのでびっくりしました．
    --結局それは落ち葉ではなかったということですね．;-)

• 2回のレポート課題により評価を行う予定でいます．
• レポート課題1

• こちらをご覧ください

• 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
• Damien Prot, and Odile Bellenguez-Morineau, A Survey on How the Structures of Precedence Constraints May Change the Complexity Class of Scheduling Problems. Journal of Scheduling 21 (2018) 3-16.
  https://doi.org/10.1007/s10951-017-0519-z

• Complexity results for scheduling problems by P. Brucker and S. Knust
• The Scheduling Zoo maintained by Christoph Dürr

• 離散最適化基礎論 (2023年度) テーマ：ネットワークフロー
• 離散最適化基礎論 (2022年度) テーマ：整数計画法
• 離散最適化基礎論 (2021年度) テーマ：グラフの準同型
• 離散最適化基礎論 (2020年度) テーマ：マッチング
• 離散最適化基礎論 (2019年度) テーマ：離散最適化における計算困難性
• 離散最適化基礎論 (2018年度) テーマ：理想グラフに対する組合せ最適化
• 離散最適化基礎論 (2017年度) テーマ：幾何的被覆問題
• 離散最適化基礎論 (2016年度) テーマ：グラフの木分解
• 離散最適化基礎論 (2015年度) テーマ：組合せ最適化におけるマトロイドの役割
• 離散最適化基礎論 (2014年度) テーマ：組合せ最適化における線形計画法の利用
• 離散最適化基礎論 (2013年度) テーマ：局所探索法の理論的側面
• 離散最適化基礎論 (2012年度) テーマ：ゲーム理論における離散構造とアルゴリズム