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 <[email protected]> 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 <[email protected]> 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 [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
