ルビー/レールでのアポイントメントスケジューリング

Question

私はレールでコールセンターソフトウェアを開発しており、顧客向けのコールを処理できるエージェントのアポイントをスケジュールする必要があります。コールセンターのソフトウェアを話したら、できるだけエージェントのスケジュール全体を利用してアポイントをスケジュールし、最低限のホール（エージェントにはアポイントがない）のスコープを残しておく必要があります。

午後1時から午後1時30分までの昼休み30分の午前9時から午後5時30分までのエージェントのスケジュールを指定すると、約60分、約90分です。

何らかの理由で昼休みがスケジュールに穴が残っていると、昼休み30分+/-を移動できるはずですので、午後1時から午後1時30分ではなく午後1時30分 - 2:00 PMまたは12:30 PM - 1:00 PM。

私は、ランチブレイクを開始して、starts_at属性とfinishes_at属性を柔軟に移動できるようにする予定でした。そして、任命は30分の倍数であり、昼食も30分である60分か90分のいずれかであるので、私は30分のスロットにエージェントのスケジュールを分割し始めました。

私は自分のスケジュールを見て、それぞれのエージェントのスケジュールを見て、それぞれ30分の長さのスロットをインスタンス化し、starts_atとfinish_att属性は午前9時〜午前9時30分、 10:00 AMなど

私は、この予約スロットの配列をループし、60または90分間の予定に応じて2つの連続するスロットまたは3つの連続するスロットをプルするのに役立つ必要があります。ランチ+/- 30分を移動します。

ご迷惑をおかけして申し訳ありません。

Answer 1

あなたの問題を見て：

1. 予定はどちらか60か90分の長さです。私たちは何の予定を持っていない分の量を最小限に抑えたい

00：30-2：12 90分間隔の間

ランチは変えることができます。

ここでは、午前9時から午後5時30分までの入力間隔があります。予定が9：00〜5：30の間であると仮定すると、最も早い終了時間（source）に基づく間隔スケジューリングのための欲張りアルゴリズムを追加の制約で使用することができます。

（擬似的に）次のように基本的なアルゴリズムである

Let R be the set of all appointments 
Let R11 be the set of appointments from R before 12:30 that are compatible with 12:30-1:00 and R12 be the set of appointments from R after 1:00 that are compatible with 12:30-1:00 
Let R21 be the set of appointments from R before 1:00 that are compatible with 1:00-1:30 and R22 be the set of appointments from R after 1:30 that are compatible with 1:00-1:30 
Let R31 be the set of appointments from R before 1:30 that are compatible with 1:30-2:00 and R32 be the set of appointments from R after 2:00 that are compatible with 1:30-2:00 

Let R1Comb = findSet(R11) + 12:30-1:00 + findSet(R12) 
Let R2Comb = findSet(R21) + 1:00-1:30 + findSet(R22) 
Let R3Comb = findSet(R31) + 1:30-2:00 + findSet(R32) 

Function findSet(R) 
    Let A be the time interval to fill  
    While R is not empty 
     Choose a request r in R that has the smallest finishes_at 
     Add r to A 
     Remove all appointments in R that are not compatible with r 
    EndWhile 
    Return A 
EndFunction 

Return the R that has the smallest amount of holes in R1Comb, R2Comb, R3Comb 

このアルゴリズムは、それらが重複する場合、いくつかの概念

1. 予定R1の使用はR2と互換性がないことができます。
2. ＃1のため、i = 1,2,3のRi1/Ri2は互いに競合しないことがわかります。 Ri2の予定がRi1と互換性がない場合は、昼食期間と互換性がないため、互換性のない予定をすべて取り除いたため、矛盾します。
3. 一度アポイントを分割すると、2つのスケジューリング問題を解決することができます。これは貪欲に解決できます。

このアルゴリズムは、欲張りアルゴリズムを6回（定数）実行し、各欲張り反復がO（n log n）であるため、依然としてO（n log n）であり、最初の数行と最後の行はすべてO（n）です。

人々は予定に論文を書きますが、それは簡単な問題ではありません。私はより良い理解を得るためにあなたがhttp://www.asap.cs.nott.ac.uk/watt/resources/university.htmlを見てお勧めします。

幸運：