問題タブ [resource-scheduling]

重み付けされた間隔のスケジューリング問題では、各間隔が連続した範囲を表す間隔 のシーケンスがあります (私の場合、非負の整数の範囲; たとえば)。通常の目標は、各間隔の重みをその幅に等しく設定し、合計重みが最大になる重複しない間隔のサブセットを決定することです。私が提供したリンクで優れた解決策が提供されています。{i_1, i_2, ..., i_n}i_xi_x = [5,9)

特定のリンクで提供されているアルゴリズムから始めて、ソリューションを C++ で実装しました ( GitHub リポジトリのPython で記述されています。

ただし、指定されたリンクでの現在のソリューション (および私がそれについて議論した他のすべての場所) は、単一の最大フィットをキャプチャする方法のみを提供します。もちろん、場合によっては、複数の最大適合があり、それぞれが同じ合計 (全体的な最大) 重みを持つ場合があります。

以下で説明するように、すべての最大適合をキャプチャするための「ブルート フォース」アプローチを実装しました。

ただし、私が使用したブルート フォース アプローチの具体的な詳細について説明する前に、解決したい私のブルート フォース アプローチの重要な問題は、私のブルート フォース アプローチが、真の最大適合に加えて、多くの偽陽性を捕捉することです。 . 次の質問に答えることができれば、私のブルート フォース アプローチの詳細を掘り下げる必要はありません。

1 つの最大適合だけでなく、すべての最大適合をキャプチャすることをサポートする基本的なO(n log(n))ソリューションに対する最も効率的な拡張機能 (または) を知りたいです(ただし、誰かが偽陽性を回避する方法に答えることができれば、それも私を満足させます) ）。

私はこれについて何の進歩も遂げていません.私が使用している力ずくのアプローチは、数千を超える（おそらくそれ以下の）最大適合がある場合に、手に負えないほど爆発し始めます.

ありがとうございました！

私が使用しているブルートフォースアプローチの詳細は、興味があるか有用な場合にのみ:

上記でリンクした既存のソース コードには、すべての最大適合をキャプチャできるパスをたどるのではなく、アルゴリズムが 1つの最大適合を選択するという事実に関与する 1 行のコードがあります。 ここをクリックして、そのコード行を確認してください。 ここにあります：

>(大なり記号)に注意してください。このコード行は、特定のサブ問題の他の間隔の組み合わせよりも高い合計重みを持つ間隔の組み合わせが保持されることを正常に保証します。に変更>すること>=で、検討中の現在の間隔セットの合計重みが以前の最大の合計重みと等しいシナリオをキャプチャできます。これにより、すべての最大適合をキャプチャできるようになります。このシナリオを捉えたいので、私の C++ 移行では を使用し、>=等号が成り立つ場合は、再帰的な関数呼び出しを介してフォーク内の両方のパスを進みます。

以下は、サブ問題ごとにすべての最適な間隔セット (および重み)を取得する (重要な) 関数の C++ コードです (サブ問題が問題全体に対応する最後のインデックスで最終的な解が得られることに注意してください)。

はすべての潜在的な解 (最大間隔セット)の でOPTsあることに注意してくださいlist(つまり、 の各要素自体が、間隔のセットとすべての副問題の対応する重みでOPTs構成されるすべての副問題の単一の完全な解です) 。単一のそのような完全なソリューションを記述するために使用されます - それを構築するために使用されるすべての間隔での潜在的な最大適合、各サブ問題に対して1つ。OPT

上で示した重み付きインターバル スケジューリング問題の標準的な解決策の場合、得られる解決策はOPT(リストではなく 1 つのみ) だけです。

以下のコードのRangeElement型は、私が議論している問題とは関係のない単純なメタデータです。

RangesVec問題への入力である間隔のセットが含まれています (終了値で適切にソートされています)。 上記のリンクで説明されているPreviousIntervalVecものに対応します。compute_previous_intervals

(注: 上にリンクされた Python コードを見ている人は、最大セットで間隔を保存することに関連するバグを見つけたと思うことに注意してください。このバグに関するコメントについては、こちらを参照してください。以下の私の C++ コードで修正されました。)

これは、すべての最大適合をキャプチャする私の「ブルートフォース」実装です。 私のブルート フォース アプローチは、最後に削除する必要があるいくつかの誤検知もキャプチャします。誤検知を除外するための最も効率的なアプローチを提供するが、それ以外の場合は以下のアルゴリズムと同等のアルゴリズムを使用する回答に満足します。

現在優先 FIFO スケジューリング アルゴリズムを使用しているエンタープライズ BI システムをクリーンアップしようとしています (したがって、火曜日の優先度 4 のレポートは、木曜日の優先度 4 のレポートと月曜日の優先度 3 のレポートの前に実行されます。) 追加の詳細:

• キューが空になることはなく、ジョブは常に追加されています
• ジョブの実行時間は、1 分未満から 24 時間以上の範囲です
• ジョブを実行するために使用される 40 の奇数の同一のアプリ サーバーがあります。

優先度に関するハード ルールとキュー内の平均時間に関するいくつかのソフト ルールを使用して、このシナリオで optaPlanner を起動して実行できると思います。私はスケジューリングの最適化に慣れていないので、この状況で optaPlanner が役立つかどうかを判断するには、何を調べればよいのでしょうか?

SWI プロローグと CLP でプロジェクトのスケジューリングを試みています。順次依存関係をサポートすることはできましたが、二重予約の人を避けるのに苦労しています。

[taskname, starttime] のような要素を含む Schedule というリストがあります。ここで、starttime は制約ソルバーの自由変数です。それらは、シーケンシャルな依存関係によって既に制約されています。

二重予約を排除するために、次のようなループを作成しようとしています。

foreach では常に失敗し、forall では何も制約することなく常に成功します。

このループに関する限り、Schedule はグローバルであり、その目的は、シリアル化を使用して starttime 要素を制約することです。OTOH、HisSchedule、Sts、Dus は人によって異なります。ですから、Schedule を幸せにするためには foreach が必要だと思いますが、HisSchedule などを幸せにするためには forall が必要だと思います。それが問題ですか？もしそうなら、どうすれば修正できますか？

私はルート最適化の初心者であり、jsprit を使用して次のビジネス要件を解決するための助けをいただければ幸いです。jsprit の基本を学ぶのに役立つ Stefan Schröder からフィードバックをもらいました。最初にビジネス要件を説明し、その後いくつか質問をします。

目的は、1 か月で完了する必要があるメンテナンス ジョブのリストをスケジュールすることです。1 か月分の毎日のスケジュールを作成する必要があります。ここでの目的は、1 日あたり最大数のジョブを実行することです。

• リージョンごとに 4 つのデポがあります
• 各地域には約 70 の倉庫があり、合計で 300 の倉庫があります。
• その地域内の各デポと倉庫の間の距離がわかっている
• 地域ごとに異なるタイプの車両が 3 ～ 4 台、合計 12 台あります。
• 地域内の車両は、その地域内の倉庫にのみサービスを提供できます
• 地域内の車両には、たまたま終点となる同じ始点があります
• 車両には、容量、集荷、または配送の要件はありません
• 車両は、保守作業を行う作業員の輸送にのみ使用されます
• 各車両の平均速度がわかります
• 約80のメンテナンスジョブタイプがあります
• 各ジョブ タイプの既知の所要時間 (分単位)
• メンテナンス ジョブは特定の時間に開始する必要はありません
• 毎月、実行する必要がある約 200 のメンテナンス ジョブがあります。
• これらのジョブは、どの倉庫でも可能です
• 同じ日または別の日に同じ倉庫で複数のジョブが発生する可能性があります
• 1 日 8 時間のシフトが 3 回あります。午前6時～午後2時、午後2時～午後10時、午後10時～午前6時
• 車両は、シフトの開始時にデポ倉庫を出発し、8 時間のシフト内でできるだけ多くの倉庫を訪問します。
• 次の倉庫に移動するか、デポ倉庫に戻る前に、ジョブが実行されている間、車両は倉庫で待機する必要があります。

私の基本的な理解は、保守作業は jsprit でサービスとして定義でき、車両ごとに開始/返却時間を設定できるということです。また、コスト マトリックスを使用して、車両と倉庫の関係に時間と距離を追加することもできます。私が持っている質問は次のとおりです。

1. 各メンテナンス ジョブはサービスとして定義する必要があります。その結果、VRP ソルバーに渡されるサービス オブジェクトが 200 になりますよね?
2. VehicleTypeImpl には、addCapacityDimension()、setCostPerDistance()、および setCostPerTime() メソッドがあります。これらは正確には何であり、上記のケースをどのように適用しますか?
3. Service.Builder には addSizeDimension() メソッドがあります。それは何をするためのものか？
4. costMatrixBuilder には、TransportDistance と TransportTime を追加するメソッドがあります。これらのメソッドで使用される単位と、それらをどのように使用できますか?
5. デポごとに Coordinate を定義し、VehicleImpl ごとに setStartLocationCoordinate() メソッドに渡す必要があります。これは正しいですか？
6. vehicleBuilder には setLatestArrival( double maxDuration); があります。ここで使われているユニットは？

上記のケースを解決するための助けに感謝します。

ありがとう、アダム

EDIT1：

いくつかの質問

A. setEarliestStart() および setLatestArrival() メソッドは double 値を受け入れますが、これらのメソッドに実際の日付として最も早い出発と最も遅い到着を指定するにはどうすればよいですか? たとえば、開始時刻は 2014 年 11 月 28 日の午後 2 時で、終了時刻は同日の午後 10 時です。

B. サービス時間を分単位で指定する方法はありますか?

C. VehicleTypeImpl.Builder.setMaxVelocity(double inMeterPerSeconds) メソッドは最大速度を想定していますが、車両の平均速度を指定する方法はありますか?

D. すべての車両は 3 シフトで作業する必要があります。これは、同じ車両を 3 回定義する必要があるということですか? シフトごとに 1 つずつ、さまざまな最早出発時刻と最遅到着時刻を指定します。

E. ジョブは月のいつでも実行できるため、各ジョブの時間枠は月の始まりと終わりとして Service.Builder.setTimeWindow() メソッドに渡されますか?

これが私が解決しようとしている問題です：

• 場所 (x,y) に患者がいる町があり、患者が死ぬ時間があります。
• 患者は、救助されるために死ぬ前に病院に到着する必要があります。
• (x,y) にある一連の病院と、1 回の旅行で最大 4 人の患者を搬送し、任意の病院に搬送できる救急車がいくつかあります。
• 救急車は病院から出発し、複数回の移動を経て、最終的にどの病院にも行き着く可能性があります。
• できる限り多くの患者を救うことになっています。
• 問題の完全な説明はこちら: http://cs.nyu.edu/courses/fall15/CSCI-GA.2965-001/ambulance.html

この問題を解決するためにjspritを使用しようとしていますが、次のことを行う方法がわかりません: (API のどの部分を調べる必要があるか知りたい)

1) 救急車の数は限られているが、複数回の移動が可能であることを指定します。

• VehicleRoutingProblem.Builder.setFleetSize(FleetSize.INFINITE) を設定すると、これが行われますか? コードは正確な機能を文書化していません。

2) 患者が死ぬ前に病院に運ばれるように拘束する、または患者を離れる。

• Shipment.Builder.newInstance("...").setDeliveryTimeWindow(time_of_patient_dying) はこれを達成しますか?

3) 救急車が配達のために病院に到着するための 1 分間の荷降ろし時間を追加します。

• これについては、API のどの部分を確認すればよいかわかりません。

4) 救急車が患者を任意の病院に搬送できるようにすることで、より適切なルートを選択できるようにします。

• これについては、API のどの部分を確認すればよいかわかりません。

これまでの私のコードは次のとおりです。