works fine for the case taken in the code....Check if it fails for any case please. http://www.ideone.com/paKYX
On Wed, Aug 24, 2011 at 9:41 PM, Nikhil Gupta <nikgp...@iitr.ernet.in>wrote: > @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. > -- 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.
