0
$\begingroup$

The goal of the model is to predict progression in position in a FIFO queue, given our current position and other predictor variables. This is progression in the sense that the number ahead of us in the queue has decreased. We are effectively discretizing the problem by making predictions over short time horizons, but the raw data is a time series.

I'm having trouble finding a more efficient way of formulating the data and model than a messy regression, although I suspect there is one. Let's assume that our only predictor is our current position in queue, Pos_0 and we are trying to predict the next event's effect on our position (Pos_0-Pos_1) where Pos_1 is our position after the next event; note this can only be positive or zero.

The queue can be depleted by either FIFO processing (first in line is processed), or by departure (someone leaves the queue from some position). To simplify things, we can assume that departure will only occur from the back of the queue (newest entrants).

Processing an item will cause progression in the queue by 1 for all items in the queue, e.g. if queue length is 100 and 1 is processed from the front, then everyone moves up by 1 spot (100th in line is now 99th in line). To represent this single event in a regression, doesn't this require 100 X,Y pairs - where X is current position and Y is progression amount? E.g. 1,1; 2,1; ... 100,1

Departure from the rear of the queue will only affect our position if we are last in line. e.g. queue length is 100, we join and we are 101, and 3 people leave so we progress by 3 (we are now 98th in line). Similarly, if queue length is 100 and we are 90, at least 10 must leave from the end of the queue before we progress. Taking the case of queue length 100 and a departure event of 10, this seemingly requires 10 X,Y pairs to represent in a regression. E.g. 100,10; 99,9 ... 91,1

My question is, is there a better way to formulate the data and/or model such that each event does not have to be "unrolled" into multiple samples in order to capture its information? We are dealing with millions of events with queue lengths in the thousands, so unrolling all of them becomes computational painful.

$\endgroup$
  • $\begingroup$ Have you looked at modeling your data as a simple poisson distribution? I think that should be the first step, assuming that the data fits a poisson distribution. $\endgroup$ – John Yetter Jul 23 '15 at 18:22
  • $\begingroup$ Hmm I think this may work for progression from the front since it applies to all positions equally. From the back though, how would that work? Since the progression for each event is a function of its current position $\endgroup$ – gbasin Jul 23 '15 at 18:30
  • $\begingroup$ You are looking at negative arrivals. That is beyond my understanding, but I believe that this [link] (citeseerx.ist.psu.edu/viewdoc/…) provides a synopsis of the history of the research with some decent references. $\endgroup$ – John Yetter Jul 23 '15 at 18:57

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.