Алгоритмы упаковки n-мерных гофров на базе методов линейного программирования тема диссертации и автореферата по ВАК РФ 05.13.16, кандидат технических наук Васильева, Лидия Ильясовна

• Васильева, Лидия Ильясовна
• кандидат технических наук
• 2000

Оглавление диссертации кандидат технических наук Васильева, Лидия Ильясовна

ВВЕДЕНИЕ.

Глава 1. Проблема раскроя-упаковки: многообразие задач и методов их решения.

1.1. Постановка задачи раскроя-упаковки.

1.2. Классификация задач раскроя-упаковки.

1.3. Многообразие задач раскроя-упаковки.

1.4. Задача прямоугольной упаковки.

1.4.1. Постановка задачи прямоугольной упаковки.

1.4.2. Эвристические методы решения задачи прямоугольной негильотинной упаковки.

1.4.3. Точные методы решения задачи негильотинного прямоугольного раскроя.

1.5. Задачи фигурного раскроя-упаковки.

1.6. Задачи трехмерной упаковки.

1.7. Постановка задачи исследования.

1.8. Выводы по первой главе:.

Глава 2. Анализ постановки и методов решения задачи упаковки гофров с позиций общей теории проблемы оптимального размещения геометрических объектов.

2.1. Модели и методы двумерной упаковки геометрических объектов произвольной формы.

2.1.1 Основные понятия и постановка задачи.

2.1.2. Классификация методов решения.

2.2. Метод упаковки n-мерных параллелепипедов в полубесконечную область.

2.2.1. Постановка задачи.

2.2.2. Матричная интерпретация упаковки.

2.3. Задачи генерации и планирования раскроя-упаковки.

2.4. Приближенный метод решения задачи планирования п-мерных упаковок гофров.

2.5. Выводы по второй главе:.

Глава 3. Разработка математических моделей и алгоритмов решения задачи планирования п-мерных упаковок гофров.

3.1. Постановка задачи как задачи ЛП.

3.2. Математическая модель задачи планирования.

3.3. Генерация последовательностей из номеров гофров.

3.4. Алгоритм случайной выборки для генерации способа упаковки.

3.4.1. Математическая модель задачи генерации способа упаковки.

3.4.2. Размещение гофра в объекте.

3.4.2.1. Представление гофра в виде совокупности блок-структур

3.4.2.2. Операция сложения блок-структур.

3.4.2.3. Учет условий допустимости упаковок гофров в процессе размещения блок-структур.

3.4.2.4. Процедура уплотнения.

3.5. Алгоритмы решения.

3.7. Оценка сложности алгоритма генерации карты упаковки.

3.6. Выводы по третьей главе:.

Глава 4. Программная реализация алгоритмов и численный эксперимент .88 4.1. Описание программного обеспечения.

4.1.1. Структура файлов.

4.1.2. Описание модулей программы.

4.2. Подготовка численного эксперимента.

4.3. Численный эксперимент.

4.3.1. Исходные данные эксперимента.

4.3.2. Численный эксперимент №1.

4.3.3. Численный эксперимент №2.

4.3.4. Численный эксперимент №3.

4.4. Развитие методов решения и другие постановки задачи упаковки гофров.

4.4.1. Генерация поворотов гофра.

4.4.2. Другие постановки задачи и развитие методов их решения.

4.5. Выводы по четвертой главе.

Введение диссертации (часть автореферата) на тему «Алгоритмы упаковки n-мерных гофров на базе методов линейного программирования»

Проблема ресурсосбережения была и остается чрезвычайно важной. Среди множества ресурсосберегающих задач важное место занимают задачи, связанные с раскроем и упаковкой (Р-У) в заданных областях объектов различного вида и имеющих различную физическую природу.

Актуальность проблемы оптимального раскроя объясняется не только очевидной эффективностью использования рациональных планов раскроя-упаковки на производстве, но и многообразием постановок задач Р-У, трудностью создания совершенных математических моделей и выбора методов их решения. Задачи Р-У представляют собой важный раздел методов оптимизации и исследования операций. В рамках решения этих задач развиваются и исследуются общие проблемы, характерные для указанных областей математики.

