algorithm - 如何预测具有异构 table 的排队系统中的等待时间？

Question

我有一个对一种排队系统进行建模的系统，它由以下元素组成:

• 服务:可以提供给客户的服务
• 办公 table :可以提供一项或多项服务的办公 table 。有几个服务台，每个服务台都可以配置为提供不同的服务子集，服务台之间有或没有重叠
• customers/tickets:一位顾客进来，并打印一张票，指定她需要的服务

系统已经到位并且运行良好。这是一个真实世界的系统，有允许客户请求和打印门票的票务分发器，有桌面客户端应用程序可以将客户调用到服务台，还有可以显示客户去往何处的显示器。

现在一个新的要求是一种方法来大致预测队列中任何给定工单的等待时间，并在等待时间过长时发出警报。

我们将从每项服务的使用统计中收集服务持续时间。

预测不需要非常精确，目标是让网站管理员快速了解情况，反馈是否一切顺利，或者客户是否正在排队，这将是最好多开一张 table ，反之，顾客稀少，可以关闭一张 table 。最重要的因素是客户的等待时间(例如，如果每个客户在办公 table 前停留 1 分钟，则有 10 个客户等待是可以的，但如果此持续时间为 10 分钟，则不行!)。

问题在于任何服务台都可以不受限制地提供任何服务。因此，任何数量的服务台都可以提供给定的服务。但反过来，每个办公 table 可以提供任意数量的服务。

我尝试了各种方法:

您可以生成一个队列，其中仅包含一个服务台可以提供的服务的票证。但是，此列表中的每张票可能仅由该服务台或其他 5 个服务台“服务”...

您可以获取一张票，查看哪些服务台可以为它提供服务，然后获取这些服务台中任何一个服务的所有票。同样，问题是有些门票只能由一组中的一张 table 处理，而其他门票则由所有 table 处理...

我真的不知道如何从这里解决问题。是否有可用于这种异构服务台的任何排队模型？有什么想法可以对此建模吗？

Answer 1

由于您使用算法 标记了问题，并且您是在编程站点(而不是数学或统计站点)中提问，我将从编程的角度来处理这个问题。

型号:

// 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. 创建办公 table 并为其分配服务。
3. 定义您当前的策略，并用它创建一个队列。队列一开始是空的。
4. 随着时间的推移，调用 tick()(并且，如果票进来了，使用 createNow() 将它们 push() 进来)
5. 根据需要调用 estimate()

实现:

tick() 将遍历所有服务台以查看哪些服务台已完成 ()，并根据当前策略将票分配给服务台。通过多次调用 tick() 直到队列为空，可以确定每种服务类型的确切关闭时间——但这会破坏队列，并且它应该只在当前队列的 clone() 上完成.

forecast() 将 clone() 队列 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 次模拟的平均值，以产生概率预测。