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.
