How to decide between a inaccurate system and a accurate system with capacity constraints to do a stream of jobs

Question

Let's say you have a list of at most N Jobs to be done which are coming in a stream. There are two kinds of systems that can do the job:

1. System 1: A very fast system, which however, only does the job correctly some of the time.
2. System 2: A slower system, which does the job correctly all the time, however has a fixed capacity of only doing C jobs, which is small compared to number of total jobs (C < N).

The time required for doing all the jobs is the same for each system.

The Probability of the System 1 doing the job correctly (let's call say P_sys1(Job)) depends upon the job itself (so different jobs have different probabilities, some can be 5% some can be as high as 99%).

Let's assume the cost of doing a Job badly is Cost(Job). So expected cost of a bad job is (1 - P_sys1 (Job)) * Cost (Job).

We need to decide to send the Job to System 1 or 2 as soon as it arrives. Once a job is sent to the either system, it's done and cannot be reprocessed if done wrongly.

How would we minimise the overall expected cost of doing all the Jobs.

Or equivalently, how will decide which jobs will we send to System 2 to do?

(intuitively, you want to send the Jobs with the highest cost & smallest probability to succeed in System 1).

Note: since the jobs are coming as a stream you don't know all the jobs before hand. You can assume a prediction of what kind of jobs will come in a stream, however, it will also have its own error.

Would even appreciate links to any papers or research done on similar problems.

Answer 1

To use simulation- optimization procedure, One way would be as follows:

Suppose, you have some jobs in which need to process in stream or chase customer demand. You will have to calculate the probability distribution function (PDF) of the arrival jobs based on the orders or demands. (e.g. using exponential distribution function with a specific parameter).

Then, you would need to estimate the jobs failure probability function by using something like goodness-of-fit method. In the next step, when you could estimate these functions, you can use some criteria, for instance, based on "the highest cost & smallest probability to succeed in System 1" as you mentioned.

Once, the jobs are assigned to its specific system you can calculate the detailed schedule based on the MP model or maybe simulation process to achieve the optimum efficiency.

The process can be depicted as: The arrival jobs=> assign PDF=> define criteria=> schedule systems.

I hope it Would be helpful?

Answer 2

I'll propose an "online" decision process (heuristic), but I don't know if you have the data / forecasting ability to make it work, so I'm not sure it would be helpful.

Let $C_0$ be the remaining capacity of the slow system when the next job arrives (which you will definitely know), and let $\gamma$ be the expected "bad job" cost of the newly arrived job (which I'm assuming you will know once the job arrives). Now, for the tricky part, let $\Gamma$ be the expected "bad job" cost of the $C_0 $th most expensive remaining (yet to arrive) job. If there are not that many jobs left to come, set $\Gamma = 0$. For instance, if $C=6$, you're being asked to peer into the future and estimate what the fifth worst "bad job" cost out of all remaining jobs might be. (This is known as an order statistic.) You'll need a way to forecast $\Gamma$, noting that it depends on both the number of jobs to come and the nature of the jobs.

If you can get a figure for $\Gamma$, the decision rule is simple. If you route the newly arrived job to the fast process, you incur expected cost $\gamma$ (and $C_0$ remains the capacity left in the slow process). If you route the newly arrived job to the slow process, and charitably assuming you make all remaining decisions optimally, you end up sending the job with expected cost $\Gamma$ to the fast line (because you don't have capacity for it on the slow line) when, had you sent the current job to the fast line, you would have sent that job to the slow line. So the logic is to use the slow line now if $\gamma > \Gamma$ and the fast line if $\gamma < \Gamma$.