МОДЕЛІ ТА МЕТОДИ ОПТИМІЗАЦІЇ В ЗАДАЧАХ ОДНОВИМІРНОГО РОЗКРОЮ МАТЕРІАЛУ НА МАШИНОБУДІВНИХ ПІДПРИЄМСТВАХ

brief description

ЧЕРКАСЬКИЙ ДЕРЖАВНИЙ ТЕХНОЛОГІЧНИЙ УНІВЕРСИТЕТ

На правах рукопису

Сагун Андрій Вікторович

УДК 621.7.01:519.876.5(043)

Моделі та методи оптимізації в задачах одновимірного розкрою матеріалу на машинобудівних підприємствах

01.05.02 математичне моделювання та обчислювальні методи

ДИСЕРТАЦІЯ
на здобуття наукового ступеня
кандидата технічних наук

Науковий керівник
Кожухівський Андрій Дмитрович
Доктор технічних наук, професор

Черкаси 2008

ЗМІСТ

Вступ.. 6

РОЗДІЛ 1. ТЕОРЕТИЧНІ АСПЕКТИ МЕТОДІВ ДОСЛІДЖЕНЬ, ТЕОРІЇ АНАЛІЗУ, ОЦІНКИ ТА ОПТИМІЗАЦІЇ ПРОЦЕСІВ ЛІНІЙНОГО
РОЗКРОЮ .. 12
1.1. Загальна характеристика задач розкрою ... 12
1.2. Аналіз моделей та методів розкрою та комплектування . 17
1.3. Особливості моделей одновимірного розкрою матеріалу
різної довжини...... 20
1.4. Аналіз задач пошуку оптимального плану одновимірного розкрою
та комплектування. 23
1.5. Висновки до розділу 1 32

РОЗДІЛ 2. МЕТОДИ ТА ОСНОВНІ МАТЕМАТИЧНІ МОДЕЛІ РОЗВ’ЯЗКУ ЗАДАЧ ОДНОВИМІРНОГО РОЗКРОЮ.................................................................. 34
2.1. Постановка задачі одновимірного розкрою матеріалу .... 34
2.2. Чисельні методи розв’язку задачі лінійного розкрою....... 37
2.2.1. Розв’язок задачі лінійного розкрою методом гілок та меж 38
2.2.2. Розв’язок задачі лінійного розкрою методом січних площин ....... 42
2.2.3 Реалізація методу січних площин в задачі безперервної
релаксації . 44
2.3. Задача генерації карт розкрою..... 48
2.3.1. Генерація карт розкрою при розв’язках безперервної релаксації ...51
2.3.2. Рівняння динамічного програмування для генерації карт розкрою... 53
2.3.3. Методика генерування дискретних проміжків в динамічній
підзадачі лінійного розкрою .. 54
2.4. Генерація карт розкрою за наявності січних ..... 57
2.4.1. Динамічний принцип сортування заготовок за наявності січних .. 59
2.5. Принцип домінантності заготовок в задачі лінійного розкрою ...60
2.5.1. Перевірка принципу домінантності за наявності січних 62
2.6. Висновки до розділу .... 64

Розділ 3. ОПТИМІЗАЦІЯ математичної МОДЕЛІ лінійного РОЗКРОЮ .. 66
3.1. Формулювання ознак оптимальності задачі лінійного розкрою...66
3.2. Формування технологічного фактору оптимізації математичної
моделі лінійного розкрою.68
3.3. Формулювання стохастичних ознак зовнішнього впливу на
математичну модель розкрою..........76
3.4. Формулювання принципу оптимальності . 83
3.4.1.Побудова округлених цілочисельних рішень 83
3.4.2. Метод послідовного уточнення оцінок ітерацій . 86
3.5. Тест оптимальності цілочисельних рішень 88
3.6. Висновки до розділу 3 91

РОЗДІЛ 4. КОМП’ЮТЕРНЕ МОДЕЛЮВАННЯ ЕКСПЕРИМЕНТАЛЬНИХ
ДАНИХ РОЗРОБЛЕНОГО АЛГОРИТМУ РОЗКРОЮ ... 93
4.1. Трансформація базисної матриці розв’язків цільової функції. 94
4.2. Аналіз похибок обчислень цілочисельного округлення .. 99
4.3. Порівняння алгоритму ЛП на базі СМ та евристик БП з іншими
типами алгоритмів при декількох типах вхідних векторів заготовок . 101
4.3.1 Принцип генерування тестових задач ..103
4.3.2. Порівняння розробленого алгоритму з алгоритмом
на базі методу branch and price.... 108
4.4. Характеристика розробленого алгоритму для задач з двома і більше
типами заготовок ...110
4.4.1 Аналіз роботи алгоритму розкрою ... 114
4.5. Аналіз еталонних результатів роботи моделі розкрою....... 122
4.6. Цілочисельна трансформація базису розробленої моделі .124
4.7. Відновлення карти розкрою за допомогою методу branch-and-bound... 130
4.8. Висновки до розділу 4 132

