Best Planning Tasks

Question

I am working on this question and cannot find the correct answer. Can someone please help me with this?

We are given N jobs [1,..,N] . We get a salary S(i) >= 0 for completing the task i done and subtracting D(i) >= 0 , which is added up for each pass of the day.

We will need T(i) days to complete task i . Assuming task i is completed on day d , we get S(i) - dD(i) as a reward. The reward may be negative if d too large. We can switch jobs in the process and work at workplaces in any order, that is, if we start work 1, which takes 5 days on the first day, we do not have to spend 5 days in a row on work 1.

How can we choose the best work schedule so that we can complete all tasks and get the maximum salary?

Answer 1

I think Shapiro is right. You need to determine the appropriate weighted cost formula for each task. It should take into account the remaining days, the deduction per day and, possibly, the total deduction.

Once you have a weighted cost, you can sort the list of tasks by weighted cost and complete one day of work on the first task in the list (there should be one that will cost the most if it is not completed). Then recalculate the weighted cost for all tasks now that the day has passed, sort the list and repeat until all tasks are completed.

Usually, when you optimize graphics in the real world, this is the approach. Find out which task you should work with first, do some work on it, then recount to see if you should switch tasks or continue working on the current one.

Answer 2

Following the discussion above:

For each job i calculate the cost of one day delay as X(i) = D(i) / T(i) and order the jobs. Perhaps even just order D(i) , because when you select one task, you do not select others, so it makes sense to choose the one with the most expensive output. Complete tasks on this order to minimize deduction fees.

Again, it is assumed that S(i) is a fixed reward for each task, regardless of what day it ends, and that all tasks are completed.

Answer 3

First forget about S (i). In any case, you complete all the tasks in which you receive all the rewards.

Secondly, it makes no sense to interrupt the task and switch to another. Suppose you have tasks A and B. The conclusion you get for the one that ends last is the same (it will take T (A) + T (B) to finish it, no matter how you plan) . The deduction for another job can only increase if you switch, because it will take longer to complete it. Therefore, it is best if you release the switch.

Now the problem is to order tasks in order to get the minimum amount of the fine. I'm not sure what next. You can choose the first job to minimize T (x) * sum (d) (since you are doing the dong x job, everything will delay the delay T (x)). Or you can choose the last job, since you know that you are going to pay the amount (T) * d (x) (you know when it will end). One says the order through T (x) the other says order d (x), and they are both wrong.

Probably the solution is some dynamic programming in this space, but it eludes me at the moment.