7
\$\begingroup\$

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:

Input sample

 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.

nesting plot on roll paper

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).

Fixed Variables

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)

Output sample

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:

  • R stand 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 90° or 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.

Goal:

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.

\$\endgroup\$

closed as unclear what you're asking by cat, lirtosiast, SuperJedi224, FryAmTheEggman, GamrCorps Dec 15 '15 at 0:48

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    \$\begingroup\$ Is there a scoring system/is the winning answer determined by popularity? \$\endgroup\$ – Kaya Nov 3 '13 at 15:54
  • 1
    \$\begingroup\$ The title might read more clearly as: "Efficiently packing rectangles on a strip of paper". "Nesting rectangles" suggests placing rectangles within rectangles that are within rectangles that are within…. \$\endgroup\$ – DavidC Nov 4 '13 at 2:13
  • \$\begingroup\$ Could you please clarify the scoring? Is the goal just to output "a" paperlength and some arrangement? Or the "best" arrangement? In what sense? And could you explain how the number of paper cuts is calculated (maybe using your example)? \$\endgroup\$ – WolframH Nov 4 '13 at 10:13
  • 3
    \$\begingroup\$ Rectangle bin packing is not for the faint of heart. See clb.demon.fi/files/RectangleBinPack.pdf \$\endgroup\$ – DavidC Nov 4 '13 at 14:44
  • \$\begingroup\$ I thought I could find beefy people, on Programming Puzzles & Code Golf ;-) \$\endgroup\$ – F. Hauri Nov 9 '13 at 21:21

Browse other questions tagged or ask your own question.