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 day 1000 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.
