NP困難/NP完全であるいくつかのスケジューリング問題があることを私は知っています...しかし、それらのどれもこの状況がNPでもあることを示すような方法で述べられていません。
startAfter、startBy、durationに制約された一連のタスクがあり、すべてが単一のリソースを使用しようとしている場合...スケジュールを解決するか、徹底的な検索なしでは解決できないことを特定できますか？
答えが「申し訳ありませんが、これはNP完全です」の場合、使用するのに最適なヒューリスティックは何でしょうか。また、a）スケジュールを解決し、b）解決できないものを特定するのにかかる時間を短縮する方法はありますか。スケジュール。
「最小ウィンドウファースト」ヒューリスティックを実装する再帰を通じて、基本的な競合解決の目標を（プロローグで）実装しました。これは実際にはかなり迅速に解決策を見つけますが、無効なスケジュールを見つけるのは非常に遅いです。これを克服する方法はありますか？
複雑な質問にイェーイ！
実生活でのほとんどのスケジューリング問題の最も難しい部分は、信頼性と制約の完全なセットを手に入れることです。大学のタイムテーブルを作成する例をとると、次のようになります。
次に、変更に対応できるスケジュールシステムが必要です。そのため、直前に1つの制約が変更された場合でも、完全な時刻表を変更する必要はありません。
上記のすべては、スケジューリングシステムに関する研究論文では通常無視されます。与えられたスケジューリング問題のNP完全性に関しては、実際には、NP完全でなくても、「最良の解決策」が何であるかを定義することさえできないので、十分に良いので十分です。
始めるのに役立つ可能性のある論文のリストについては、http：//www.asap.cs.nott.ac.uk/watt/resources/university.htmlを参照してください。スケジューリングソフトウェアにはまだ多くのPHDがあります。
スケジューリングのようなNP困難/完全な最適化問題には、多くの場合、優れた近似アルゴリズムがあります。Ahmed Abu Safiaによる、スケジューリングまたはさまざまな論文の近似アルゴリズムに関するコースノートをざっと読むことができます。
ある意味で、すべての公開鍵暗号化は、部分的に因数分解するなどの「それほど難しくない」問題で行われます。これは、NP困難な問題では簡単なケースが多すぎるためです。それらを「道徳的に困難」にするのと同じNP完全性であり、非常に多くの簡単な問題を引き起こします。これは、多くの場合、最適の誤差範囲内にあります。
ただし、近似アルゴリズムの制限について説明している、近似の硬さに関するより深い理論があります。
動的計画法を使用して、これらの問題のいくつかを解決できます。欲張りアルゴリズムも思い浮かびます。スケジューリング理論は深くて美しいですが、私が見つけたこれら2つは、私が直面した問題のほとんどを解決します。たぶん私は幸運でした。
startByとはどういう意味ですか？
startAfterを使用し、リソースが1つしかない場合、トポロジカルソートを使用するのが迅速な解決策になる可能性があります。アルゴリズムの例は線形時間で実行されますが、グラフにサイクルが含まれている場合のエラーケースは含まれていません。
これはそうではないものです。
平均待機時間が最小になるように、それぞれが時間t（i）を要する単一のマシンで一連のジョブi = 1,2...nをスケジュールします。
解決策：t（i）の昇順で並べ替えます。O（n log n）
ここに良いリスト
クラスPにあるスケジューリングの問題を考えてみましょう。
入力：開始時刻と終了時刻を含むアクティビティのリスト。
終了時間で並べ替えます。
このソートされたリストの最初のN個の要素を選択して、特定の時間にスケジュールできるアクティビティの最大量を見つけます。
次のような警告を追加できます。すべてのアクティビティは午後5時に終了する必要があります。この場合、リストを確認しながら、この時間の後に終了するアクティビティに到達したら停止します。