Best scheduling jobs

Question

I have been working on this question and can't seem to find the right answer. Can someone please help me with this?

We are given N jobs [1,..,N]. We'll get a salary S(i) >= 0 for getting a job i done, and a deduction D(i) >= 0 that adds up for each day passing.

We'll need T(i) days to complete job i. Suppose the job i is done on day d, we'll get S(i) - d.D(i) in reward. The reward can be negative if d is too big. We can switch jobs in the process and work on jobs in any order, meaning if we start job 1 that takes 5 days on day 1, we don't have to spend 5 consecutive days working on job 1.

How can we decide the best schedule of the jobs, so that we can complete all the jobs and get maximum salary?

Answer 1

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

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

Generally when you are optimizing schedules in the real world this is the approach. Figure out which task should be worked on first, do some work on it, then recalculate to see if you should switch tasks or keep working on the current one.

Answer 2

Following the above discussion:

For each job i, calculate the one day delay cost as X(i) = D(i) / T(i) and order the jobs by it. Maybe even just order by D(i) since when you choose one job you are not choosing the others - so it makes sense to choose the one with the most expensive deduction. Perform the jobs by this order to minimize the deduction fees.

Again, this is assuming that S(i) is a fixed reward for each job, independent on the exact day it is finished by, and that all jobs need to be performed.