1

私は、これらの要素で構成される一種のキューイングシステムをモデル化するシステムを持っています:

  • サービス:顧客に提供できるサービス
  • デスク:1つ以上のサービスを提供できるデスク。いくつかのデスクがあり、それぞれがデスク間のオーバーラップの有無にかかわらず、サービスの異なるサブセットを提供するように構成できます。
  • 顧客/チケット:顧客が入ってきて、必要なサービスを指定するチケットを印刷します

システムはすでに設置されており、正常に動作しています。これは、顧客がチケットを要求して印刷できるチケットディストリビューター、顧客をデスクに呼び出すデスククライアントアプリ、および顧客がどこに行くかを示すディスプレイを備えた実際のシステムです。

現在、新しい要件は、キュー内の特定のチケットの待機時間を概算し、この待機時間が長くなりすぎた場合にアラームを発生させる方法です。

サービスごとに、使用統計から収集されるサービス期間があります。

予測は非常に正確である必要はありません。目標は、サイトの管理者に状況の迅速な見通し、すべてがスムーズに流れているかどうか、または顧客がキューに蓄積されているかどうかをフィードバックすることです。もう1つのデスク、または逆に、顧客が不足していて、デスクが閉鎖される可能性があります。最も重要な要素は、顧客の待ち時間です(たとえば、各顧客が1分間デスクにいる場合は、10人の顧客が待機していても問題ありませんが、この期間が10分である場合はそうではありません)。

問題は、どのデスクでも制限なしにあらゆるサービスを提供できることです。したがって、特定のサービスは、任意の数のデスクで提供できます。しかし、順番に、各デスクは任意の数のサービスを提供できます。

私はさまざまなアプローチを試しました:

1つのデスクで提供できるサービスのチケットのみで構成されるキューを生成できます。しかし、このリストの各チケットは、このデスクだけで、または他の5つのデスクでも「サービス可能」である可能性があります...

チケットを取得して、どのデスクがサービスを受けやすいかを確認し、これらのデスクのいずれかでサービスできるすべてのチケットを取得できます。繰り返しますが、問題は、一部のチケットはセット内の1つのデスクでしか処理できず、他のチケットはすべてのデスクで処理できることです...

ここからどうやって問題に取り組むのか本当にわかりません。そのような異種のデスクに使用できるキューイングモデルはありますか?これをモデル化する方法はありますか?

4

1 に答える 1

1

質問に。のタグを付けておりalgorithm、(数学や統計のサイトではなく)プログラミングサイトで質問しているので、プログラミングの観点からこれにアプローチします。

モデル:

// creates a new ticket for a given service; arrival time and length are only known
// for generated tickets
class Ticket(int arrival, int length, Service s)

// an abstract distribution (parameters are distribution-dependent)
class Distribution(...) 
      int generate() // generates integer with this distribution

// a service, with a distributions of time-to-finish and time-between-arrivals 
//    (both set experimentally from historical data).
class Service(Distribution lengths, Distribution arrivals)
      // simulated ticket: length from lengths.generate(), 
      //     arrival from t + arrivals.generate();
      Ticket createFuture(int t)  
      // same as above, but arrival = t+0
      Ticket createNow(int t)

// a desk, offers one or more services
class Desk() 
      void addService(Service s) // allows this desk to attend this service
      void removeService(Service s) 
      bool isCompatible(Service s) // is this desk compatible with this service?
      void attend(Ticket t) // marks a desk as attending a service
      bool isFree() // returns true if the desk is not attending anyone
      // returns a finished ticket, if any. After this, isFree() will return true
      Ticket finished() 

// a policy which assigns tickets to desks. Implement your current one (probably "FIFO") 
class Policy()
      // returns a suitable desk for that ticket, or null if none is posible/desired
      Desk assign(Ticket t, Ticket[] pending, Desk[] deks) 

// a live queue of tickets, dispatched using policy p t
class Queue(int startTime, Policy p, Service[] ss, Desk[] ds)
      void push(Ticket t) // adds a new real ticket to the queue
      // estimates wait-times for new arrivals to all services at time 't'
      Map<Service, int> forecast(int t) 
      void tick() // advances time for this queue
      Queue clone(); // deep-clones the queue (including time, policy, desks, and services)

使用法:

  1. サービスを定義し、その到着をモデル化します。
  2. デスクを作成し、それらにサービスを割り当てます。
  3. 現在のポリシーを定義し、それを使用してキューを作成します。キューは空で始まります。
  4. 時間の経過とともに、tick()を呼び出します(チケットが入ってくる場合は、createNow()を使用してそれらをプッシュ()します)
  5. 必要に応じてestimate()を呼び出します

実装:

tick()は、すべてのデスクを反復処理して、どのデスクが終了したかを確認し、現在のポリシーに従ってデスクにチケットを割り当てます。キューが空になるまでtick()を数回呼び出すことにより、サービスタイプごとに正確なクローズまでの時間を決定できますが、これによりキューが破棄されるため、現在のキューのclone()でのみ実行する必要があります。 。

Forecast()はキューをN回clone()し、クローン化されたキューごとに、シミュレートされたチケット(createFuture()で生成)を追加しながら、時間を「now-t」時間進めます。createFutureの時間を次のように連鎖させる必要があります。

// create 3 future tickets for service s
Ticket t1 = s.createFuture(now);
Ticket t2 = s.createFuture(t1.arrival);
Ticket t3 = s.createFuture(t2.arrival);
//...

シミュレートされたチケットは、シミュレートされた時間がシミュレートされた到着時間に達した場合にのみ、実際のキューにプッシュされます。シミュレートされた時間が「now+t」に達すると、実際のサービスレイテンシが決定され、N回のシミュレーションすべてで平均化されて、確率的な予測が得られます。

于 2012-08-03T14:51:04.850 に答える