ЗАГАЛЬНІ ВИСНОВКИ.... 132

ДОДАТОК А. Блок-схема алгоритму перевірки домінантності . 137

ДОДАТОК Б. Програмна реалізація алгоритму одновимірного розкрою 140

ДОДАТОК В. Дані розрахунків трансформації базису ... 154

ДОДАТОК Г. Дані розрахунків трансформацій базису серій тестових
прикладів при еталонних параметрах в розробленому алгоритмі 179

ДОДАТОК Д. Акти впровадження у виробництво .. 184

СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ. 187

Вступ

Актуальність теми дослідження. Проблема оптимального використовування сировини має велике значення для багатьох галузей промисловості. Ефективність економії матеріальних ресурсів на теперішній час є найважливішим чинником зниження ціни продукції і конкурентоспроможності підприємства в цілому. Відходи виробництва складають значну частину собівартості виготовленої продукції, а значить, мінімізація відходів є першочерговою задачею.
Одним з найважливіших чинників, що забезпечують економію сортаменту металу, композиційних матеріалів, картону тощо шляхом мінімізації відходів виробництва є їх раціональний розкрій. Серед заходів цього напряму одне з провідних місць займає автоматизація процесу розкрою, що дозволяє значно підвищити коефіцієнт корисного використання матеріалу різного сортаменту і номенклатури.
Розв’язок задачі полягає в отриманні карт розкрою для смуг, стрічок, стрижнів, профілів, прутків та листових заготівок з урахуванням централізованого методу розкрою з одночасним забезпеченням оптимальних норм витрати відповідних ресурсів [1,3,4,34,25,28,86].
Вирішення задачі оптимізації розкроїв є важливою задачею організації виробництва. Відомі розв’язки задач отримання карт одновимірного розкрою матеріалу різної довжини, які не враховують факторів корекції технологічного процесу, тому задачі оптимізації одновимірних розкроїв є актуальними, а розв’язок цих задач доцільно здійснювати засобами лінійного програмування з використанням евристик на базі методу безперервної релаксації (БР) та врахуванням факторів корекції, які мають здатність швидко оптимізувати цей процес та уточнювати розв’язок за рахунок оптимального алгоритму отримання розв’язків при великій номенклатурі заготовок та деталей.
Задачі розкрою-пакування викликають широкий інтерес як у виробництві, так і в теоретичних дослідженнях. Класична задача одновимірного розкрою (1DCSP) розглядається в багатьох публікаціях [15,21,27,35,44,51,67,68,80,97]. Ця задача полягає в мінімізації кількості ідентичних прутків матеріалу, що використовуються для розкрою певного набору заготівок.
Проблемами одновимірного розкрою матеріалів займалися і займаються відомі вчені та дослідники: Л.В.Канторович, Д.М. Малишев, С.Г. Нікітов, А.М.Павлов, Г.Н. Бєлов, Ю.В. Бугаєв, В.А. Кузнєцов, А.І. Єрмаченко, Т.М.Сіразетдінов, К.Г. Андрєєва, Е.А. Мухачова, В.Л. Рвачов, Т.Є.Романова, О.В. Панкратов та інші.
В дисертаційній роботі розглядається загальний випадок отримання оптимальних карт одновимірного розкрою, коли на підприємстві використовується матеріал різної довжини, а оптимальність отриманих карт розкрою враховує вплив на математичну модель факторів зовнішнього середовища. При цьому задача одновимірного розкрою розв’язується в складі підсистеми АСУ виробництвом [1,11,14,18,21,29,39,45,61,63,74,75].
Зв’язок роботи з науковими програмами, планами, темами. Дисертаційну роботу виконано згідно з планом науково-дослідних робіт Черкаського державного технологічного університету в рамках госпрозрахункової науково-дослідної теми № 1-2007 (державний реєстраційний номер № 0107U008093) «Моделювання задачі плоского розкрою матеріалу в структурі інформаційної системи керування виробничим процесом», в якій автор був безпосереднім виконавцем.
Мета і завдання дослідження полягають у розробці та дослідженні математичної моделі одновимірного промислового розкрою матеріалу різної довжини на основі лінійного програмування та методу січних площин з врахуванням факторів корекції математичної моделі.
Для досягнення мети розв’язані такі задачі:
1. Проаналізовані особливості існуючих математичних моделей та розроблена оптимізована математична модель одновимірного розкрою матеріалу різної довжини в АСУ дискретних виробництв;
2. Адаптовані та модифіковані існуючі методи та алгоритми дискретної оптимізації для задачі одновимірного розкрою матеріалу різної довжини в розв’язках безперервної релаксації;
3. Досліджені та сформульовані фактори корекції зовнішніх впливів на математичну модель одновимірного розкрою матеріалу;
4. Синтезовано алгоритм знаходження оптимальних планів розкрою на базі лінійного програмування та методу січних площин;
5. Досліджено ефективність розробленого алгоритму на основі серій тестових прикладів, характерних для машинобудівних підприємств;
6. Проведене комп’ютерне моделювання з метою перевірки достовірності теоретичних результатів дослідження ефективності застосування отриманого алгоритму.
Об’єктом дослідження є технологічні процеси оперативного розкрою у реальному вимірі часу, що враховують перерозподіл матеріалу при впровадженні нових виробів у виробництво.
Предметом досліджень є моделі та алгоритми розкрою в складі задачі ОКП виробництва дискретного машинобудівного виробництва за умов врахування впливу зовнішнього середовища.
Методи дослідження ґрунтуються на використанні теорії і методів системного аналізу виробничих систем, матричного аналізу, методів динамічного та лінійного програмування, методів дискретної оптимізації, теорії і методів дослідження операцій, теорії ймовірностей та математичної статистики, теорії інформаційної взаємодії.
Наукова новизна одержаних результатів полягає в тому, що автором вперше розв’язана задача оптимального одновимірного розкрою матеріалу різної довжини на машинобудівних підприємствах за умов системного поєднання задач стратегічного управління виробничим процесом, корекцією факторів зовнішнього впливу та мінімізацією відходу матеріалу.
Автором отримані наукові результати, які полягають в наступному:
- вперше розроблена бікритеріальна математична модель процесу одновимірного розкрою матеріалу різних довжин на базі лінійного програмування та методів дискретної оптимізації, яка дає змогу отримувати оптимальні розв’язки задачі майже у 4 рази швидше, порівняно з існуючими однокритеріальними математичними моделями;
- удосконалена математична модель одновимірного розкрою матеріалу різної довжини за рахунок введення в неї корегуючих коефіцієнтів, які враховують вплив факторів зовнішнього середовища та підвищують точність отримуваного розв’язку до 10%;
- набула подальшого розвитку модифікація критерію, за яким здійснюється процедура перевірки оптимальності розв’язків, що забезпечує можливість застосування методу послідовного уточнення оцінок для випадку групових одновимірних розкроїв матеріалу різної довжини;
- набула подальшого розвитку модифікація методу генерування карт розкрою за наявності матеріалу різної довжини на основі методу січних перерізів при неявно заданій матриці обмежень, що полягає в комбінації методу ЛП та евристик безперервної релаксації і дозволяє отримувати точний розв’язок задачі генерування групових одновимірних розкроїв засобами ЛП;
- запропонований метод розрахунку верхньої межі цільової функції при застосуванні МСП і евристик, що дає можливість одержання меж цільової функції та конкретизації математичної моделі одновимірного розкрою матеріалу різної довжини.
Практичне значення одержаних результатів роботи полягає в тому, що на основі запропонованої математичної моделі, методів та критеріїв отримано:
- функціональну схему модуля одновимірного розкрою в складі АСУ машинобудівних виробництв, що дає змогу інтегрувати розроблену математичну модель до існуючої АСУ машинобудівного підприємства;
- програмне забезпечення, яке дає змогу збільшити коефіцієнт корисного використання сировини розкрою до 99,8% для окремих класів задач та збільшити частку отримуваних оптимальних КР засобами ЛП до 90% (замість 60%, які існують на сьогоднішній час);
- сформульовані еталонні результати, що дають змогу детермінувати класи практичних задач, що є оптимальними для практичного застосування запропонованої математичної моделі;
- результати порівняння продуктивності розроблених моделей та методів на широкому класі задач з аналогічними, описаними в фахових наукових джерелах.
Модель, що розроблена автором в 2006 році, успішно впроваджена у виробництво на ЗАТ «Кіровоградський завод дозуючих автоматів» у складі інформаційної системи «Інтеграл» та на ВАТ «Черкаський приладобудівний завод».
Особистий внесок здобувача. Дисертація є самостійно виконаною завершеною роботою здобувача. Наукові розробки, узагальнення, висновки та пропозиції, що містяться в дисертацій роботі, одержані автором самостійно.
В публікаціях, написаних в співавторстві, здобувачеві належать: [39] сформульована методика отримання корегуючого коефіцієнту, що враховує вплив факторів зовнішнього середовища на математичну модель одновимірного розкрою; [40] формулюванні процедури цілочисельного округлення безперервного рішення, розширення задачі залишку з врахуванням коефіцієнту технологічної корекції.
Дисертація є самостійно виконаною завершеною роботою здобувача. Наукові розробки, узагальнення, висновки та пропозиції, що містяться в дисертаційній роботі, одержані автором самостійно.
Апробація результатів дисертаційного дослідження. Основні результати дисертаційної роботи доповідались на Міжнародній науково-практичній конференції «Сучасні наукові досягнення - 2007» (Дніпропетровськ, 2007); Міжнародній науково-практичній конференції «Обробка сигналів і негаусівських процесів» (Черкаси, 2007), семінарі Інституту проблем машинобудування НАН України (м. Харків, 2008).
Публікації. Основні наукові результати опубліковані у восьми наукових роботах, серед яких шість у наукових виданнях, які входять до переліку ВАК України та двох виданнях міжнародних науково-практичних конференцій.

