Re: algorithm to sum run time of simultaenous jobs?

On Mon, 8 Dec 2008 13:03:18 -0800 (PST), trickybleeder@xxxxxxxxx
wrote:

I have a series of jobs with known durations (seconds). Example:

job 1 - 9
job 2 - 9
job 3 - 9
job 4 - 1
job 5 -2
job 6- 8
job 7 -1
job 8 - 8
job 9 - 5

I am going to process more than one job at a time. For the sake of
example let's say 5 at a time. I can control the order in which the
jobs excute. I want to know how much time will have passed when all
the jobs are complete.

Isn't this the same as a packing problem? Something like this?

http://en.wikipedia.org/wiki/Bin_packing_problem

Your "5 at a time" is a match for "5 bins." And the durations of the
jobs are a match for the size of the objects you're trying to fit into
the 5 bins?

If so, then my understanding is that there is no algorithm outside of
brute force trial & error that can pack (or schedule) to maximum
efficiency.
.

Relevant Pages

  • Re: How much requirement documentation up front?
    ... provide a best fit for a particular product. ... where there is no historical data or products where consumer habits ... fitting analysis again and selects a new algorithm. ... The fact that the software product itself makes it very convenient to ...
    (comp.object)
  • Re: Mathematica - How to plot the PDF?
    ... Density Function (PDF). ... number of elements in bins of some width I set, ... that Mathematica histogram is not a 'probability' type histogram like ... I've never tried using anything other than Fit to fit polynomials before. ...
    (sci.math.symbolic)
  • Re: Where is behavior AI now?
    ... regards going past the basics of intelligence. ... It's like documenting the flight path of a bird, without any understanding ... This is the same missing piece which has been missing for over 50 ... It's like trying to reverse engineer an encryption algorithm. ...
    (comp.robotics.misc)
  • Re: C++: why 80 charachters??
    ... I guess if the result of your editor's word-wrapping algorithm is ... to be able to fit more than about 130 characters on my ... print utility to do ...
    (comp.lang.cpp)
  • Re: Packing Problem
    ... minimizes the number of bins. ... backup onto a bunch of CD's.) ... My impression is that no efficient algorithm ... "The best fit decreasing and first fit decreasing strategies are among ...
    (sci.math)