Задачи Р-У представляют собой широкий класс моделей, объединенных однообразной логической структурой и допускающих различное толкование. В литературе они встречаются под названиями: задача раскроя запаса материала, задача плотного размещения геометрических объектов в заданной области, задача загрузки рюкзака, задача упаковки контейнеров, задача загрузки транспорта, задача выбора ассортимента, задача планировки помещений, задача обеспечения ритмичности производственного процесса, и другие. Общим для них является наличие двух групп объектов. К первой группе относятся большие объекты, ко второй - малые. Требуется установить соответствие и порядок назначения между ними так, чтобы некоторая целевая функция достигала минимум при выполнении определенных ограничений.

Все эти задачи по своей сути относятся к проблеме оптимизационного геометрического моделирования, заключающейся в оптимизации размещения данного вида объектов в заданных областях.

Сложность решения задач Р-У заключается в том, что они относятся по своей сложности к классу ОТ- трудных проблем оптимизации, т.е. для кото5 рых пока не существует методов и алгоритмов, находящих точное решение за полиномиальное время.

В классе задач Р-У на верхних ступенях сложности, по отношению к другим задачам Р-У, находятся задачи двух- и трехмерного нерегулярного размещения геометрических объектов (ГО) сложных форм. Это связано с трудоемкостью формализации условий взаимного непересечения объектов и условий их размещения в заданных областях Р-У. В то же время для задач двумерного раскроя-упаковки фигур простых форм (прежде всего, прямоугольников) имеются методы нахождения приближенных и оптимальных решений.

На практике часто возникает необходимость решения задачи раскроя-упаковки заготовок, представляющих собой объединение конечного числа прямоугольников или параллелепипедов, чаще всего связанных друг с другом (например, развертка коробки); такие фигуры будем называть гофрами.

Понятие «гофр» впервые было введено и рассмотрено Корницкой М.Н. и Липовецким А.И. [72]. В связи с трудностями, возникающими в процессе решения задач фигурного Р-У, ими был предложен подход, связанный с упрощением формы раскраиваемых заготовок путем их аппроксимации фигурами определенных классов и решением указанной задачи для этих классов фигур. Предложенный аппроксимационный подход был разработан для проектирования раскройных карт в единичном производстве путем обобщения эффективных алгоритмов негильотинного раскроя на подкласс л 12-фигур, названных гофрами. Гофром в [72] назван многоугольник, ребра которого можно разбить на две ветви, составленные из ступенчатых ломаных с координатами вершин, монотонно возрастающих по оси абсцисс и монотонно убывающих по оси ординат.

В нашем случае понятие гофра обобщено на случай произвольных совокупностей прямоугольников или параллелепипедов любой мерности.

Определение. Гофр- это фигура, состоящая из конечного числа непересекающихся «-мерных прямоугольных параллелепипедов, ребра которых параллельны осям координат, с фиксированным положением относительно друг друга. На рис. 1 приведены примеры двумерных гофров. а) б) с)

Рис. 1. Двумерные гофры.

Гофр является частным случаем ГО сложной формы и относится к фигурным элементам с прямолинейными составляющими. В связи со строго заданной структурой гофра рассмотрение таких заготовок не вызывает трудностей, связанных с представлением исходной информации и моделированием УВН. В то же время, если это необходимо, с помощью гофров может быть получена аппроксимация ГО сложной формы нетиповыми элементами. Таким образом, гофры могут рассматриваться как самостоятельно в качестве заготовок при решении задачи их размещения, так и в качестве аппроксимирующих элементов при решении общей проблемы фигурного нерегулярного Р-У. Исходя из сказанного, следует, что задача планирования упаковок гофров является актуальной.

Диссертационная работа посвящена разработке и исследованию математических моделей и алгоритмов решения п -мерной задачи раскроя-упаковки заготовок, имеющих форму гофров, в условиях массового производства.

Целью работы является: создание математической модели задачи генерации допустимых способов упаковки; разработка эффективных вычислительных алгоритмов решения задачи планирования п -мерных упаковок гофров и создание на их основе программного обеспечения для генерирования карт Р-У в массовом производстве.

Для этого были поставлены и решены следующие задачи:

1. Разработка математических моделей задачи планирования п-мерных упаковок гофров и задачи генерации способа упаковки;

2. Представление гофра в виде совокупности блок-структур по каждому направлению и сведение задачи упаковки гофра к решению п задач размещения его блок-структур;

3. Разработка алгоритма случайной выборки для генерации допустимого способа упаковки, использующего представление гофра в виде совокупности блок-структур;

4. Проведение и анализ результатов численного эксперимента на базе созданного программного обеспечения.

Научная новизна работы:

• Обобщен класс п -мерных прямоугольных многоугольников-гофров, предложено представление гофра в виде совокупности блок-структур, исследованы возможности покоординатной укладки гофров путем размещения блок-структур;

• Разработаны алгоритмы решения задачи Р-У гофров, являющейся частным случаем проблемы фигурного Р-У, в условиях массового производства;

• Предложенные алгоритмы решения разработаны и реализованы для решения п -мерной задачи Р-У гофров ( п > 2).

Практическая значимость работы: 1. Предложенные в диссертации алгоритмы ориентированы на достаточно широкий класс прикладных задач, связанных с раскроем-упаковкой заготовок сложных форм в условиях массового производства: результаты диссертации могут быть использованы при решении задач упаковки гофров, а также при решении задач фигурного нерегулярного раскроя-упаковки с предварительной аппроксимацией исходных заготовок гофрами.

2. Разработанные алгоритмы инвариантны относительно мерности задачи, поэтому могут использоваться при решении задач двумерного и трехмерного Р-У заготовок сложных форм.

Поставленные в работе задачи решались на основании современной методологии задач раскроя-упаковки, геометрических методов, линейного программирования, теории вероятностей и математической статистики.

Работа выполнялась при поддержке Российского Фонда Фундаментальных Исследований, проект 99-01-00937.

Диссертация состоит из введения, четырех глав, списка используемой литературы и приложений.

Заключение диссертации по теме «Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях (по отраслям наук)», Васильева, Лидия Ильясовна

Основные результаты работы:

1. Обобщено введенное ранее понятие «гофр»; в поставленной задаче планирования упаковок в качестве заготовок рассмотрены «-мерные гофры (п-мерность задачи).

2. Разработана математическая модель задачи упаковки п -мерных гофров (п> 2) внутри п -мерных прямоугольных объектов: поставленная проблема описана непрерывной моделью линейного программирования.

3. Введено понятие «блок-структура» и предложено представление каждого гофра в виде совокупности блок-структур.

4. Определены правила размещения и операция сложения блок-структур; сформулированы необходимые и достаточные условия допустимости размещения.

5. Предложено формирование последовательностей из гофров для предварительной генерации подмножества допустимых упаковок.

6. Показано сведение задачи упаковки п -мерного гофра в объект к решению п задач размещения блок-структур гофра.

7. Разработан алгоритм случайной выборки для генерации допустимого способа упаковки, основанный на представлении гофра в виде совокупности блок-структур.

8. Алгоритм решения задачи планирования упаковок п -мерных гофров базируется на симплекс-методе с предварительно сгенерированной матрицей ограничений - векторов упаковки, полученных алгоритмом случайной выборки.

9. Разработанные алгоритмы программно реализованы. Проведены численные эксперименты, подтверждающие перспективность данного подхода.

ЗАКЛЮЧЕНИЕ

Список литературы диссертационного исследования кандидат технических наук Васильева, Лидия Ильясовна, 2000 год

1. Aarts Е., Lenstra J.K. (eds.) Local search in combinatorial optimization. John Wiley & Sons Ltd, 1997. -315p.

2. Abdou, G., Yang, M. A Sistematic Approach for the Three-Dimensional Palletization Problem.//International Journal of Production Research, №10,1994.-P. 381-394.

3. Amaral C., Portugal. Automatic interactive program means for packing.//SICUP-Bulletin №12, November, 1992. -P.2-3.

4. Beasley J.E. An exact two-dimensional non-guillotine cutting tree search procedure. //Operational Research, 1985, vol.33. -P.49-64.

5. Blazewich J., Drozdowski M., Soniewicki В., Walkowiak R., Poland. Systems for figure cutting stock problem fulfillment and experimental comparison.//SICUP-Bulletin №5, November, 1990. -P.3.

6. Blazewich J., Walkowiak R., Poland. Parallel "search of prohibition for two dimensional cutting stock problem. //SICUP-Bulletin №12, November, 1994. -P.5.

7. Blazewicz J., Hawryluk P., Walkowiak R. Using a tabu search approach for solving the two-dimensional irregular cutting problem. //Annals of OR, №41(1-4), 1993. -P.313-325.

8. Brooks R. L., Smith С. А. В., Stone A. H., Tutte W. T. The dissection of rectangles into squares. //Duke Mathematical Journal, №7, 1940. -P.312-340.

9. Chen, C.S., Lee, S.M., Shen, Q. S. An Analitical Model for the Container Loading Problem.// International Transactions in Operational Research, Vol.80,1995. -P.68-76.

