制約付きスケジュール

Question

ジョブストアスケジューリングの問題と同様に制約を使用してタスクをスケジュールしたいので、Microsoft Solver Foundation（C＃を使用する必要があります）のようなものを使用できると考えました。しかし、私が知っている限り、問題を解決するには最適な極小を見つけることができます。私はスケジューリングが総時間に関して最適（できるだけ良い）ではなく、すべての制約が満たされるように近似が必要です。 この問題にアプローチする方法はありますか？

Answer 1

Z3ソルバーを使用することをお勧めします。それはあなたにC＃APIを提供します。基本的には、SMTソルバーであり、与えられた制約に関して「十分に良い」解を探します。 SMTLIB言語で問題を定義するのはかなり難しいかもしれません。

MinizincまたはClingoのソルバーを参照してください。問題の定式化をテキストファイルとして生成し、C＃コードとは別のプロセスとしてソルバーを実行し、出力テキストファイルからソリューションを解析し直してください。

EDIT

スケジュールの長さを最小限に抑えたい場合は、以下の方法を試すことができます。 がの長さのスケジュールKであるとしましょう。あなたの計画の問題はこの仮定の下で充足可能ですか？これを見つけるためにソルバーを呼んでみましょう！異なるKでいくつかの問題を生成し、ソルバーを繰り返し実行します。試行回数を減らすには、バイナリ検索を使用してください。