Given an arbitrary list of input files, of varying processing times (dependent on unpredictable factors), whose start and end times can be obtained from log files. And given a known optimum number that can be run in parallel, the challenge was to find (using a Perl for quicker "time-to-market") the distribution of files into separate lists so that each list runs in parallel and its contents run in series and the difference in execution time between different lists is minimised. Clearly this falls into the category of problem that is the title of this post.

Because most recent runs are more indicative than older ones, I used the reciprocal of (update: the age of) each finish time to find the weighted average execution time for each type of input file. A reasonable but not perfect algorithm was to then sort the list by execution time descending and at each iteration place it in the list with the least total execution time so far. This looks like an intuitive winner and indeed got about 2% away from perfection on testing, but I could see by inspection that some list entries could be swapped around to produce a slightly closer result to equality (indivisibility makes exact equality highly unlikely).

So after some research it became clear that mathematicians are still struggling with this one and the last two years has seen a frenzy of research to solve it theoretically. They seem to be trying to avoid linear programming and find an analytical solution, so far without success. My gut feeling is neural network, but before I veer off in that direction, I wonder if anyone has a better or clarified idea.

One world, one people

In reply to Proportional distribution of indivisible items by anonymized user 468275

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.