@Saurabh: what does your algo does when the number of jobs are much more than the number of processors??
On Wed, Aug 24, 2011 at 7:55 AM, saurabh singh <saurab...@gmail.com> wrote: > sorry a typo....Round the sum to the next multiple of number of > processors.Alternatively taking the ceil of per processor time. > Eg: > Consider 3 processors and 4 jobs with time 6 12 5 14 > Sum of jobs=37 > Time per processor ceil(37/3)=13 > Now sort the jobs in order of there slugishness 14 12 6 5 > Try assigning 14 to p1.Not possible time=13 > try assigning 12 to p2.Possible.Assign.Remaining time=1 unit.None of the > jobs can now be accomodated so move to p2. > Try assigning 6.Possible.Assign.Remaining time=7 unit > Assign 5.None job < 2 left.so move to the next processor. > This is the last processor.So assign all remaining jobs to this processor.( > *i.e. 14)* > I have tried this logic on few trivial cases..still to test for the hard > ones..... > > > On Wed, Aug 24, 2011 at 7:30 AM, saurabh singh <saurab...@gmail.com>wrote: > >> @Nikhil Gupta I tried on this strategy but I still could find better >> solutions. >> Another approach that I tried was : summing all the jobs. >> Then finding the total time per processor required(Sum of all jobs/no of >> processors).Round this to next higher multiple of the number of >> processors.Call this number *T* >> Now assign each processor jobs as knapsack where limit would be *T(By >> assigning jobs starting from longest job picking the best candidates such >> that the knapsack does not overflows)*..Give all remaining jobs to the >> last processor. >> If the problem is NP complete I am sure this logic will fail for many >> cases.But I am unable to find a contradiction. >> >> >> On Wed, Aug 24, 2011 at 12:32 AM, DK <divyekap...@gmail.com> wrote: >> >>> It's NP Complete in the general case: >>> http://en.wikipedia.org/wiki/Multiprocessor_scheduling >>> >>> -- >>> DK >>> >>> http://twitter.com/divyekapoor >>> http://gplus.to/divyekapoor >>> http://www.divye.in >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To view this discussion on the web visit >>> https://groups.google.com/d/msg/algogeeks/-/T_4ygbPRqYIJ. >>> >>> 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. >>> >> >> >> >> -- >> Saurabh Singh >> B.Tech (Computer Science) >> MNNIT ALLAHABAD >> >> >> > > > -- > Saurabh Singh > B.Tech (Computer Science) > MNNIT 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. > -- Nikhil Gupta Indian Institute of Technology Roorkee, Roorkee, Uttarakhand, India , 247667 Phone: +91 9634990161 email: nikgp...@iitr.ernet.in nikhilg.8...@gmail.com -- 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.