10. Dyckhoff H. A Typology of Cutting and Packing Problems. //European Journal of Operational Research, v.44, 1990. -P. 145-159.

11. Fabian C., Spinulescu E., Rumania. A non-guillotine cutting problem for defecting sheets.//SICUP-Bulletin №7, June, 1993. -P. 13.

12. Fernandes J.L., Bernardo J.C., Portugal. Geometric algorithms and heuristic methods for automatic packing of figures. //SICUP-Bulletin №9, January 1993. -P.20.

13. Fraser, H.J., George, J.A. Integrated Container Loading Software for Pulp and Paper Industry.//EJOR, №77, 1994. -P.466-474.

14. Freeman, H. and Shapira, R. Determining the minimum area encasing rectangle for an arbitrary closed curve. //Comm.ACM. №18(7), 1975. -P.409 - 413.

15. Heckmann R., Lengauer T. A simulated annealing approach to the nesting problem in the textile manufacturing industry.//Annals of OR, №57, 1995. -P. 103133.

16. Galambus G., Van Vliet A. Louwer bounds for 1-, 2- and 3-dimensional on-line bin packing algorithms. //Computing vol. 52. -P. 281-297.

17. Gehring H., Bortfeldt A. A Genetic Algorithm for Solving the Container Loading Problem. // International transactions in operational research, vol.4, № 5/6, 1997.-P. 401-418.

18. George, J.F., New Zealand A Method for Solving Container Packing for a Single Size of Box.//Journal of the Operational Research Soviety,Vol.43,№4,1992.-P.307-312.

19. Gilmore P. C., Gomory R. E. The theory and computation of knapsack functions. //Oper. Res, №14,1966. -P.145-175.

20. Gilmore P.C., Gomory R. E. A linear programming approach to the cutting stock problem (Part I/II). //Oper. Res. №9. -P.849-859, and Oper. Res. №11, 1961/63. -P.863-888.

21. Gilmory P.C., Gomory R.E. Multistage cutting stock problem of two and more dimensions. //Oper.Res., №13, 1965. -P.94-120.

22. Haessler R.W., USA. Minimization of counts n-dimensional packing problem. //SICUP-Bulletin №9, January, 1993. -P.20.

23. Haessler, R.W. Cost Minimization of Multiple-Vehicle Shipment./SICUP-Bulletin №9, January 1993. -P.2-3.

24. Holland J.H. Adaptation in Natural and Artificial Systems. Ann Arbor. //The University of Michigan Press, 1975. -96p.

25. Ikonen I.T., Biles W.E. Three dimensional chromosomal representation for a genetic algorithm for packing non-convex parts in 3D. //Proceedings of the 3NWGA. Helsinki, Finland, 1997. -P. 101-119.

26. Ikonen I.T., Biles W.E., et al. Concept for a genetic algorithm for packing three dimensional objects of complex shape. //Proceedings of the first online workshop of soft computing, 1996. -P. 12-24.

27. Martello S., Vigo D., Exact solution of two-dimensional finite bin packing problem. //Management Science, vol. 35, 1997. -P. 68-74.

28. Medetz W., Austria. Package of programs for automatic figure packing. //SICUP-Bulletin №9, January 1993. -P.20.

29. Milencovic V.I., Daniels K., Li Z., USA. Allocation and compacting of non-convex polygons for easy industry. //SICUP-Bulletin №9, January 1993. -P. 15.

30. Milenkovic V.J., Daniels K. Translational polygon containment and minimal enclosure using mathematical programming.//ITOR special issue with papers from IFORS'96, 1996. -30p.

31. Mohanty, B.B., Mathur, K., Ivancic, N.J. Value Consideration in Three-Dimensional Packing A Heuristic Procedure Using the Fractional Knapsack Problem// EJOR, №74, 1994. -P.143-151.

32. Morabito R., Arenales M., Brazil. Application of AND/OR-graphs to Container Loading Problem. //SICUP-Bulletin №9, January, 1993. -P. 12.

33. Perry E.C., Landon M.D., Balling R.J. Spatial packaging of complex parametric solid objectives via optimization. // Engineering Design Methods Labs, Report 89-9. Bringham University, 1989. -51p.

34. Portmann, M.-C. An Efficient Algoritm for Container Loading.//Working Paper, 1990. -P.23-25.

