4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Do you know how much time the jobs take? The C jobs limit is simultaneous or a total maximum capacity (e.g. independent of time; the machine can do at most C jobs total). Is the job is done wrong, do you need to reprocess it? I.e. is the desired final output to have all jobs done correctly? $\endgroup$ – dhasson Aug 10 at 20:38
  • $\begingroup$ @dhasson thanks for you comments, I've modified the question accordingly. Just to clarify, C is the total max capacity, jobs cannot be reprocessed and the desired output is to reduce the total cost of doing jobs badly. $\endgroup$ – dg428 Aug 11 at 4:41
  • $\begingroup$ @dg428, as per you have a complex production system w.r.t the Probability of doing the job correctly, I recommended using the simulation-optimization approach. In your case, discrete event simulation could be applied. Would you try this? $\endgroup$ – A.Omidi Aug 11 at 4:57
  • $\begingroup$ @A.Omidi thanks, yeah I was thinking about using a simulation. However, the question still remains how? As in what algorithm or strategy should I use? $\endgroup$ – dg428 Aug 11 at 7:57
  • $\begingroup$ Do you know the cost and P_sys1 for each job in the stream at the outset, or are those revealed only when the jobs arrive? If the latter, do you at least have probability distributions for cost and P_sys1? $\endgroup$ – prubin Aug 11 at 20:19
1
$\begingroup$

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?

| improve this answer | |
$\endgroup$
  • $\begingroup$ thanks, but I am actually looking for how to quantify into a equation or algorithm "the highest cost & smallest probability to succeed in System 1" $\endgroup$ – dg428 Aug 13 at 5:22
  • $\begingroup$ @dg428, if you need to use a MP, the stochastic programming might be useful. $\endgroup$ – A.Omidi Aug 13 at 6:24
1
$\begingroup$

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$.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you @prubin for your answer. Yes, was thinking in the same lines, basically weighing the expected cost of doing the current job using the slow process vs the cost of having to send a higher cost job to the fast process down the line. However, do you know any other methods/literature which provides a more sophisticated approach? Or even industry solutions for similar real world problems? Thanks! $\endgroup$ – dg428 Aug 24 at 6:56
  • $\begingroup$ Sorry, no, I don't know anything directly applicable. You might look at how hospitals are allocating certain facilities (such as beds in isolation wards) during the pandemic. In some cases, they face similar issues: if they use a scarce bed on a somewhat sick arrival, will it be gone when a sicker person arrives. They don't have a limited input queue, though. $\endgroup$ – prubin Aug 24 at 15:38

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.