Структура та обсяг дисертації. Дисертаційна робота складається зі вступу, чотирьох розділів, висновків, списку використаних літературних джерел (102 найменування). Дисертація містить 20 таблиці, 16 рисунків, 5 додатків на 51 сторінці. Повний обсяг дисертації становить 197 сторінок, у тому числі 134 сторінок основного тексту.

bibliography

ЗАГАЛЬНІ ВИСНОВКИ

Проведені в роботі дослідження щодо розробки моделей та методів оптимізації одновимірного розкрою матеріалу на машинобудівних підприємствах дозволяють зробити висновки, які мають значення для мінімізації кількості відходів крою матеріалу та для подальшого розвитку теорії математичного моделювання та впровадження в практичну діяльність машинобудівних підприємств, а саме:
1. Проведено систематизацію загальних характеристик задач одновимірного розкрою та їх специфічні особливості, що пов’язані з варіантами мінімізації ЦФ розкрою, формуванням матриці обмежень, що складає основу подальшого дослідження.
2. Розроблена бікритеріальна математична модель одновимірного розкрою, яка враховує вплив стохастичних чинників на технологічний процес машинобудівних підприємств.
3. Сформульовано корегуючі чинники математичної моделі, що дає можливість врахувати мультиплікативний вплив технологічних та стохастичних складових на математичну модель, враховуючи важливість знаходження цілочисельних розв’язків задачі одновимірного розкрою шляхом формулювання методу послідовного уточнення оцінок розв’язку та формулювання корегуючих коефіцієнтів і .
4. Модифіковано методику генерування КР з використанням верхньої границі ЦФ, яка виконується з метою генерування стовбців КР за наявності січних та обмеження перебору і стратегії дострокового переривання роботи алгоритму, що дає змогу зменшити час роботи алгоритму в безперервній релаксації.
5. На базі методів ЛП та евристик БР сформульовані ознаки оптимальності математичної моделі одновимірного розкрою, які дають можливість отримати точні результати базисних планів розкрою.
6. Розроблена функціональна схема модуля одновимірного розкрою матеріалу в складі системи АСУ(ОКП) машинобудівного виробництва, що враховує оптимізацію математичної моделі.
7. На основі розв’язків оберненої задачі з модифікованою верхнею межею і матрицею обмежень удосконалена перевірка домінантності заготовок, що знижує розмір задачі генерації розкрою в середньому до 60% без перерізів і до 90% з перерізами.
8. Для тесту оптимальності цілочисельних рішень вдосконалений метод генерації лінійних комбінацій цін матеріалу на основі бітових полів, що зменшує обчислювальну складність задачі.
9. Виявлено переваги розробленого алгоритму на задачах з великим розривом оптимальності і слабкіші результати на задачах з малими комплектностями матеріалу та заготовок (поліпшення коефіцієнту корисного використовування матеріалу в середньому на 8-15% ціни найбільшого прутка) та зменшення часу отримання оптимального розв’язку при генерації КР.
10. Отримані еталонні результати запропонованого методу, які випробувані на визначеному наборі синтетичних і практичних задач, характерних для машинобудівного підприємства.
11. Запропонована модифікація верхньої межі цільової функції в генерації карт розкрою за наявності перерізів, яка розширила область задач, що мають розв’язок за прийнятний з точки зору комерційного продукту час.
Моделі та методи оптимізації задач одновимірного розкрою матеріалу ввійшли до складу підсистеми одновимірного розкрою матеріалу АСУ «Інтеграл» на ЗАТ «Кіровоградський завод дозавтоматів», м. Кіровоград та ВАТ «Черкаський приладобудівний завод», м. Черкаси.

