Yes, pshaus is absolutely right. I have just confirmed it by exchange
arguments. Just schedule the one first having (duration/panelty) ratio
lesser.
On Wed, Jun 8, 2011 at 12:01 AM, pschaus psch...@gmail.com wrote:
sort the jobs increasingly according to ratio: duration/penalty.
It is easy to prove it's optimal for two jobs.
Then you generalize the proof for n jobs easily because you can swap
two consecutive jobs i,j that have duration(i)/penalty(i)duration(j)/
penalty(j) to decrease the total penalty of the schedule (same
reasoning as for two jobs + a constant for the ones before and after
that remain unchanged).
On May 30, 7:00 pm, ross jagadish1...@gmail.com wrote:
You are given a sequence of jobs. The no. of days which each job takes
to complete is also provided.
You are also given the penalty amount to be paid per day each day a
job left done. Give an optimal ordering
among jobs to minimize penalty. There are no concurrent jobs.
eg:
Jobs: J1 J2 J3
no. of days to complete: 1 10 4
Penalty incurred each day1000 30 40
the job is pending
output:
Schedule is J1 J3 J2
hence, J1 goes for 1st day. J3 for subsequent 4 days. J2 for the next
10 days.
Penalty incurred = (delay for job i ) * (penalty per day of job i) =
= (0)(1000) + (1)(40) + 5(30) = 190
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
-Aakash Johari
(IIIT Allahabad)
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
