如何预测异构办公桌排队系统中的等待时间？

Question

我有一个模拟排队系统的系统，它由以下几个要素组成：

• 服务:可以提供给客户的服务。
• 桌子:一种能提供一种或多种服务的桌子。有几张桌子，每一张都可以配置成提供不同的服务子集，无论是否有重叠的办公桌。
• 顾客/入场券:一个顾客进来，打印一张票，说明她需要什么服务。

该系统已经到位，运作良好。这是一个现实世界的系统，门票分销商允许客户请求和打印门票，办公桌客户端应用程序将客户呼叫到办公桌上，并显示显示客户到哪里去。

现在，一种新的需求是一种近似预测队列中任何给定票的等待时间的方法，并在等待时间过高时发出警报。

我们将有一个服务持续时间，将收集从使用统计，为每个服务。

这个预测不需要很精确，目的是让网站管理员快速了解情况，反馈是否一切进展顺利，或者如果顾客在排队，多开一张桌子会更好，或者相反，顾客稀少，办公桌可以关闭。最重要的因素是顾客的等待时间(例如，如果每个顾客在办公桌前等1分钟，就可以有10名顾客等待，但如果这个时间是10分钟，则不是这样！)

问题是，任何办公桌都可以无限制地提供任何服务。因此，给定的服务可以由任意数量的办公桌提供。但反过来，每个服务台都可以提供任意数量的服务。

我尝试过各种方法：

您可以生成一个队列，该队列仅由一个办公桌提供的服务的票证组成。但是，这张单子上的每一张票只要这张桌子就可以“使用”，或者其他5张桌子也可以.

你可以抓起一张票，看看哪些桌子可以服务它，然后抓取所有这些桌子都可以服务的票。同样的问题是，有些票只能由一张桌子来处理，而另一些则由所有的人处理.

我真的不知道从现在开始该怎么解决这个问题。有什么排队模型可以用于这种异构的办公桌吗？有什么办法来建模吗？

Answer 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. 按需要呼叫估计数()

Implementation:

tick()将遍历所有的办公桌，查看哪些已经完成()，并根据当前的政策将票分配给办公桌。通过多次调用抽签()，直到队列为空为止，可以为每种服务类型确定确切的关闭时间--但这会破坏队列，而且应该只在当前队列的克隆()s上执行。

forecast()将克隆队列N次，对于每个克隆队列，在添加模拟票证(用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个模拟中进行平均，从而得出概率预测。