Mathematics

Maren Marks

24 December, 15:00

Suppose we have N jobs labelled 1, ..., N. For each job, you have determined the bonus of completing the job, Vi ≥ 0, a penalty per day that you accumulate for not doing the job, Pi ≥ 0, and the days required for you to successfully complete the job Ri > 0. Every day, we choose one unfinished job to work on. A job i has been finished if we have spent R, days working on it. This doesn't necessarily mean you have to spend R / contiguous sequence of days working on job i We start on day 1, and we want to complete all our jobs and finish with maximum reward. If we finish job i at the end of dayt, we will get reward V IP. Note, this value can be negative if you choose to delay a job for too long Given this information, what is the optimal job scheduling policy to complete all of the jobs?