プロジェクト管理の話でクリティカルパスという話は絶対出て来る.
でもクリティカルパスを導くためのタスクの順番をどうやって決めるか,という問題には大抵触れられていない.
一般的な解説ページなどでは,タスク数は高々10個程度.だから人間が適当に作ってもだいたい最適なスケジュールが組める.でももっとタスクが増えて依存関係が増えたら難しい.一時間費やしてスケジュール組みましたみたいな本末転倒なことが起こり得る.
完了時刻和最小化スケジューリング問題を発展させて,タスクの依存関係や各タスクの必要人員を考慮した予定組みってできないだろうか.NP困難臭がすごいけど.
応用先が広そうだし,組み合わせ最適化とかグラフ理論とか詳しく学びたい
http://dopal.cs.uec.ac.jp/okamotoy/lect/2013/localsearch/lect01.pdf