I am trying to come with a optimization framework & cost function for the following problem:

  1. I have a stream of tasks coming in (volume of tasks upfront is unknown). Each task has a priority between 0 and 1 (1 being highest) and an Expiry Time (after which the Task is considered to be cancelled) - which is usually 1 or 2 days. Doing each task can take a few minutes.

  2. I have two sets of workers:

    1st Set Are Highly Skilled (have accuracy of High_X%) and have a fixed capacity of High_Y tasks/day and fixed cost $High_Z/day. The number of people might vary throughout the day as they login or out.

    2nd Set are low skilled (have accuracy of Low_X%), have a fixed capacity of Low_Y Tasks/day. However, their cost is different. They have a variable cost of $Low_Z_Per_Ad which is lower than High_Z/High_Y. The number of people might vary throughout the day as they login or out.

We need to try and maximize the sum(priority) of tasks done accurately before their Expiry Time, while minimizing the cost.

Note the number of tasks is greater than High_Y + Low_Y so we can't follow a simple strategy of assigning of highest priority to High Skill and lowest priority to low skill.

Since this is a stream of tasks, and the number of tasks + number of workers vary throughout the day, I am thinking the best way is to run an optimization every X minutes by forming a graph between the Tasks and Workers where the edges have a cost function. And then try to pick the edges with least cost while ensuring each task is only assigned to one worker.

However, what should the cost function look like for this kind of problem.


1 Answer 1


Since you have two distinct objectives (maximizing priority-weighted accurate task completions and minimizing cost), one approach is to form a weighted combination of the two objective functions and optimize that.

The first question is whether objective one (completions) can be expressed as a linear function. Are you comfortable with giving each task a "value" formed by the product of the probability it is completed accurately and the priority? This implicitly assumes that a task with priority 0.6 is twice as important/valuable as a task with priority 0.3.

Assuming the answer is yes, then the next question is whether you can quantify the tradeoff between task value and cost. Can you find a value $\alpha$ such that you would be indifferent between increasing (decreasing) a task value by 1 and increasing (decreasing) cost by $\alpha$? Note that this implies that the monetary value of a one unit change in task value (product of priority and completion probability) is constant regardless whether it would be adding to a low value or a high value.

It the answer is again yes, then you can look at maximizing (task value - $\alpha$ * cost) as your objective function.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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