7

私はインタラクティブなジョブ スケジューリング アプリケーションに取り組んでいます。対応する容量/可用性プロファイルを持つ一連のリソース、これらのリソースで実行される一連のジョブ、およびジョブ シーケンスとジョブの最早/最遅開始/終了時間を決定する一連の制約が与えられた場合、ユーザーが手動で移動できるようにしたい周りの仕事。基本的には、ユーザーがジョブ ネットワークのノードを「つかみ」、制約に違反することなく前後にドラッグできるようにしたいと考えています。

このイメージは、単純な構成例を示しています。最後の三角形のジョブは、すべてのジョブの最終終了時刻を示し、ジョブ間の接続線はジョブに順序を課し、灰色/緑色のバーはリソースの可用性と負荷を示します。

任意のジョブをドラッグして、スケジュールを圧縮できます。能力プロファイルが異なるため、ジョブの長さが変わることに注意してください。

ちょっと機能するアドホックアルゴリズムを実装しました。ただし、失敗していくつかの制約に違反する場合がまだあります。ただし、ジョブ ショップ スケジューリングは、一般的な NP 困難な問題に対する最適な (または適切な) ソリューションを見つけるための多くのアルゴリズムとヒューリスティックを備えた十分に研究された分野であるため、より簡単なサブセットにはソリューションが存在するはずだと考えています。制約プログラミングのトピックや物理ベースのソリューション (静的ジョイントを介して接続された剛体) を調べましたが、これまでのところ適切なものが見つかりませんでした。ポインター/ヒント/ヒント/検索キーワードはありますか?

4

4 に答える 4

1

問題が整数のみを扱っている場合は、MozartOzを確認することを強くお勧めします。Ozは、有限ドメイン制約の仕様、推論、および最適化を優れた方法でサポートしています。あなたの場合、通常、次のことを行います。

  1. 宣言的な方法で制約を指定します。ここでは、すべての変数とそのドメインを指定します（たとえば、V1：1＃100は、V1変数が1〜100の範囲の値を取ることができることを意味します）。一部の変数には直接値が含まれる場合があります（V1：99など）。さらに、変数のすべての制約を指定します。

  2. システムに解決策を求めます。制約を満たす任意の解決策または最適な解決策のいずれかです。次に、このソリューションをUIに表示します。

  3. ユーザーが変数の値を変更したとしましょう。これはタスクの開始時間である可能性があります。これで、ステップ1に進んで、問題をOzソルバーに投稿できます。今回は、すべての変数がすでにインスタンス化されているため、問題の解決には以前ほど時間がかからない可能性があります。

    ユーザーが一貫性のない値を選択した場合があります。その場合、ソルバーはnullを返します。次に、UIを以前のソリューションに移すことができます。

Ozがニーズに合っていて、言語が好きな場合は、ソケットでリッスンするサーバーとして制約ソルバーを作成することをお勧めします。このようにして、UIを含む残りのコードから制約ソルバーを分​​離しておくことができます。

お役に立てれば。

于 2009-12-31T10:23:24.007 に答える
1

いくつかの理由から、制約プログラミングに賛成票を投じます。

1) 制約を満たすスケジュールがない場合、CP はすぐに通知します。

2) ユーザーに実行可能な解決策を最初に提供したいが、解決策を改善するためにジョブを操作できるようにしたいと考えているようです。これもCPが得意です。

3) MILP アプローチは通常、複雑で定式化が難しく、人工的に目的関数を作成する必要があります。

4) 特に経験豊富なプログラマーにとって、CP を習得するのはそれほど難しくありません。実際には、運用研究者 (私のような) よりも、コンピューター サイエンス コミュニティから学ぶことが多いです。

幸運を。

于 2010-02-02T16:32:42.947 に答える
0

Have you considered using an Integer Linear Programming engine (like lp_solve)? It's quite a good fit for scheduling applications.

于 2010-01-26T16:55:49.630 に答える
0

おそらく、Waltz 制約伝播アルゴリズムを変更して制約の変更に対処し、特定のソリューションが有効かどうかをすばやく確認できます。私は手への参照を持っていませんが、これはあなたを正しい方向に向けるかもしれません : d&_docanchor=&view=c&_searchStrId=1102030809&_rerunOrigin=google&_acct=C000043939&_version=1&_urlVersion=0&_userid=809099&md5=696143716f0d363581a1805b34ae32d9

于 2009-11-20T10:56:15.780 に答える