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:
- System 1: A very fast system, which however, only does the job correctly some of the time.
- 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.