35. Scheithauer G, Terno J. A heuristic approach for solving the multi-pallet packing problem. //Decision Making under Conditions of Uncertainty (Cutting -Packing Problems). The International Scientific Collection. Ufa, 1997. -P. 140155.

36. Scheithauer G., Germany. Algorithms for solving the Container Loading Problem. //SICUP-Bulletin №9, January, 1993. -P.8.

37. Scheithauer G., Terno J., Germany. Modeling of bin packing problems. //SICUP-Bulletin №9, January, 1993. -P.7.

38. Scheithauer,G. Algoritm for the Container Loading Problem.//Operations Research Proceedings, 1991, Springer-Verlag, Berlin/Heidelberg, 1992 (ISBN 3540-55410-6). -P.445-452.

39. Sha E.L. Area efficient and volume efficient algorithms for loading cargo, master's thesis (unpublished).// US Navy Post-Graduate School, 1970. -188p.

40. Simchi-Levi D. New worst-case results for the bin packing problem. //Naval Res. Log.Quart, vol.41, 1994. -P. 579-585.

41. Terno J., Lindeman R, Scheithauer G. Zuschnitprobleme und ihre prakti-sche Losung. //Leiprig, 1987. -P.207.

42. Tinarelli U., Addonizio M. Un problema di caricamento di containers. //Proc. AIRO congress, 1978. -P.79-91.

43. Udy J.L., Balling R.J., Benzley S.E., Landon M.D. Computation of interferences between three-dimensional objects and the optimal packing problem. // Advances in Engineering Software, Vol.10, №1, 1988. -P.8-14.

44. Valerio de Carvalho J.M., Rodrigues A.J.G., Portugal. Interactive computer's approach to a problem of two-stage cutting stock problem. //SICUP-Bulletin №9, November, 1992. -P.l.

45. Valeyeva A., Totskov I. Development of three-dimensional packing methods. //Decision Making under Conditions of Uncertainty (Cutting Packing Problems). The International Scientific Collection. -Ufa: USATU, 1997. -P. 198207.

46. Аккуратов Г.В., Березнев B.A., Брежнева O.A. О методе решения уравнения с булевыми переменными. //Принятие решений в условиях неопределенности: межвуз. научный сб. Уфа, 1990. -С. 145-146.

47. Белякова Л.Б. Об оптимальном раскрое листового материала. //В кн.: Автоматизация технологического проектирования при помощи ЭЦВМ. -М. : Машиностроение, 1968.-С.21-32.

48. Белякова Л.Б., Орехова О.М., Дмитриевская О.В. Алгоритм рационального раскроя полос на фигурные заготовки. //Труды ОНТИ ПТНИИ Волго-Вятского совнархоза, 1964. -С. 53-65.

49. Бухвалова В.В. Реализация метода зон Липовецкого для прямоугольного раскроя. //Математическое обеспечение рационального раскроя в системах автоматизированного проектирования. Тезисы докл. всесоюзной конференции.-Уфа, 1987.-С. 16-17.

50. Валеева А.Ф. Алгоритм построения прямоугольной упаковки и применение его к задаче фигурного раскроя//Труды междун. сибир. конф. по прикл. и индустр. математике. СО РАН, т.2, 1995. -С.47-57.

51. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. М.:Мир,1985. - 509с.

52. Гиль Н.И., Черноморец A.A. Метод построения поверхности 0- уровня Ф-функции. -Харьков, 1992.-29с.-(Препринт/АН Украины, Ин-т пробл. машиностроения: 359).

53. Данциг Д.Б. Линейное программирование, его применение и обобщение. -М.: Прогресс, 1966. -600 с.

54. Иванов Г.А. Проектирование размещения плоских геометрических объектов методами нелинейного программирования. Автореферат диссертации на соискание ученой степени кандидата технических наук. Йошкар-Ола: МарПИ, 1993 .-16 с.

55. Канторович JI.В. Математические методы в организации и планировании производства. -Л.:ЛГУ,1939. -60 с.

56. Канторович Л.В. Методы рационального раскроя металла// Производственно технический бюллетень. -М., 1942. -35с.

57. Канторович Л.В., Горстко А.Б. Математическое оптимальное программирование. -М: Экономика, 1968. -96 с.

58. КантОрович Л.В., Залгаллер В.А. Рациональный раскрой промышленных материалов. -Новосибирск: Наука СО, 1971. -320с.

59. Картак В.М. Модели и методы оптимизации упаковки N-мерных параллелепипедов. //Диссертация на соискание ученой степени кандидата физико-математических наук. -Уфа, 1999г. -90с.

