2

私は仕事の影響の問題を解決する必要があり、この問題を解決するためにできれば効率的なアルゴリズムを見つけたいと思います。

いくつかの種類のタスクを実行できるワーカーがいるとしましょう。また、毎週実行する必要のあるタスクのプールもあります。各タスクには時間がかかります。各タスクは誰かが行う必要があります。各労働者は週にNからP時間の間働かなければなりません。

問題のこの最初の部分は、制約プログラミングアルゴリズムの良い候補のようです。

しかし、ここに複雑さがあります。労働者はさまざまなタスクを実行できるため、好み（または希望）もある可能性があります。すべての人のすべての希望を満たしたい場合、問題の解決策はありません（制約が多すぎます）。

したがって、この問題を解決するためのアルゴリズムが必要です。完璧なホイールがすでに存在する場合、私はホイールを再発明したくありません。

アルゴリズムは公平でなければならないので（この単語を定義できる場合）、たとえば、「人ごとに少なくとも1つの願いを満たそうとする」などの制約を追加できるはずです。この問題が、ここで説明されている制約階層メソッドによって解決できるかどうかはわかりません：制約階層。実際、このカテゴリのアルゴリズムの有効な制約によって「公平性」と希望を表現できるかどうかはわかりません。

アドバイスをくれる制約プログラミングの専門家はいますか？効率的なCPアルゴリズムを使用する代わりに、いくつかのヒューリスティックを使用して新しいホイールを開発する必要がありますか？

ありがとう ！

4

4 に答える 4

8

あなたの問題は十分に複雑なので、一般的な解決策はおそらく線形整数問題として定式化する必要があります。一方、特定の要件を緩和できる場合は、より簡単なアプローチを使用できる可能性があります。たとえば、2部マッチングを使用すると、複数のワーカーを複数のジョブにスケジュールでき、設定を処理することもできますが、一般的な「公平性」の制約を適用することはできません。たとえば、この関連するSOの質問を参照してください。頂点カラーリングには、ジョブ分離の制約を適用するための効率的なアルゴリズムがあります。

他のポスターは、シンプレックスとジョブショップのスケジューリングについて言及しています。シンプレックスは最適化アルゴリズムです-それはいくつかの目的関数を最大化しようとしてソリューション空間を横断します。目的関数の定式化は確かに実行できますが、自明ではありません。二部マッチングのような古典的なジョブショップスケジューリングは、問題のいくつかの側面をモデル化できますが、すべてではありません。たとえば、優先順位の制約はありません。タスクに時間制限を設定するなど、いくつかの制約を処理できる拡張バージョンがあります。

既存の実装に興味がある場合は、Pythonnetworkxライブラリにこのマッチングアルゴリズムの実装があります。興味深いかもしれないオープンソースのタイムテーブルプログラムの例はTablixです。

于 2009-08-09T12:10:44.733 に答える
2

制約プログラミングの一形態と見なすことができるタイムテーブルを作成しました。ハード（不可侵）制約とソフト制約（間隔設定など）があります。

線形整数計画法は通常、30を超える変数の後で役に立たなくなります。これは、シンプレックスについても言えます。

解決策が見つかったのは、ヒューリスティックアルゴリズムのドメイン固有の最適化でした。

使用されたヒューリスティックアルゴリズムは、シミュレートされたアニーリング、遺伝的アルゴリズム、メタヒューリスティックアルゴリズムなどでしたが、最終的には、「インテリジェント」ドメインでカスタマイズされた欲張り検索アルゴリズムによって最良の結果が得られました。

基本的に、ここのヒューリスティックの1つで適切な結果が得られる可能性がありますが、主な問題は、問題が過度に制約されている場合に識別できることです。

研究のための優れたオープンソースツールはHeuristicLabです。

于 2009-08-09T12:48:29.580 に答える
2

私はここで提案されたことに同意します。ただし、非常に大きなサイズ（30変数をはるかに超える！）のMIP（混合整数計画問題）は、現在、商用コード（Xpress、Cplex、Gurobi）またはオープンソース（Coin-Or / Cbc）のおかげで実際に解決されています。さらに、OPL Studio、GAMS、AMPL、Flopなどの高度なモデリング言語を使用すると、APIを使用する代わりに数学モデルを簡単に作成できます。

NEOSサーバー（http://neos.mcs.anl.gov/neos/solvers/index.html）を利用して、非常に簡単に異なるMIPを試すことができます。モデルをAMPL形式で送信します。AMPLは無料の限定バージョンとして提供されますが、NEOSは無制限のインスタンスを処理できます。

モデリング言語は、CP（COMET / OPL Studio）およびローカル検索（COMET）にも存在します。

私のウェブサイトwww.rostudel.com（「連絡先」ページ）から私に連絡してください。

デビッド

于 2009-09-21T12:19:01.893 に答える
0

これは、ジョブショップのスケジューリングのように聞こえます。

于 2009-08-09T11:17:29.770 に答える