optimal job scheduling with prerequisites (DAG) and finish time penalties

Revision en1, by pabloskimg, 2019-07-21 21:58:30

There are $N$ jobs, each job $i$ has a single prerequisite job $P_i$ that must be done before, except for a global root job which has no prerequisite. Each job takes $T_i$ time to be finished, and if a job is finished at time $t$ it contributes with a penalty of $t * U_i$, where $U_i$ is the i-th job's penalty coefficient. What is the minimum penalty for finishing all jobs?

Constraints: $N <= 2 * 10^5$, everything is integer and non-negative

History

Revisions

Rev. Lang. By When Δ Comment
en5 pabloskimg 2019-07-22 08:07:52 27
en4 pabloskimg 2019-07-22 08:05:53 47
en3 pabloskimg 2019-07-22 08:03:03 6 Tiny change: 'ng, but I still haven't f' -> 'ng, but I haven't f'
en2 pabloskimg 2019-07-22 08:02:00 510
en1 pabloskimg 2019-07-21 21:58:30 521 Initial revision (published)