Estimating time remaining in a queue with multiple workers

Question

I've been trying to figure out a way of calculating the estimated time remaining for an item in a queue when there are multiple workers processing items from the single queue.

A client submits a job to the queue, but since processing can take some time I wanted to give an estimate of feedback.

I know

• Number of items in the queue
• Position in queue
• Length of time an item takes to process*
• How many workers are running
• When each worker last completed a job

I don't know

• How far along processing the worker is, only when it starts and ends**

_{*Processing time is the 90th percentile processing time of past jobs within a reasonable time range. Not completely accurate but tends to overestimate slightly and is accurate enough for my needs.
**Workers are calling an external service so the best estimate of progress is time taken}

With a single worker I can use a function such as

estimated_seconds_remaining = (
    (position_in_queue + 1) * average_processing_time_seconds
) - (
    average_processing_time_seconds - time_since_worker_last_finished_seconds
)

(position_in_queue + 1) * average_processing_time_seconds gives me the time it will take to process all the items in the queue plus the one that is currently being processed, then taking away average_processing_time_seconds - time_since_worker_last_finished_seconds gives me the estimated time remaining to process the current queue item.

This works fairly well, and is accurate enough for reporting back since the variation in processing times is quite small.

But, in production I'll be running multiple workers, so multiple workers will be processing items from the same queue. There will most likely be 3 or 4 workers running, but could be upwards of 10 at times.

The simplest option is just modifying my formula so

estimated_seconds_remaining = (
    (position_in_queue + 1)/number_of_workers * average_processing_time_seconds
) - (
    average_processing_time_seconds/number_of_workers - time_since_worker_last_finished_seconds
)

But this gives inaccurate and erratic predictions, since the estimates are being re-calculated every second to update the display the times jump up and down depending on when the workers all finish their jobs.

Is there a simple way, with the information I have, to calculate a reasonably accurate prediction of the time remaining before an item from the queue is processed?

Answer 1

Sure, what you can do is adapt your second equation. I think it's basically right, but the problem is that workers might all end at about the same time, so that second term can jump about a little bit.

What I'd suggest would be to track the termination time of each worker individually. You could also track their individual average processing time, but for simplicity I'll keep assuming it's constant.

So now the function becomes:

(position_in_queue) / (avg_worker_processing_time / workers_count)
+ time_until_most_advanced_worker_completes_processing

that holds until your position is 0, at which point of course you want to report time_until_worker_that_has_my_task_completes_processing .

This should be far smoother, as time_until_most_advanced_worker_completes_processing will go to about zero smoothly and then you'll go forward one spot (reducing the time) and at the same time the next time_until_most_advanced_worker_completes_processing will rise a bit (keeping the smooth descent).

Hope that helps!