В результаті практичного застосування розроблених моделей та методів в практичних умовах машинобудівного підприємства досягнуто збільшення коефіцієнта використання сировини і зменшення часу отримання оптимальних КР, що підтверджується в наведених довідках про впровадження.

СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ

1. Автоматизированная система управления раскроем проката для непрерывно заготовочного стана / [Б.С. Гусев, О.Г. Шевченко, В.А. Нечипоренко и др.] Металл и литье Украины. 1999. №5-6. С.28-31.
2. Андреев А.Е. Задачи дискретной оптимизации и сложность алгоритмов /
А.Е. Андреев, А.А. Болотов, А.Б. Фролов. М.: МЭИ, 2000. 71 с.
3. Андреева К.Г. Задача рационального использования сырья в рамках CAM-системы предприятия легкой промышленности / К.Г. Андреева,
Д.Н. Малышев, С.Г. Никитов, А.М. Павлов // Автоматизация в промышленности. Декабрь, 2004. С. 14-17.
4. Бажал Ю.М. Економічна теорія технологічних змін / Ю.М. Бажал. К.: Заповіт, 1996. 240 с.
5. Балакирев В.С. Экспериментальное определение динамических характеристик промышленных объектов управления / В.С. Балакирев,
Е.Г. Дудников, Л.М. Цилин. М.: Энергия, 1967. 232 с.
6. Беллман Р. Динамическое программирование / Р. Беллман. М.: Мир, 1960. 424 с.
7. Беллман Р. Прикладные задачи динамического программирования /
Р. Беллман, С. Дрейфус. М.: Мир, 1965. 368 с.
8. Белов Г.Н. Моделирование и решение задачи одномерного раскроя материала различных длин методом отсекающих плоскостей: автореферат диссертации на соискание уч. степ. канд. техн. наук: спец. 05.13.18 «Математическое моделирование, численные методы и комплексы программ» / Г.Н. Белов. Уфа: УГАТУ 2003. С. 6-15.
9. Белов Г.Н. Псевдослучайное генерирование тестовых задач раскроя-упаковки: метод и представительность эксперимента / Г.Н. Белов // Принятие решений в условиях неопределенности: cборник научных трудов. Уфа: УГАТУ. 1998. С. 23 27.
10. Бендат Дж. Измерение и анализ случайных процессов / Дж. Бендат,
А. Пирсол. М.: Мир, 1974. С.38.
11. Бугаев Ю.В. Применение векторной оптимизации на графах для моделирования раскроя лесоматериалов / Ю.В. Бугаев // Изв. вузов. Лесной журнал. 2001. № 3. С. 84 88.
12. Васильева Л.И. Эвристический алгоритм упаковки графов на листах /
Л.И. Васильева, В.М. Картак / Дискретный анализ и исследование операций (Материалы конференции): изд-во инст. математики. Новосибирск, 2000. С. 182.
13. Виленкин С.Я. Статистическая обработка результатов исследования случайных функций / С.Я Виленкин. М.: Энергия, 1979. 320 с.
14. Волкович В.Д. Методы распределенного решения взаимосвязанных оптимизационных задач / В.Д. Волкович, Т.В. Коленов // Техническая кибернетика. 1990. № 6. С. 28 42.
15. Воронин А.В. Прикладные оптимизационные задачи в целлюлозно-бумажной промышленности / А.В. Воронин, В.А. Кузнецов. Петрозаводск: Изд-во ПетрГУ, 2000. 152 с.
16. Воронин А.В. Командные задачи по программированию: организация, задачи и решения / А.В. Воронин, В.А. Кузнецов, Д.В. Подкопаев. Петрозаводск: Изд-во ПетрГУ, 1999. 92 с.
17. Воронин А.В. Программные системы для обучения методам разработки математических моделей оптимизационных задач / А.В. Воронин,
В.А. Кузнецов, В.В. Поляков // НИТ в образовании и управлении: Тезисы Всероссийской конференции. Петрозаводск, 1993. С. 62 64.
18. Воронин А.В. Система математических моделей для построения прогноза и оптимизации выбора управления в АСУ ТП / А.В. Воронин, В.А. Кузнецов, А.Ю. Тарасенко // Труды ПетрГУ, сер. Прикладная математика и информатика. ­ Петрозаводск, 1997. Вып.6 С. 7 18.
19. Гасс С. Линейное программирование: методы и приложения / С. Гасс. М.: Физматгиз. 1961. 303 с.
20. Гимади Э.Х. Задача упаковки в контейнеры: асимптотически точный подход / Э.Х. Гимади, В.В. Залюбовский // Известия высших учебных заведений, Математика. № 12 (427). 1997. С. 25 33.
21. Глиненко Л.К. Основи моделювання технічних систем / Л.К. Глиненко,
О.Г. Сухоносов // Вид-во «Бескид Біт». Львів. 2003. С. 148 169.
22. Годлевский М.Д. RPD алгоритм системной оптимизации развивающихся систем в задачах линейного программирования большой размерности /
М.Д. Голдевский // Кібернетика. 1990. № 2. С. 46 54.
23. Годлевский М.Д. Классификация задач системной автоматизации в линейном программировании / М.Д. Голдевский // Математическое и электронное моделирование в машиностроении. Киев: ИК АН УССР. 1989. С. 53 ­ 65.
24. Грибов А.А. Техника ценных списков, ее программирование и использование в алгоритмах оптимизации / А.А. Грибов, И.М. Давыдова, И.В. Романовский // Исследование операций и статистическое моделирование. Ленинград. ­ Сб. трудов. Вып. 4. 1977. С. 127 166.
25. Дудников Е.Е. Типовые задачи оперативного управления непрерывным производством / Е.Е. Дудников, Ю.М. Цодиков. М.: Энергия, 1979. 272 с.
26. Дюбин Г.Н. Жадные алгоритмы для задачи о ранце: поведение в среднем / Г.Н. Дюбин, А.А. Корбут // Сиб. журн. индустр. математики. 1999. Т. 2, № 2. С. 68 93.
27. Єфіменко Н.А. Постановка та формулювання задач оптимального управління технологічним процесом машинобудівного виробництва / Н.А. Єфименко // Вісник ЧДТУ. № 2. Черкаси, 2002. №2. С. 9 13.
28. Єфіменко Н.А. Оптимальне управління якістю продукції на машинобудівному виробництві / Н.А. Єфименко // Вісник СНУ ім. В. Даля. № 1. Луганськ, 2002. С. 171 173.
29. Єфіменко Н.А. Формальна узагальнена графова модель оперативного управління дискретним виробництвом / Н.А. Єфименко // Вісник ЧДТУ.
№ 3. Черкаси, 2003. С. 55 59.
30. Ермаченко А.И. Рекурсивный метод для решения задач гильотинного прямоугольного раскроя / А.И. Ермаченко, Т.М. Сиразетдинов // Математическое моделирование в решении научных и технических задач (выпуск 2). 1998. С. 23 27.
31. Еремин И.И. Двойственность в линейной оптимизации. / И.И. Еремин. Екатеринбург: ИМИМ. 2001. 179 с.
32. Еремин И.И. Несобственные задачи линейного и выпуклого программирования / И.И. Ерёмин, В.Д. Мазуров, Н.Н. Астафьев. М.: Наука, 1983. 336 с.
33. Жадан В.Г. Численные методы линейного и нелинейного программирования. Вспомогательные функции в условной оптимизации / В.Г. Жадан. М.: ВЦРАН, 2002. 156 с.
34. Задачи оптимизации в АСУ ремонтным производством / А.В. Воронин, В.А. Кузнецов, В.А. Поляков, А.В. Карпов // НИТ в образовании и управлении: Всероссийская конференция. Петрозаводск: Изд-во ПетрГУ, 1993. С. 112. 114.
35. Канторович Л.В. Рациональный раскрой промышленных материалов /
Л.В. Канторович, В.А. Залгаллер. Новосибирск: Наука, 1972. 300 с.
36. Картак В.М. Оптимальная упаковка N мерных параллелепипедов в полубесконечность / В.М. Картак // 12-я Байкальская международная конференция, методы оптимизации и их приложения. Иркутск. 2001. С.18-22.
37. К вопросу о системной оптимизации в многокритериальных задачах линейного программирования / В.М. Глушков, В.С. Михайлевич, В.Л.Волкович, Г.А. Доленко // Кибернетика. 1982. № 3. С. 4 8.
38. Кочетов Ю. Вероятностный поиск с запретами для задачи упаковки в контейнеры / Ю. Кочетов, А. Усманова // Иркутск: ХII Байкальская международная конференция.­ 2000. С. 22-27.
39. Кожухівський А.Д. Математична модель одновимірного розкрою матеріалу з врахуванням коефіцієнта логістичної обробки / А.Д. Кожухівський,
Н.А. Єфіменко, А.В. Сагун // Вісник ЧДТУ. № 4. Черкаси. 2006.
С. 39 41.
40. Кожухівський А.Д. Оптимізація моделі плоского розкрою матеріалу в задачі оперативного планування виробничого процесу / А.Д. Кожухівський,
А.В. Сагун // Вісник ЧДТУ. № 1-2. Черкаси. 2007. С.67-70.
41. Колесник А.Д. Об одной модели марковской случайной эволюции на плоскости / А.Д. Колесник // Аналитические методы исследования эволюций стохастических систем. Киев. 1989. С. 55 61.
42. Колмогоров А.Н. Элементы теории функций и функционального анализа / А.Н. Колмогоров, С.В. Фомин. М.: Наука, 1976. С. 92-98.
43. Комбинированные методы и алгоритмы решения задач дискретной оптимизации большой размерности / Под ред. В.В. Шкурба. М.: Наука. 2000. 353 с.
44. Кузнецов В.А. Задачи раскроя и комплектовки материалов в моделировании производственных процессов / В.А. Кузнецов // Известия высших учебных заведений «Лесной журнал». № 1. Архангельск: изд-во АГТУ. 2004.
С. 111 116.
45. Кузнецов В.А. Задачи объемно-календарного планирования основного производства предприятия ЦБА / В.А. Кузнецов // Новые информационные технологии в ЦБА и энергетике. Материалы IV Международной конференции. Петрозаводск. 2000. С. 32 33.
46. Левитин Е.С. Задачи математического программирования при наличии ограничений экстремального типа / Е.С. Левитин // Обратные задачи математического программирования. М.: ВЦРАН. 1992. С. 20 31.
47. Малышев Д.Н. Исследование и анализ эффективности методов линейного программирования для решения задачи одномерной упаковки /
Д.Н. Малышев, К.Г. //Современные проблемы фундаментальных и прикладных наук. Часть V: Труды XLVI научной конференции / Моск. физ. тех. ин-т. М. Долгопрудный, 2003. С. 97.
48. Малышев Д.Н. Разработка эвристических алгоритмов решения 1DCSP задачи / Д.Н. Малышев, К.Г. Андреева, А.М. Павлов. //Современные проблемы фундаментальных и прикладных наук. Часть V: Труды XLVII научной конференции /Моск. физ. тех. ин-т. М. Долгопрудный, 2004. С. 98.
49. Метод поиска минимума с запретами в задачах двумерного гильотинного раскроя / Э.А. Мухачева, А.И. Ермаченко, Т.М. Сиразетдинов, А.Р. Усманова // Информационные технологии. М.: 2001. №6. С. 25-31.
50. Михалевич В.С. Вычислительные методы исследования и проектирования сложных систем / В.С. Михалевич, В.Л. Волкович. М.: Наука, 1982. 287 с.
51. Мухачева Э.А. Рациональный раскрой промышленных материалов: Применение АСУ / Э.А. Мухачева. М: Машиностроение, 1984. 91 с.
52. Мухачева Э.А. Метод последовательного уточнения оценок: алгоритм и численный эксперимент для задачи линейного раскроя / Э.А. Мухачева,
А.С. Мухачева А.С., Г.Н. Белов // Информационные технологии. № 2. 2000. С. 11 17.
53. Мухачева Э.А., Картак В.М. Модифицированный метод ветвей и границ: алгоритм и численный эксперимент для задачи одномерного раскроя /
Э.А Мухачева, В.М. Картак // Информационные технологии . № 9. 2000. С. 15 22.
54. Норенков И.П. Эвристики и их комбинации в генетических методах дискретной оптимизации / И.П. Норенков // Информационные технологии - М.: 1999. № 1. С. 2 7.
55. Овчінніков П.Т. Вища математика / П.Т. Овчинніков, Ф.П. Яремчик,
В.М. Михайленко. К.: Техніка, 2003. 567 с.
56. Павлов А.А. Алгоритм решения задачи «Минимизация суммарного штрафа при условии, что для некоторых заданий сроки не могут быть нарушены» / А.А. Павлов, Е.Б. Мисюра, О.С. Вакуленко // Проблемы информатизации и управления: Сб. научн. тр. Вып. 2 К.: КМУГА, 1997. С. 58 60.
57. Павлов А.А. Багаторівнева система планування дрібносерійного виробництва в умовах ринку /А.А. Павлов, О.Б. Місюра, О.В. Мельников, О.С. Вакуленко. Київ: НТУУ „КПІ”. „Автоматика 98”. П’ята українська конференція з автоматичного управління. Ч. II. 1998. С. 182 186.
58. Павлов А.А. Организация планирования мелкосерийного производства в условиях рынка / А.А. Павлов, Е.Б. Мисюра, О.С. Вакуленко // Інформаційні управляючі системи і технології / Збірник наукових праць Українського державного морського технічного університету. - Миколаїв. 1998. № 9 (357). С. 104 107.
59. Павлов А.А. ПДС - алгоритм для важко вирішуваних комбінаторних задач. Теорія та методологія розробки / А.А. Павлов, Л.О. Павлова. Ужгород: Поличка Карпатського краю. 1998. 323 с.
60. Петров В.А.. Планирование гибких производственных систем / В.А. Петров. Л.: Машиностроение, ЛО. 1985. 182 с.
61. Планирование производства в условиях АСУ: (Справочник) / К.Ф. Ефетова, В.М. Португал, Б.Е. Тинчук. К.: Техніка, 1984. 135 с.
62. Планирование одномерного раскроя материала различной длины на базе непрерывной релаксации и метода отсекающих плоскостей / Г. Шайтхауэр, А.С. Мухачева, Г.Н. Белов, Э.А. Мухачева // Информационные технологии. 2004. №1. C. 23-27.
63. Разработка моделей, методов и инструментальных средств создания системы планирования и управления функционированием производственных подразделений в составе единой взаимосвязанной системы прогнозного и точного планирования: Отчёт о НИР 2175 (заключительный) / НТУУ «КПИ». Киев. 1999. 221 с.
64. Райбман Н.С. Построение моделей процессов производства / Н.С. Райбман, В.М. Чадеев. М.: Энергия. 1975. С.49-54.
65. Рвачев В.Л. Геометрические приложения алгебры логики / В.Л. Рвачев. К.: Техніка. 1967. С. 146-185.
66. Романовский И.В. Алгоритмы решения экстремальных задач / И.В. Романовский // М.: Наука. 1998. 126 с.
67. Сагун А.В. Аналіз прикладних задач оптимального плану лінійного розкрою і комплектування / А.В. Сагун // Праці Луганського відділення міжнародної академії інформатизації. № 1(14). - Луганськ. 2007. С. 63 66.
68. Сагун А.В. Характеристика алгоритму безперервної релаксації задачі залишку лінійного розкрою / А.В. Сагун // Тези II Міжнародної науково-практичної конференції «Сучасні наукові досягнення - 2007». Т. 6. Дніпропетровськ, вид-во «Наука і освіта». 2007. С. 71 73.
69. Сагун А.В. Генерування стовпців карт лінійного розкрою з врахуванням стохастичності математичної моделі / А.В. Сагун // Тези доповідей Міжнародної науково-практичної конференції «Обробка сигналів і негаусівських процесів». Черкаси: ЧДТУ. 2007. С. 50 52.
70. Сагун А.В. Метод генерування стовпців в задачі лінійного розкрою з урахуванням стохастичного характеру виробничої моделі / А.В. Сагун // Вісник Хмельницького національного університету. Хмельницький. 2007. №3. С. 163-166.
71. Сагун А.В. Моделювання задачі оптимізації карт розкрою з одновимірним характером / А.В. Сагун // Праці Луганського відділення міжнародної академії інформатизації. № 2(15). - Луганськ. 2007. С. 135 139.
72. Сагун А.В. Порівняльний аналіз алгоритмів лінійного розкрою матеріалу / А.В. Сагун. Вісник Хмельницького національного університету. 2007, №6, т.1 (100). С. 194-198.
73. Свешников А.А. Прикладные методы теории случайных функций /
А.А. Свешников. М: Наука. 1968. 345 с.
74. Система перспективного та оперативного управління дрібносерійним виробництвом / А.А. Павлов, О.Б. Місюра, О.В. Мельников, О.С. Вакуленко //”Автоматика 97”. 4-та українська конференція з автоматичного управління. Черкаси. 1997. Т. II. С. 93 99.
75. Система планирования мелкосерийного производства в условиях рынка / А.А. Павлов, Е.Б. Мисюра, О.В. Мельников, Алауи Исмаили Юнес // Проблемы информатизации и управления: (cб. науч. тр.). К.: КМУГА. 1997. С. 9 13.
76. Современные методы идентификации / Под редакцией Эйкхоффа. М.: Мир. 1983. 400 с.
77. Тихонов А.Н. Методы решения некорректных задач / А.Н. Тихонов,
В.Я. Арсенин. М.: Наука. 1979. C. 118-125.
78. Щеглов А.Ю. Метод многокритериальной оптимизации сложных систем с экспертным заданием гипотетически идеального вектора качества /
А.Ю. Щеглов // Изв. ВУЗов. Приборостроение. 1994. Т. 37. С.21-23.
79. Belov G. (2002). A Cutting Plane Algorithm for the One-Dimensional Cutting Stock Problem with Multiple Stock Lengths /G. Belov, G. Scheithauer // European Journal of Operational Research, Special Issue on Cutting and Packing, 141 (2). P. 274 294.
80. Cutting and packing, in: M. Dell’ Amico / H. Dyckhoff, G. Scheithauer, J. Terno, F. Maffioli, S. Martello (Eds.). Annotated Bibliographies in.
81. Degraeve Z. Optimal integer solutions to industrial cutting stock problems: Part 2, Benchmark Results, Technical Report / Z. Degraeve, M. Peeters. Katholieke Universiteit Leuven. 2000. 38 p.
82. Dykhoff H. A typology of cutting and packing problems. / H. Dykhoff. F.R. Germany. 1991. 257 p.
83. Gilmore P.C. A linear programming approach to the cutting-stock problem (Part II) / P.C. Gilmore and R.E. Gomory // Operations Research 11. 1963. P. 863 859.
84. Gilmore P.C. A linear programming approach to the cutting-stock problem (Part I) / P.C. Gilmore and R.E. Gomory // Operations Research 11. 1963. P. 458 487.
85. Marcotte O. Aninstance of the cutting stock problem for which the rounding property does not hold / O. Marcotte // OR Letters 4(5). 1986. P. 239 243.
86. Morton T.E. Heuristic Scheduling Systems / T.E. Morton, D.W. Pentico. Wiley Series in Engineering and Technology Management. Wiley, New York. 1993. P. 89 101.
87. Nicholson T.A.J, Finding the shortest route between two points in a network, Computer Journal 9 / T.A.J. Nicholson. 1966. P. 275 280.
88. Rao С. R., Linear Statistical Inference and Its Applications / Rao C.R. Wiley. 1965. P.188-211.
89. Scheithauer G. A. branch-and-bound algorithm for solving one-dimensional cutting stock problems exactly / G. Scheithauer and J. Terno // Applicationes Mathematica, 23(2). 1995. P. 151 167.
90. Scheithauer G. Facet-defining inequalities for the cutting stock problem / G. Scheithauer and J. Terno // Technical Report MATH-NM-10-1997, TU Dresden. 1997. 28 p. 91
91. Scheithauer G. and J. Terno. The modified integer round-up property of the one-dimensional cutting stock problem / G. Scheithauer and J. Terno// European J. Oper. Res., 84. 1995. P. 562 571.
92. Scheithauer G. and J. Terno. Theoretical investigations on the modified integer round - up property for the one - dimensional cutting stock problems /
G. Scheithauer and J. Terno // Oper Res. Lett, 20. 1997. P. 93 100.
93. Scheithauer G. Theoretical investigations on the modified integer round-up property for the one-dimensional cutting stock problems / G. Scheithauer and J.Terno // Oper.Res. Lett., 20. 1997. P.93-100.
94. Scholl A. BISON: A fast hybrid procedure for exactly solving the one-dimensional bin-backing problem / A. Scholl, R. Klein, C.Jurgens // Computers and Ops.Res.