問題タブ [resource-scheduling]

オンライン Web プロジェクトの計画には、さまざまな手順があります。

1) 情報アーキテクチャ

• ユーザーストーリーを提供します
• ワイヤーフレームを提供

2) 設計

• ワイヤーフレームを使って素敵なデザインを開発する

3) 開発

4) テスト

アジャイルに取り組むには専任のチームが必要であることを私は知っています。しかし、プロジェクトが終了するまで、専任の IA を持つことは不可能です。プロジェクトは小規模であるため、開発者はさまざまなチームで作業しています。50 の小さなプロジェクトと 20 の新しいプロジェクトが異なるリソースを使用していることがわかっている場合、どのようにリソースを計画しますか?

また、これを支援できる便利なツールはありますか?

私が取り組んでいるソフトウェア アプリケーションは、現在持っているタスクの数に基づいてユーザーのグループにタスクを割り当てることができる必要があります。つまり、タスクが最も少ないユーザーが次のタスクを取得する可能性が最も高くなります。ただし、現在のタスクの負荷は、絶対的な順序の定義ではなく、重み付けとして扱う必要があります。IOW、重み付けされた負荷分散アルゴリズムを実装する必要があります。

次の数のタスクを持つ 5 人のユーザーがいるとします。

A: 4 B: 5 C: 0 D: 7 E: 9

CABDE の順序で次のタスクのユーザーに優先順位を付けたいと考えています。ここで、C は割り当てを取得する可能性が最も高く、E は最も可能性が低いです。ここで注意すべき重要な点が 2 つあります。

• ユーザー数は、2 人から数十人までさまざまです。
• 各ユーザーに割り当てられるタスクの数は、1 から数百までさまざまです。

今のところ、すべてのタスクを同等に扱うことができますが、将来使用できる変数として困難なタスクを含めてもかまいませんが、これは純粋に飾りです。

これまでに思いついたアイデアは、状況によってはあまり良くありません。多数のユーザーがいる場合、ユーザーの重み付けが近すぎる可能性があります。または、ユーザーに現在のタスクがない場合、それらは横ばいになる可能性があります。

Web をいろいろ調べてみましたが、うまくいきませんでした。うまく機能するアルゴリズムの簡単な要約を教えてもらえますか? 実際の実装は必要ありません - その部分は私が行います - 良い説明だけです。代わりに、自由にアクセスできる優れた Web サイトはありますか?

また、私は確かに品質を高く評価していますが、これは統計的に完全である必要はありません. では、上手いけど下手なテクニックがあれば、興味があります！

ここでの私の最初の投稿–しばらくの間検討していたアルゴリズムの設計を手伝ってくれることを願っています–どのアプローチを取るべきかわからない（VRPTWまたはリソーススケジューリングまたは他の何か！？）

実例に言えば、少数の場所（通常は5つ未満）に大量の庭ごみがあります。廃棄物はすべて、所定の時間枠内に他の場所に輸送する必要があります。庭のゴミを移動するために、車で牽引しなければならないトレーラーがあります。庭のゴミは、特定の時間（時間枠）にのみゴミ捨て場に捨てることができます。いくつかの場所では、トレーラーを降ろしてそこにいる人々がいっぱいになるか空にすることができますが、他の場所では、車の運転手が自分でそれをしなければならず、車はそこに留まらなければなりません。すべてのタイミングを計算できます（つまり、ロード/アンロード時間、通過時間など）。車はトレーラーなしでサイト間を移動できます。トレーラーは空に牽引できますが、トレーラーは場所間を移動できません。

私たちの目的は、トレーラーに積まれたすべての廃棄物が輸送されていることを確認することです。

• 使用中のトレーラーと車の数を最小限に抑える
• 廃棄物を落とすためのすべての時間枠を満たす
• トレーラーの「バランスをとる」–つまり、1日の終わりには、1日の始まりにあったのと同じ数のトレーラーが各場所にあります。

これをリソーススケジューリングアルゴリズムとしてアプローチすることを考えましたが、トレーラーの「バランシング」をどのように処理するかがわかりません。

私が考えたもう1つの方法は、最初に車を検討することでした。次に、最も早いタスクを選択し、その後に実行可能なすべてのタスクのグラフを作成できます。次に、トレーラーの最大積載数に対応するグラフの最長パスを選択した場合。次に、これらのタスクをタスクのリストから削除し、すべてのタスクが処理されるまで繰り返すことができます。次に、これらのトレーラーの負荷のリストを調べて、必要なトレーラーの数を計算する必要があります。

アプローチについての考えはありがたいです！

ここでできる限り検索しましたが、関連する質問がいくつか見つかりましたが、目前の質問をカバーしているとは思いません。

1 つのリソースと、タスクをスケジュールするための既知の要求リストがあるとします。各リクエストには、start_after、start_by、expected_duration、および action が含まれます。

目標は、各タスクのスケジュールを start_after から start_by の間に保ちながら、できるだけ早く実行するようにタスクをスケジュールすることです。

動作するはずだと「思った」簡単な Prolog の例をコーディングしましたが、残念ながら実行時にエラーが発生しました: ">=/2: 引数が十分にインスタンス化されていません".

どんな助けやアドバイスも大歓迎です

編集: 競合の目標が正しくありませんでした: 追加の T>T1 句が必要でした。

編集: 有効な Request,Time ペアを指定すると、スケジュールの目標が機能するようですが、R1..3 が指定されたときに Prolog に T1..3 の有効な値を強制的に見つけさせようとして行き詰まりましたか?

