3
$\begingroup$

I have a software application which uses a queue and multiple processors to process those jobs. Jobs get re-run on a daily basis for customers, but we also have new customers signing up regularly.

The problem is that customers generally sign up during office hours, and the daily re-running of the jobs simply schedules the job to run at the same time every day. This means that we have built up quite large spikes of work during the day, with very few jobs running overnight.

I would like to even out the spikes in this job queue, but I also want to minimise how far each individual job is moved from it's original time slot. In other words, I would rather move 100 jobs by 5 minutes each than move 1 job by an hour to achieve an even distribution of jobs over the whole 24 hour period.

$\endgroup$
1
$\begingroup$

This is a problem in optimal control. But you only need a few tools to get a practical solution for your problem.

1) a way to estimate the time distribution of jobs from new customers. Plotting the hourly, daily, and weekly averages for instances of jobs from new customers will give you a feel for the periodicity of the distribution. Then you can fit the distribution to a time-dependent Poisson process, with terms for minute/hour/day/week.

2) quantification of your "loss function." Based on your statement I would imagine that your loss function will include a term penalizing concentrations of jobs in short time periods and a term penalizing time delays on jobs in a nonlinear fashion. Supposing $t_1,...,t_2$ represents the times at which jobs are executed, and $d_1,...,d_m$ represents the delays for job 1, job 2, etc., your loss function might look like

$$ L = k_1 \sum_{i=1}^m (\sum_{j=1}^m I(t_i - t_j < T))^2 + k_2 \sum_{i=1}^m d_i^2 $$

where $k_1$ and $k_2$ are positive constants, and $T$ is a 'critical' time period (like 5 minutes).

3) simulation of various control policies (scheduling of recurring jobs) to find their expected loss. Given a policy of running daily jobs at time $x_1,...,x_l$ you would draw from your distribution of new jobs to get times of new jobs $y_1,...,y_m$ (where $m$ is random). You can estimate the expected loss by doing the simulation many times and averaging the loss function over the runs.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.