Have you considered processing the files in parallel using a demand-based algorithm rather than trying to predict their runtime? For example, have X processes, and each time one of the processes finishes, it can simply consume one of the remaining files?

I've had success with it in the past. I generally do it something like:

while (1) {
    # Are we supposed to pause or stop?
    if (-E "/tmp/pause") {
        sleep 10;
        next;
    }
    last if -E "/tmp/STOP";

    # Find a file to process
    my @filist = glob("*.input");

    while (my $file = shift @filist) {
        # try to claim the file
        if (rename $file, "$file.working.$$") {
            # Successful, so go handle it
            process_file("$file.working.$$");
            last;
        }
        # Didn't get the file (someone else might've claimed it just
        # as we tried to), so just loop to the next one...
    }
 }
[download]

The rename is essentially to let the OS handle the task of serializing the processes: on all operating systems I generally use, renaming (on a local filesystem) is considered to be an "atomic" operation, so only one process would "win" the file, and other processes would have to go and try the next one.

The advantages of demand-based sharing are:

• Bad runtime predictions won't cause task starvation
• It balances itself automatically, so it's easy to add or remove processes based on system load.

...roboticus

When your only tool is a hammer, all problems look like your thumb.

It seems an interesting idea to accept them from a queue like 5 government workers pressing the button for the next ticket number held by "customers". It would certainly mean the system is sensitive to processes completing earlier than predicted. But in this context, the first available worker at any time cannot always optimally take the largest process in the queue. For example, in the simplest case of two workers with three items left in the queue, when one becomes available 3 minutes ahead of the other and the remaining process times are estmated at 8, 5 and 4 minutes; taking the 8 minute one would leave the other worker with 12 minutes (update 3 to be free plus the 5 and 4 remaining) to your 8 whereas taking the 5 minute one would leave him 11 (3+8) minutes to your 9 (5+4). So yes, I see benefit in dynamic selection although it doesn't actually remove the problem of optimal picking (based on averaged runtimes and best fit) from what is remaining to be processed, but it does add another independent optimisation to the best solution.

One world, one people

I'd say partition problem (optimization variant with N partitions, ie the worst kind) rather than Knapsack, but otherwise the conclusion is pretty much the same. This means that while finding the best solution is easy (test all combinations, keep the best one), doing so in reasonable time is worth 1 million. Your "intuitive winner" looks like a pretty good approximation.

For what I understand of neural networks, I don't think they are relevant for this kind of problems. This is neither extracting information (the data size of the output, ie an ordering of your elements, is the same as the input), nor a classification problem (an element isn't sent to a set according to its properties alone, but to the properties of all the elements in the input).

Yes it does look like a partitioning problem but for reals not just integers. The best solution is indeed supposed to be something similar to a neural network, but so far the example solutions I found which build a tree and walk it (my earlier idea was to have N tree-walkers where N is also the number of workers when parallel processing of the jobs begin) seem to have errors in the method. My latest idea taken from various replies and munged/improved, is to start by putting the biggest five each in their own child process (that first step is obviously right though difficult to prove) and have each worker, on finishing a job, solve the remaining tree for what to take next. The dynamic solution of only 25 processes takes no time compared with the heavy jobs being performed.

One world, one people

> My latest idea taken from various replies and munged/improved, is to start by putting the biggest five each in their own child process (that first step is obviously right though difficult to prove) 

Probably because it's obviously wrong?

5+5+2 =12

3+3+3+3=12

> have each worker, on finishing a job, solve the remaining tree for what to take next

That's the best approach if you can avoid race conditions of two workers picking the same job.

> it does look like a partitioning problem but for reals not just integers.

All floats are effectively only integer approximations of real numbers. So?

> The best solution is indeed supposed to be something similar to a neural network,

By whom? Source?

Cheers Rolf
_{(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery FootballPerl is like chess, only without the dice}

What you describe sounds like a variation on the Knapsack Problem (but I am guessing you already knew that). I have not kept up with the state-of-the-art in dealing with that problem (or any NP-complete problems, actually), but that would be where I would start for theory. In practice, if you are within a single-digit percentage of best results, I would leave it there unless your working set reaches a size where that difference becomes problematic.

Hope that helps.