60. Картак В.М., Васильева Л.И. Модели и методы оптимизации упаковки N-мерных параллелепипедов. // Деп. в ВИНИТИ. №58-В99 от 14.01.1999-14с.

61. Кацев C.B. Об одном классе дискретных минимаксных задач. //Кибернетика, №3. -Киев, 1979. -С. 113-118.

62. Липовецкий А.И. Алгоритмы негильотинного прямоугольного раскроя. //Математическое обеспечение рационального раскроя в САПР. Материалы всесоюзной конференции. -Уфа, 1988. -С. 72-79.

63. Липовецкий А.И. К оптимизации свободного размещения прямоугольников. //Автоматизация проектирования в машиностроении. Минск: ИТК АН БССР, 1985.-С. 80-87.

64. Липовецкий А.И. Свойства прямоугольных укладок и алгоритмы оптимального раскроя. -Свердловск: Уро АН СССР, 1988. -50 с.

65. Математическое обеспечение рационального раскроя в системах автоматизированного проектирования. Материалы Всесоюзной конференции 15-17 июня 1987. -Уфа: УАИД988. -159 с.

66. Мухачева A.C. Алгоритмы плотной упаковки прямоугольных объектов на базе аппроксимации линейным раскроем. // Рук. Деп. в ВИНИТИ, №53-В99 от 14.01.1999.-18 с.

67. Мухачева Э.А. Рациональный раскрой промышленных материалов: Применение АСУ. -М. Машиностроение, 1984. -176с.

68. Мухачева Э.А., Мухачева A.C., Белов Г.Н. Метод последовательного уточнения оценок: алгоритм и численный эксперимент для задачи одномерного раскроя. //Информационные Технологии, N2, 2000. -С. 11-17.

69. Мухачева Э.А., Верхотуров М.А., Мартынов В.В. Модели и методы расчета раскроя упаковки геометрических объектов. -Уфа: УГАТУ, 1998. -217с.

70. Пономаренко Л.Д., Туранов И.Н. Оптимальная упаковка параллелепипедов: модель, метод и алгоритм. -Харьков, 1984. -51с. (депон. в ВИНИТИ, №4075-84).

71. Рвачев В.JI. Геометрические приложения алгебры логики. -Киев: Техника, 1967.-212с.

72. Рвачев В.Л. Теория R-функций и некоторые ее приложения. Киев: На-ук.думка, 1982. -550 с.

73. Рвачев В.Л., Стоян Ю.Г. Алгоритм построения неравенств, которым удовлетворяют параметры размещения непересекающихся тел. //Кибернетика, №5, 1966.-С .43-53.

74. Рвачев В.Л., Стоян Ю.Г. К вопросу об оптимальном раскрое материалов.// В кн.: Вопросы теоретической кибернетики. Киев: Изд. института кибернетики АН УССР, 1965. -С.30-42.

75. Рвачев В.Л., Стоян Ю.Г. К задаче об оптимальном размещении круговых выкроек. //Кибернетика, №4, 1965. -С .66-78.

76. Стоян Ю.Г., Гиль Н.И. Методы и алгоритмы размещения плоских геометрических объектов. -Киев: Наукова думка, 1976, -144 с.

77. Стоян Ю.Г., Новожилова М.В., Карташов A.B. Математическая модель и оптимизация линейных Ek(R ) задач размещения. -Харьков, 1991. -44 с.-(Препринт /АН УССР. Ин-т пробл. Машиностроения: №353).

78. Стоян Ю.Г., Яковлев C.B. Математические модели и оптимизационные методы геометрического проектирования. -Киев: Наук, думка, 1986. -286с.

79. Томарченко Л.И. Опыт организации безостаткового раскроя. -М.: Легкая промышленность, №1, 1941. -С. 19-26.

80. Федоров Е.С. Начала учения о фигурах. -Записки Мин. Общества, 2-я серия, №21, 1885.-С. 1-289.

81. Федоров Е.С. Симметрия и структура кристаллов. -М.: Изд-во АН СССР, 1949.-154 с.

82. Шавырин Н.В. Раскрой ткани без остатка. -М.: Швейная промышленность, №2, 1940. -С.49-57.

83. Шехтман Л.И. Линейный алгоритм решения задачи регулярной трехмерной упаковки. //Принятие решений в условиях неопределенности. Межвузовский научный сборник. -Уфа: УГАТУ, 1996. -С.38-40.