The underlying problem is a bin packing or multiple knapsack problem, and is well researched and known.

In your case, there are three equivalent printers, with seven separate jobs with different durations. I gather that the task is to find the job distribution (to the three printers) that yields the shortest completion time. (The completion time being, obviously, the most time taken by one of the three printers to print its jobs.)

At the core, the problem is to find the printer used for each chapter. This is combinatorics. Because there are seven chapters to print, and each chapter can be printed by one of the three printers, there are 3 = 3^{7} = 2187 possible combinations. (This does include the symmetry cases though; the cases that differ only by how the printers are labeled.)

The total printing duration is a constant, 5+6+7+4+5+6+3 = 36 seconds. If evenly divided between the three printers, the soonest that all jobs can be completed is 36/3 = 12 seconds. This does not mean there *is* a solution where all three printers complete in 12 seconds; it means that *if* there is such a solution, it is *optimal*: the best possible.

(It turns out that there indeed are two such packings, each specified by 6 of the 2187 combinations due to symmetries (in naming the printers). In the first one, one printer will print chapters 1 and 3, another will print chapters 2 and 6, and the third will print the remaining chapters 4, 5, and 7. In the second one, one printer will print chapters 1, 4, and 7, another chapters 2 and 6, and the third will print the remaining chapters 3 and 5. In both cases all printers will complete in 12 seconds, in the optimum time.)

I verified this with this Bash one-liner:

Code:

C=(5 6 7 4 5 6 3) ; for ((I=0;I<2187;I++)); do P=(); D=(); v=$I ; for ((i=0;i<7;i++)); do k=$[v%3]; v=$[v/3]; P[i]=$k; D[k]=$[D[k]+C[i]]; done ; D[0]=$[D[0]] ; D[1]=$[D[1]] ; D[2]=$[D[2]] ; M=${D[0]}; [ $M -lt ${D[1]} ] && M=${D[1]} ; [ $M -lt ${D[2]} ] && M=${D[2]} ; echo $M : ${P[@]} : ${D[@]} : $I ; done | sort -rg

The first number in the output is the time the slowest printer completes (thus the total duration of the print jobs), the next seven indicate the printer used for each chapter (0 is first printer, 1 is second printer, and 2 is third printer), the next three numbers indicate the total time taken by each printer, and the last number is the "seed", the value in decimal that in base 3 produced the printer selection. The output is sorted in decreasing total time (first column). Here are the last 25 lines the above outputs:

Code:

13 : 0 1 2 1 0 2 1 : 10 13 13 : 1263
13 : 0 1 2 1 0 2 0 : 13 10 13 : 534
13 : 0 1 2 0 1 2 0 : 12 11 13 : 588
13 : 0 1 1 2 2 0 2 : 11 13 12 : 1686
13 : 0 1 1 2 0 2 2 : 10 13 13 : 2010
13 : 0 1 1 2 0 2 0 : 13 13 10 : 552
13 : 0 1 1 0 2 2 0 : 12 13 11 : 660
13 : 0 1 0 2 1 2 2 : 12 11 13 : 2082
13 : 0 1 0 1 2 2 1 : 12 13 11 : 1407
13 : 0 0 2 1 2 1 1 : 11 13 12 : 1179
13 : 0 0 2 1 1 2 1 : 11 12 13 : 1341
13 : 0 0 1 2 2 1 2 : 11 13 12 : 1926
13 : 0 0 1 2 1 2 2 : 11 12 13 : 2088
12 : 2 1 2 0 0 1 0 : 12 12 12 : 266
12 : 2 1 0 2 0 1 2 : 12 12 12 : 1760
12 : 2 0 2 1 1 0 1 : 12 12 12 : 857
12 : 2 0 1 2 1 0 2 : 12 12 12 : 1604
12 : 1 2 1 0 0 2 0 : 12 12 12 : 502
12 : 1 2 0 1 0 2 1 : 12 12 12 : 1249
12 : 1 0 2 1 2 0 1 : 12 12 12 : 937
12 : 1 0 1 2 2 0 2 : 12 12 12 : 1684
12 : 0 2 1 0 1 2 0 : 12 12 12 : 582
12 : 0 2 0 1 1 2 1 : 12 12 12 : 1329
12 : 0 1 2 0 2 1 0 : 12 12 12 : 426
12 : 0 1 0 2 2 1 2 : 12 12 12 : 1920

(We can see from the above output that the seed 266, the 267th combination we tried, produced the first optimal solution.)

What I do not understand here, is

- What is a "semaphore script"?
- What does this have to do with semaphores anyway?
- What do you mean by "as fast as we can"? I'm kind of assuming you want a way to find the best solution (as outlined above).

You could, I guess, also mean that the code should not ponder the possibilities first, because that might take too long, but start printing as soon as possible, sacrificing possibly optimal solutions to get better *execution speed*. In that case, you typically want a greedy packer, which tend to be a bit more complicated than the slow but sure search for the best possible solution.

(Even a simple online greedy algorithm can find the optimal solution 426 for this particular case.)