Tile laying optimization

I have three surfaces I need to tile, length for all three is 210 units and the widths are 145, 285 and 145 units.

The tile size is 120 by 60 units and they come in packages of 6. The tiles can be cut to any size.

How can I lay those tiles so I minimize the number of packages ordered and make as few cuts as possible? Is there a computer program that can do the optimization automatically?

Are you looking for a mathematical optimum solution, or just a reasonable guess?

With a few minutes of doodling, I come up with the following solution:

1. Rip two tiles lengthwise to make four 120 X 30 tiles (2 cuts).
2. Stack each 120 X 30 tile with three 120 X 60 tiles to make a 120 X 210 area. This will use a total of 14 tiles, and cover all but 210 X 25 of surface one, 210 X 45 of surface two, and 210 X 25 of surface three.
3. In one tile, rip cut 25 from one edge to make two pieces 120 X 25 and 120 X 35. Rip the 120 X 35 once more to make two pieces 120 X 25 and 120 X 10 (two cuts).
4. In a second tile, crosscut to make a piece 90 X 60. Rip cut this piece 25 from one edge to make two pieces 90 X 25 and 90 X 35. Rip the 90 X 35 once more to make two pieces 90 X 25 and 90 X 10 (three cuts).
5. Use one 120 X 25 piece and one 90 X 25 piece to tile each leftover 210 X 25 area.
6. Rip two tiles 45 from one edge to make two pieces 120 X 45 and 120 X 15. Crosscut one 120 X 45 to make a 90 X 45 piece (three cuts).
7. Tile the remaining 210 X 45 area.

That uses exactly 18 tiles (14 + 2 + 2), which is three packages and the minumum number of packages you could use (two packages will not cover the required surface area). It also uses ten cuts–I’m not certain that’s the minimum, but it’s got to be close.

If you are actually installing tile, the goal is not to minimize the cuts, but to center the pattern such that one side doesn’t need tiny pieces to fill in, OR to put those tiny pieces under a counter toe-kick or mopboard where they don’t show. OR to simplify the most akward of the cuts. (like round holes might need to be centered on a joint for example) Sometimes these goals will conflict, and this best done by trial and error laying out tiles without adhesive.

It is rare to find a room that is built square enough that more than one wall can use uncut tiles. If possible, and considering the advice above, making this the longest wall will come close to minimizing the cutting.

If this is just a math exercise, I don’t have any idea.

If a math exercise, you’d probably want to treat it as a constraint satisfaction problem.

Thanks for the replies.

Actually they are soundproofing tiles made from a material that looks like compressed glass wool. See this earlier thread for details: http://boards.straightdope.com/sdmb/showthread.php?t=511218