0
$\begingroup$

I want to develop an algorithm to serve the queue of children queueing to a basket full of balls of different colour, where each ball can be painted within a known time any colour (of several colours offered) requested by the child, and any child would eventually return a ball back to the basket after he/she finished playing with it. Painting of several different balls can happen in parallel.

To me this looks like a scheduling algorithm to serve a queue of requests to access one resource within a shared fixed-size resource pool, where each resource takes some time to prepare. Here are the requirements it should satisfy:

  • resources can belong to one of several classes (number of classes is low and fixed), each class takes a different (known and fixed) time to prepare;
  • each customer only requests one resource of a specified class;
  • we have visibility to the customers' requests for the entire queue, not just its head, i.e. we can see all requested classes before the customer starts being served;
  • resource preparation can happen on demand, when customers arrive to the queue, as well as in advance, when we see the growing queue and want to "guess" what kind of resource future customers would want;
  • the maximum number of resource preparation activities we can run in parallel is the same as the pool size;
  • we want to maximise the queue throughput.

On the first glance, this looks like something we can address using the queuing theory for queues with multiple servers (due to our capacity to prepare several resources in parallel) and work-independent service times. The difference I see here is that each customer eventually returns resource it has obtained from the pool back to the pool. Returned resource can either:

  • be immediately served to a waiting customer, if the class of resource is what a waiting customer wants; or
  • be placed back to the pool (hoping we would soon get a customer that would want that resource class), therefore reducing pool's capacity for resources of other classes; or
  • be converted into another class: this is possible and takes same time it would take to prepare resource of that other class.

If we would know the distribution of time it takes each customer to return its resource back to the pool, can we still model this as a queue with multiple servers? How would this affect the distribution of the serving time? Or maybe there's another model describing what I want? Any help or pointers would be appreciated.

$\endgroup$
  • $\begingroup$ Questions: Is there a fixed number of children? Having returned one ball, does a child ask for another?: immediately, or after a delay? Are the arrival times random (well, Poisson in any interval)? This is awful like a number of processes queuing for different resources of a computer system: file, network, processor. Except here we are allowed to move resources from one kind to another. Interesting! $\endgroup$ – Thumbnail Jul 12 '17 at 13:55
  • $\begingroup$ Arrival times are Poisson. For colour preferences we can try coming up with a distribution (i.e. one colour is twice as popular as others, all others are equally popular). We can consider that children have an upper bound on their number, but this seems irrelevant, because after a child finished playing, it may re-join the queue with a probability that won't skew the queue's distribution. $\endgroup$ – Sergey Mikhanov Jul 12 '17 at 14:09
  • $\begingroup$ You can get equilibrium solutions for a fixed number of children and a fixed ball population by using the techniques of Buzen. Though these are formulated for exponential service-time distribution, I think they extend to any Erlangian STD, including constant service time. $\endgroup$ – Thumbnail Jul 12 '17 at 16:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.