I am a bit rusty on optimization algorithms and need an advice. This is my problem:

I have n images (with width and height) that must be printed on a planar surface at a defined point (x,y).

Then I have k printers that can move along y but are fixed on x. The planar surface run under them in only one direction. The difference with a normal printer is that once a one starts to print an image it must finish it before being able to move again on the y axis to print something else or to make space for its neighbor printer.

These printers have dimensions as well and are mounted on racks. I can have maximum 2 racks and each rack can mount up to 2 printers. Printers on the same rack cannot overlap.

The best solution, if exists, is a feasible one (all prints can be printed) that minimize the travel of the printers.

I made a naive algorithm that generate all the combinations and test them all, looking for the best. It works, but it is exponential both in time and RAM occupancy.

The RAM usage is due to the generation of the list of all the possible combinations, I store them into a matrix of (k^n x n) elements where each element h=(i,j) indicate the index of the printer that will print the j print. In the case of 12 images and 4 printers I have a matrix of 4^12 x 12 elements

Can you advice me on the best approach that I should follow to get an algorithm that find a sub-optimal feasible solution in less time and using less RAM?

Thanks in advance


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.