Algorithm for nesting submited jobs to reduce paper roll usage.
Working with a 36" large format printer, with paper roll as source (150feet=45meters).
With a delay loop on print server queue: waiting 30 seconds before printing in case another job are comming too.
At begining of (perl) print script, it do a list of paper sizes as an output from
gs -sDEVICE=bbox, with all pages of all jobs in last 30 seconds and return only one indexed list of page sizes, like:
0:807.4780x562.6371 1:562.6370x807.4780 2:1700.0000x4251.0000 3:550.6150x786.1020 4:594.0000x840.9060 5:504.7200x761.0000 6:368.3280x761.0000 7:1193.0000x1685.0000
All values are in 1/72 inches (postscript dot).
The roll is
36 x 72 = 2592 dot with but have 15dot margin.
The orientation of roll is:
Y=<width; max 2562 dots> and
X=<length: max not specified but ~127Kdots>. So when start printing, the top-left corner is one right side of printer and sheet is going out from the top of postscript page.
The goal of the challenge is to build the quicker algorithm to choose the smallest paper length to cut out from the roll and the way of nesting all pages on this paper sheet (adding a little fixed space between plots for cutter)... and having smallest number of cut (see drawing: reducing cut).
ROLL WIDTH = 36 x 72 PRINTER MARGIN = 15 x 2 PLOT SEPARATION = 15
Important: The pages may have to be re-ordered and rotated in order to find the best arrangment.
Desired output: First paper length alone on first line, than all page, one by line, in format:
<Index>:<X offset>x<Y offset><Rotation flag (R)
4281 0:1715x0 1:1715x577R 2:0x0 3:1715x1400R ...
Note: This sample may be wrong: I'm not sure now if
R are rightly placed or have to be inversed. That's doesn't matter in that:
Rstand for rotation and is a flag. But his meaning stay free it could be used to say to rotate or to not rotate (the rotation angle could be
270°, as you prefer;-).
Number of cuts
This have to be calculated only for separating plots, not do finalize margins. This mean: One separation = one cut, not two. But the rush have to be dropped!
In others word: border added could be separator/2 to plotter margin.
A cut have to be straight and end to end on a dimension of a sheet or already cutted sheet.
The winner will be the first to offer a full useable implementation of its algorithm able to process upto 20 rectangles in less than 30 seconds. (With shebang or command line sample). Any language commonly used in production is acceptable. (meaning: no brainf@#k, but lisp could be accepted.)
Bonus if in case of one fixed size of paper length due to one big plot, all other jobs are placed in the meaning of reducing number of paper cut.