Preview

Труды Института системного программирования РАН

Расширенный поиск

Упаковка прямоугольников в полосу модифицированным методом Нелдера-Мида с использованием генетического алгоритма

Аннотация

Исследуется задача упаковки прямоугольников в полубесконечную полосу. Известно, что эта задача является NP-трудной. Предложен новый эвристический алгоритм упаковки с использованием модифицированного метода Нелдера-Мида, генетического алгоритма и линейного программирования. Проведенное экспериментальное исследование предложенного алгоритма на известных тестовых примерах демонстрирует его преимущества. Предложены перспективные направления его использования для упаковки произвольных выпуклых многоугольников. Показана принципиальная возможность распараллеливания данного алгоритма.

Об авторах

С. А. Мартишин
ИСП РАН
Россия


М. В. Храпченко
ИСП РАН
Россия


Список литературы

1. Back T.: Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms. Oxford University Press, New York, 1996.

2. Baker B.S., Brown D.J. and Katseff H.P. A 5/4 algorithm for two-dimensional packing. Journal of Algorithms, 2:348--368, 1981.

3. Baker B.S., Coffman E.G. Jr., Ronald L. Rivest: Orthogonal Packings in Two Dimensions. SIAM J. Comput. 9(4):846-855 (1980)

4. Bansal L., Correre J.R., Kenyon C. and Sviridenko M. Bin Packing in Multiple Dimensions: Inapproximability Results and Approximation Schemes, Mathematics of Operations Research v.31 (2006), pp. 31-49.

5. Bortfeldt A.; Gehring, H.: Two metaheuristics for strip packing problems. 5-th International Conference of the Decision Sciences Institute. Athen, Griechenland, 4.-7. Juli 1999.

6. Bortfeldt A. Hermann G., A Parallel Genetic Algorithm for Solving the Container Loading Problem International Transactions in Operational Research Vol. 9 Issue 4 Page 497 July 2002

7. Burke E.K., Kendall G. & Whitwell G., A New Placement Heuristic for the Orthogonal Stock-Cutting Problem, Operations Research, 52(4) (2004), 655-671.

8. Danny Z. Chen, Xiaobo (Sharon) Huy, Yingping Huang, Yifan Li, Jinhui Xuz Algorithms for Congruent Sphere Packing and Applications, Symposium on Computational Geometry 2001: 212-221.

9. Gilmore, P. C., Gomery, R. E., A Linear Approach to the Cutting-Stock Problem, Operations Research, 1961, Vol 9, pp 849-859.

10. Goldberg D.E., Genetic algorithms in Search, Optimization and Machine Learning., Reading, MA: Addison-Wesley Publishing Company, 1989.

11. Goldberg M., The packing of equal circles in a square, Math. Magazine 43, pages 24-30, 1970

12. Goodman E.D, Tetelbaum A.Y. and Kureichik V.M. A Genetic Algorithm Approach to Compaction, Bin Packing, and Nesting Problems, Release 3.01, Aug. 1, 1995, Technical Report 95-08-01, Intelligent Systems Laboratory and Case Center for Computer-Aided Engineering and Manufacturing, Michigan State University, 80pp.

13. Dagli, C.H.; Hajakbari, A. Simulated annealing approach for solving stock cutting problem Systems, Man and Cybernetics, 1990. Conference Proceedings., IEEE International Conference on, Vol., Iss., 4-7 Nov 1990 Pages:221-223

14. Dagli, C. H., Poshyanonda, P., "New Approaches to Nesting Rectangular Patterns", Journal of Intelligent Manufacturing, 1997, Vol. 3, No. 3, pp. 177-190.

15. Hopper E. & Turton B.C.H., An Empirical Investigation of Meta-Heuristic and Heuristic Algorithms for a 2D Packing Problem, European Journal of Operational Research, 128(1)(2001), 34-57.

16. Hopper E. & Turton B.C.H., Problem Generators for Rectangular Packing Problems, Studia Informatica Universalis, 2(1) (2002), 123-136.

17. Kenyon, C., and Remila, E. A Near-optimal Solution to a Two-dimensional Cutting Stock Problem. Mathematics of Operations Research 25, 4 (Nov 2000), 645-656.

18. S. Kravitz. Packing cylinders into cylindrical containers. Mathematics Magazine, 40:65-71, 1967

19. Lodi A., Martello S., and Monaci M. Two-dimensional packing problems: a survey. European Journal of Operational Research, 141: 241-252,2002.

20. Mitchell M. An Introduction to Genetic Algorithms. The MIT Press, Cambridge, MA, 1996.

21. Nelder, J. A. and Mead. R. A Simplex Method for Function Minimization. Comput. J. 7, 308-313, 1965.

22. Poshyanonda, P.; Bahrami, A.; Dagli, C.H. Two dimensional nesting problem: artificial neural network and optimization approach Neural Networks, 1992. IJCNN., International Joint Conference on, Vol.4, Iss., 7-11 Jun 1992 Pages: 572-577 vol.4

23. Wang P.Y. & Valenzuela C.L., Data set generation for rectangular placement problems, European Journal of Operational Research, 134(2001), 378-391.

24. Головистиков А.В., Задачи двумерной упаковки и раскроя: обзор. Информатика, выпуск N 20, 2008, с. 18-33.

25. Жук С.Н. Онлайновый алгоритм упаковки прямоугольников в несколько полос с гарантированными оценками точности. Труды Института Системного программирования: Методы синтеза и анализа, т.12, 2007, с. 7-16.

26. Жук С.Н. Приближенные алгоритмы упаковки прямоугольников в несколько полос. Дискретная математика, т. 18:1, 2006, с. 91-105.

27. Канторович Л.В., Залгаллер В.А. Рациональный раскрой промышленных материалов. Наука. – Новосибирск, 1971, 299 с.

28. Кузюрин Н.Н., Поспелов А.И. Вероятностный анализ шельфовых алгоритмов упаковки прямоугольников в полосу. Дискретная математика, т. 18:1, 2006, с. 76-90.

29. Мухачева Э.А., Мухачева А.С., Чиглинцев А.В. Генетический алгоритм блочной структуры в задачах двумерной упаковки. Информационные технологии. Машиностроение. -М.:1999, N 11, с. 13-18.

30. Мухачева А.С., Чиглинцев А.В., Смагин М.А., Мухачева Э.А.. Задачи двумерной упаковки: развитие генетических алгоритмов на базе смешанных процедур локального поиска оптимального решения. Приложение к журналу Информационные технологии. Машиностроение. -М.: 2001, N 10, 24 с.


Рецензия

Для цитирования:


Мартишин С.А., Храпченко М.В. Упаковка прямоугольников в полосу модифицированным методом Нелдера-Мида с использованием генетического алгоритма. Труды Института системного программирования РАН. 2010;19.

For citation:


Martishin, S.A., Khrapchenko M.V. The algorithm on base of Nelder–Mead modified method and genetic algorithm for strip packing problem. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2010;19. (In Russ.)



Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


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