Re: [algogeeks] Re: Multiprocessor scheduling
works fine for the case taken in the codeCheck if it fails for any case please. http://www.ideone.com/paKYX On Wed, Aug 24, 2011 at 9:41 PM, Nikhil Gupta 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 wrote: > >> sorry a typoRound 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 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 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.
Re: [algogeeks] Re: Multiprocessor scheduling
@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 wrote: > sorry a typoRound 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 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 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.
Re: [algogeeks] Re: Multiprocessor scheduling
sorry a typoRound 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 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 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.
Re: [algogeeks] Re: Multiprocessor scheduling
@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 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 -- 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.
[algogeeks] Re: Multiprocessor scheduling
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.
