1

我有一个系统可以模拟一种排队系统，它由以下元素组成：

  • 服务：可以提供给客户的服务
  • 办公桌：可以提供一项或多项服务的办公桌。有多个服务台，每个服务台都可以配置为提供不同的服务子集，服务台之间有或没有重叠
  • 客户/票：客户进来，并打印一张票，说明她需要哪种服务

该系统已经到位并且工作正常。这是一个真实的系统，票务分销商允许客户请求和打印票，服务台客户端应用程序可以将客户呼叫到服务台，并显示以显示客户去哪里。

现在一个新的要求是一种近似预测队列中任何给定票的等待时间的方法，如果等待时间太长，就会发出警报。

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

预测不需要很精确，目的是让网站管理员快速了解情况，反馈一切是否顺利，或者客户是否在排队等候，打开就好了多一张桌子，或者相反，客户稀缺，一张桌子可能会关闭。最重要的因素是客户的等待时间（例如，如果每个客户在办公桌前停留 1 分钟，则可以让 10 个客户等待，但如果此持续时间为 10 分钟，则不是！）。

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

我尝试了各种方法：

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

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

我真的不知道如何从这里解决这个问题。有没有可用于那种异构办公桌的排队模型？任何想法如何对此建模？

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() 来 push() 他们）
  5. 根据需要调用estimate()

执行：

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

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 次模拟中取平均值，以产生概率预测。

于 2012-08-03T14:51:04.850 回答