離散最適化基礎論

岡本 吉央

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

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

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

実施形態

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

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

講義資料

• 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) スケジューリング問題の分類
  • スライド
  • 講義動画

• 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

• 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年度) テーマ：ゲーム理論における離散構造とアルゴリズム