Proceedings of ISP RAS


The algorithm on base of Nelder–Mead modified method and genetic algorithm for strip packing problem.

Sergey A. Martishin, Marina V. Khrapchenko.

Abstract

In this paper NP complete strip packing problem is analyzed. New heuristic algorithm on the base of modified Nelder–Mead method, genetic and linear programming algorithms for strip packing problem was proposed. Experiments on the well known tests show that this algorithm has certain advantages. Prospects for convex polygons packing were proposed. Possibility for parallel performance of the algorithm is shown.

Keywords

strip packing problem, genetic algorithm, Nelder–Mead method, linear programming.

Edition

Proceedings of the Institute for System Programming, vol. 19, 2010, pp. 135-156.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

Full text of the paper in pdf (in Russian) Back to the contents of the volume