NP困難/NP完全であるいくつかのスケジューリング問題があることを私は知っています...しかし、それらのどれもこの状況がNPでもあることを示すような方法で述べられていません。

startAfter、startBy、durationに制約された一連のタスクがあり、すべてが単一のリソースを使用しようとしている場合...スケジュールを解決するか、徹底的な検索なしでは解決できないことを特定できますか？

答えが「申し訳ありませんが、これはNP完全です」の場合、使用するのに最適なヒューリスティックは何でしょうか。また、a）スケジュールを解決し、b）解決できないものを特定するのにかかる時間を短縮する方法はありますか。スケジュール。

「最小ウィンドウファースト」ヒューリスティックを実装する再帰を通じて、基本的な競合解決の目標を（プロローグで）実装しました。これは実際にはかなり迅速に解決策を見つけますが、無効なスケジュールを見つけるのは非常に遅いです。これを克服する方法はありますか？

複雑な質問にイェーイ！

私は、ユーザーが毎日のスケジュールを最適化できる Java アプリケーションに取り組んでいます。そのためには、次の点に注意して「タスク」の最適な時間を計算するのに役立つフレームワークが必要です。

1. 必要なリソースとリソースの使用制限
2. タスク間の依存関係 (ただし、F->S 関係のみで実行できます)
3. 最早および最遅の始業時間、余裕時間
4. ベースラインと実際の時間 - 実際の開始時間と終了時間を報告し、それに応じて残りのタスクを更新できます

いくつかの明確化: 私は、これらのガントを描画するためのフレームワークも、1 つの特定の問題ドメイン (教室など) を処理するフレームワークも、スレッド スケジューリングを処理するフレームワークも探していません。

ありがとう！

グリッド環境でスケジューリングをシミュレートしようとしています。どのアルゴリズムを使用すればよいかわかりません。Job Shop Scheduling アルゴリズムhttp://en.wikipedia.org/wiki/Job_shop_schedulingを検討していますが、グリッドで使用されるかどうかはわかりません。受信ジョブをリソースにスケジューリングするためにグリッド環境で通常使用されるアルゴリズムは? どんな助けでも大歓迎です。ありがとう。

リソースのレッドカラント予約を可能にするプロジェクトまたはサードパーティ コンポーネントを探しています。

たとえば、毎週木曜日に会議室 A が空いているときにのみ会議室 A で開催する必要がある会議があるとします。会議の長さは 1 時間で、会議室の空き状況に応じて、午前 9 時から午後 4 時の間に開始できます。

この機能にアプローチするソフトウェアへのポインタは大歓迎です。

変数classes（〜100）、rooms（20）、terms（8）、およびweekdays（5）で構成される古典的なタイムテーブルの問題があります。

問題を単純化するために、以下に制約を減らします。

1日は9時間です。

一部のクラスは学生に必須であり、用語1、3、5、7（および2、4、6、8）の必須クラスは互いに重複してはなりません。

クラスの重みは時間で異なり、2時間のものもあれば、3時間のものもあります。

一部のクラスは特定の部屋で行う必要があります。

同じクラスで同時に2つの講義を行うことはできません。

logilabspython制約モジュールを使用します。また、変数とドメインを適切に選択すると、問題を解決するための時間が短縮されることを認識しています。問題は、これまで制約プログラミングを行ったことがなく、どこから何から始めればよいかを見つけるために問題を構築するのに苦労していることです。例えば：

「同じ部屋に2つのクラスがなく、同じ日にお互いの時間枠が重なることはありません」などの制約を設定できます。または、「同じ日に9時間以上予約できる部屋はない」から始めて、ソリューションドメインを減らして続行します。私は、最初の制約が他の制約よりも解決にはるかに長い時間がかかると見積もっています（試していませんでした）。しかし、それはまた（私が推測する）変数とソリューションドメインの変更またはより小さな問題の再構築を必要とします。私はすでに変数、ドメイン、間隔、実装などで少し迷っています。

簡単に言えば、問題を構築するためのいくつかのポインタ、ソリューションドメイン、変数の賢明な選択などが必要です。

ありがとう

アップデート

logilab-constraintパッケージを使用して、基本的なアプリケーションを作成し、それをgithubにアップロードしました

多目的計画問題を含む論文プロジェクトで考えられる研究トピックを調査していますが、そのような問題をグラフで表現するアイデアを誰かが持っているのではないかと思います。私はこの主題に関するいくつかの文献を見てきましたが、一般的なアプローチは、単一のコスト数ではなく、エッジでコストベクトルを使用することのようです。これは私には理にかなっていますが、問題の特定の側面をこのようにモデル化する方法がわかりません。

特に、モデルには各アクティビティを特定の時間枠に制約するリソースがあり、有効なスケジュールはこれらの制約内で各アクティビティをスケジュールする必要があります。さらに、相互に依存している一連のアクティビティがあります。たとえば、ユーザーは2つのアクティビティの間にタイムデルタ要件を設定して、互いにいくつかの時間単位内でスケジュールする必要がある、または有効なスケジュールで少なくともいくつかの時間単位離れている必要があると言うことができます。これらをコストベクトルのオプション要素としてモデル化することを想像できますが、より良い方法はありますか？

ボーナスの質問は、これも最小コミットメントスケジューラであると想定されていることです。各アクティビティには、名目上n時間単位の長さのウィンドウを指定する必要があるため、アクティビティの全順序が必ずしも必要ではありません。

このような問題を表現するための文献は大歓迎です！