ОДНОЕТАПНІ ЗАДАЧІ ТЕОРІЇ РОЗКЛАДІВ У БАГАТОРІВНЕВІЙ СИСТЕМІ ПЛАНУВАННЯ : ОДНОЭТАПНЫЕ ЗАДАЧИ ТЕОРИИ РАСПИСАНИЙ В МНОГОУРОВНЕВОЙ СИСТЕМЕ ПЛАНИРОВАНИЯ

Краткое описание

Міністерство освіти і науки, молоді та спорту України

Закарпатський державний університет

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

МЕЛЬНИК ОЛЕНА ОЛЕКСІЇВНА

УДК 004.9 : 519.854.2

ОДНОЕТАПНІ ЗАДАЧІ ТЕОРІЇ РОЗКЛАДІВ

У БАГАТОРІВНЕВІЙ СИСТЕМІ ПЛАНУВАННЯ

05.13.06 – інформаційні технології

Дисертація на здобуття наукового ступеня

кандидата технічних наук

Науковий керівник

Ващук Федір Григорійович,

доктор технічних наук, професор

Ідентичність всіх примірників дисертації

засвідчую:

Вчений секретар спеціалізованої

вченої ради Д 35.052.14                                       А.Є. Батюк

Львів-2013

ПЕРЕЛІК УМОВНИХ СКОРОЧЕНЬ. 6

ВСТУП      7

РОЗДІЛ 1

ІЄРАРХІЧНЕ ПЛАНУВАННЯ У ВИРОБНИЧИХ СИСТЕМАХ З МЕРЕЖЕВОЮ ТЕХНОЛОГІЄЮ І ОБМЕЖЕНИМИ РЕСУРСАМИ.. 14

1.1.  Виробничі системи, що мають мережеве представлення технологічних процесів та обмежені ресурси. Постановка задачі планування. 14

1.2.  Вимоги до розробки виробничого планування в організаційно-виробничих системах, що мають мережеве представлення технологічних процесів й обмежені ресурси. 20

1.3.  Опис ієрархічної моделі планування у складних виробничих системах       24

1.4.  Місце одноетапних задач теорії розкладів в ієрархічній системі планування, що має мережеве представлення технологічних процесів та обмежені ресурси  27

1.5.  Аналітичний огляд існуючих методів розв’язання задач одним приладом з налагодженнями. 28

1.5.1. Оптимізація та гібридні методи. 32

1.5.2. Евристики. 35

1.6.  Актуальність і обґрунтованість обраної теми. 39

1.7.  Висновки до розділу 1. 39

РОЗДІЛ 2

МАТЕМАТИЧНЕ ЗАБЕЗПЕЧЕННЯ РОЗВ’ЯЗАННЯ ЗАДАЧ МІНІМІЗАЦІЇ СУМАРНОГО ВИПЕРЕДЖЕННЯ І ЗАПІЗНЕННЯ ПРИ ВИКОНАННІ ЗАВДАНЬ ОДНИМ ПРИЛАДОМ З НАЛАГОДЖЕННЯМИ.. 40

2.1.  Постановка задачі мінімізації сумарного випередження і запізнення при виконанні груп завдань одним приладом з налагодженнями. 41

2.2.  Постановка задачі мінімізації сумарного випередження і запізнення при виконанні завдань одним приладом з налагодженнями, залежними від послідовності 43

2.3.  Основні евристики побудови розкладів задач мінімізації сумарного випередження і запізнення при виконанні завдань одним приладом з налагодженнями (1-МВЗН) 44

2.3.1. Обґрунтування ефективності використання методу мінімізації сумарного випередження і запізнення для розв’язання задач 1-МВЗН..... ..... 44

2.3.2. Обґрунтування вибору методу розв’язання задачі МВЗ для ефективного розв’язання задачі 1-МВЗН.. 45

2.3.3. Інші евристики, покладені в основу розв’язання задачі
1-МВЗН      45

2.4.  Опис і обґрунтування методу розв'язання задачі 1-МВЗН для груп завдань у разі, коли дозволені простої приладу. 52

2.5.  Опис і обґрунтування методу розв'язання задачі 1-МВЗН для груп завдань у разі, коли простої приладу заборонені 56

2.6.  Опис і обґрунтування методів розв'язання задачі 1-МВЗН у разі, коли налагодження залежать від послідовності завдань. 58

2.7.  Ілюстративні приклади розв’язання задач запропонованими методами        58

2.7.1. Приклад розв’язання задачі 1-МВЗН для груп завдань, коли дозволені простої приладу. 58

2.7.2. Приклад розв’язання задачі 1-МВЗН для груп завдань, простої приладу заборонені 71

2.8.  Висновки до розділу 2. 79

РОЗДІЛ 3

МОДЕЛЮВАННЯ ТА СТАТИСТИЧНЕ ДОСЛІДЖЕННЯ АЛГОРИТМІВ А1-А4    81

3.1.  Алгоритм розв’язання задачі МСЗ. 81

3.1.1. Підготовчий етап. 83

3.1.2. Етап оптимізації 83

3.2.  Алгоритм МВЗ. 90

3.3.  Алгоритм А1. 91

3.4.  Алгоритм А2. 93

3.5.  Алгоритм А3. 94

3.6.  Алгоритм А4. 95

3.7.  Система статистичного моделювання, структура, інформаційне забезпечення. 98

3.7.1. Загальна концепція моделювання. 97

3.7.2. Структура системи моделювання. 99

3.7.3. Система моделювання для дослідження ефективності алгоритмів А1-А4. 101

3.8.  Результати статистичного дослідження алгоритмів А1–А4. Аналіз та висновки. 105

3.9.  Порівняння алгоритмів з відомими методами. 115

3.10.Висновки до розділу 3. 119

РОЗДІЛ 4

РЕАЛІЗАЦІЯ АЛГОРИТМІВ А1-А4 У БАГАТОРІВНЕВІЙ СИСТЕМІ ПЛАНУВАННЯ З МЕРЕЖЕВИМ ПРЕДСТАВЛЕННЯМ ТЕХНОЛОГІЧНИХ ПРОЦЕСІВ ТА ОБМЕЖЕНИМИ РЕСУРСАМИ.. 121

4.1.  Загальна схема багаторівневої системи планування з мережевим представленням технологічних процесів та обмеженими ресурсами............. ............. 121

4.1.1. Перший рівень моделі 127

4.1.2. Другий рівень моделі 130

4.1.3. Третій рівень моделі 132

4.2.  Вхідні та вихідні дані алгоритмів А1-А4. 134

4.3.  Інформаційні технології  алгоритмів А1-А4. 136

4.4.  Ілюстративний приклад складання розкладу в окремій системі з мережевою технологією та обмеженими ресурсами за критерієм МВЗН.. 145

4.5.  Висновки до розділу 4. 160

ВИСНОВКИ   161

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

ДОДАТКИ 182

Додаток А 182

Додаток Б    184

Додаток В    185

СКОРОЧЕНЬ
 

 

Позначення	Пояснення
1-МВЗН	Мінімізація випередження та запізнення при виконанні завдань одним приладом з налагодженнями
EBSR	Extraction and backward-shifted reinsertion – вилучення і повторна вставка зі зрушенням назад
EFSR	Extraction and forward-shifted reinsertion – вилучення і повторна вставка зі зрушенням вперед
UML	Unified modelling language – уніфікована мова моделювання
БД	База даних
ГТ	Групова технологія
МВЗ	Мінімізація сумарного випередження і запізнення відносно директивних строків при виконанні незалежних завдань одним приладом
МЗМ	Мінімізація сумарного зваженого моменту закінчення виконання завдань
МСЗ	Мінімізація сумарного запізнення завдань відносно директивних строків
МСЗПП	Мінімізація сумарного запізнення відносно директивних строків виконання завдань паралельними приладами
ОВС	Організаційно-виробничі системи
ПДС-алгоритм	Алгоритм з поліноміальною та експоненційною складовими
ТР	Теорія розкладів

ВСТУП

Актуальність теми. Планування – процес прийняття рішень, що має важливе значення як у виробничих системах, так і у сфері різноманітних послуг. Постановкам задач планування в складних системах та методам їх розв’язання присвячені наукові праці провідних вітчизняних і зарубіжних вчених: Глушкова В.М., Скуріхіна В.І., Згуровського М.З., Морозова А.О., Павлова О.А., Ващука Ф.Г., Шкурби В.В., Танаєва В.С., Гордона В.С., Шафранського В.С., Подчасової Т.П., Бейкера К.Р., Соурда Ф., Бітрана Г.Р., Чена Б., Пінедо М., Хакса А.Ц., Лоулера Е.Л., Лікмена Р.С., Лоуренса С. та ін. Найпоширенішими є виробничі системи з мережевим представленням технологічних процесів та обмеженими ресурсами. Їх частка становить до 80% всіх типів виробничих систем. Це, зокрема, дрібносерійні виробництва, виробничі цехи, виробництва на замовлення, виробництва з виготовлення партій продукції, будівельні виробництва, системи планування та управління проектами тощо.

В умовах виробництва необхідна взаємодія та узгодженість планів на всіх рівнях ієрархічної системи. Але через їх складність процеси об’ємного планування і календарного планування з урахуванням технологій виробництва і наявності ресурсів сьогодні розглядаються окремо.

Аналіз наукових публікацій показує, що оптимальним для вирішення задачі планування в ієрархічній системі є підхід, в основі якого є об’єднання об’ємного і календарного планування по низці найбільш поширених критеріїв з урахуванням технологічних вимог, наявності ресурсів, завантаження устаткування та інших особливостей виробництва. Зазначений підхід реалізовано Згуровським М.З. та Павловим О.А. в рамках єдиної багаторівневої системи планування з мережевим представленням технологічних процесів й обмеженими ресурсами [122]. Ця система представлена комплексом взаємозв’язаних моделей дискретної оптимізації і високоефективних методів розв’язання задач планування. На основі зазначеного підходу за допомогою точних алгоритмів з поліноміальною та експоненційною складовими (ПДС-алгоритмів) для одного приладу успішно розв'язано такі задачі: мінімізації сумарного зваженого моменту виконання взаємозв’язаних завдань (що є ключовою при побудові пріоритетно-упорядкованої послідовності, яка визначає порядок призначення завдань на виконання), мінімізації сумарного запізнення при виконанні завдань; мінімізації сумарного запізнення відносно директивних строків виконання завдань паралельними приладами. Модульна структура програмного забезпечення системи дає змогу розширяти її функції, включати додаткові критерії оптимальності. Однак, в системі не розглядаються задачі складання розкладів за критерієм мінімізації сумарного випередження і запізнення з урахуванням налагоджень обладнання як при виконанні завдань групами, так і окремих завдань.

Більшість відомих напрацювань, присвячених проблемі розв'язання задач планування, пов’язаних з налагодженням приладів, передбачають одержання оптимального розв'язку на основі методів: гілок та границь, динамічного планування або частково цілочисельного програмування, як правило, для задач невеликої розмірності (до 20 завдань). Проте недостатньо досліджені питання розв’язання задач оптимізації одним приладом з налагодженнями евристичними методами та для великої кількості завдань.

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

Отже, наукова задача розроблення методів вирішення задач теорії розкладів за критерієм мінімізації сумарного випередження і запізнення з урахуванням налагодження приладів у багаторівневій системі з мережевим представленням технологічних процесів та обмеженими ресурсами є актуальною, важливою для науки і промисловості України та потребує подальших досліджень з метою отримання свого ефективного розв'язку.

Зв’язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконана в рамках планових навчальних та науково-дослідних робіт кафедри "Програмне забезпечення систем" Закарпатського державного університету, зокрема, за темою "Використання моделей дискретної оптимізації в задачах планування та управління в інформаційно-управляючих системах та технологіях".

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

Для досягнення поставленої мети необхідно вирішити такі задачі:

–       провести дослідження ієрархічної моделі планування та управління в системах з мережевим представленням технологічних процесів і обмеженими ресурсами та її математичного забезпечення; визначити моделі задач, включення яких до складу зазначеного забезпечення дасть можливість підвищити ефективність системи;

–       побудувати нові методи мінімізації сумарного випередження і запізнення груп завдань на одному приладі з налагодженнями у разі, коли дозволені простої приладу, і для випадку, коли простої обладнання заборонені;

–       розробити нові методи мінімізації сумарного випередження і запізнення на одному приладі з налагодженнями, залежними від послідовності завдань;

–       створити систему моделювання та провести статистичне дослідження ефективності розроблених методів розв’язання сформульованих задач;

–       розробити інформаційні технології та реалізувати у вигляді алгоритмів побудовані методи розв’язання досліджуваних задач в багаторівневій системі планування з мережевим представленням технологічних процесів та обмеженими ресурсами.

Об’єктом дослідження є процес планування в багаторівневій системі з мережевим представленням технологічних процесів та обмеженими ресурсами.

Предмет дослідження – сучасні методи та алгоритми для важкорозв’язуваних задач комбінаторної оптимізації, зокрема задач теорії розкладів для одного приладу; сучасні інформаційні технології планування та управління в багаторівневих системах з мережевим представленням технологічних процесів та обмеженими ресурсами.

Методи дослідження. При проведенні досліджень у дисертаційній роботі використовувалися методи: комбінаторної оптимізації, теорії розкладів, дослідження операцій. Для експериментальних досліджень використано статистичні методи обробки інформації, методи об’єктно-орієнтованого програмування в середовищі .NET.

Наукова новизна одержаних результатів полягає у наступному:

вперше розроблено:

–       метод розв’язання задачі сумарного випередження і запізнення груп завдань на одному приладі з налагодженнями (дозволені простої приладу);

–       метод розв’язання задачі сумарного випередження і запізнення груп завдань на одному приладі з налагодженнями (простої обладнання заборонені);

–       два методи розв’язання задачі сумарного випередження і запізнення завдань на одному приладі з налагодженнями, залежними від послідовності;

удосконалено:

–       математичне і алгоритмічне забезпечення планування та управління в багаторівневій системі з мережевим представленням технологічних процесів та обмеженими ресурсами за рахунок включення розроблених моделей і нових ефективних методів розв’язання сформульованих задач виконання завдань на одному приладі з налагодженнями за критерієм мінімізації сумарного випередження і запізнення.

Практичне значення одержаних результатів. Отримані результати досліджень є основою вдосконалення багаторівневої системи планування з мережевим представленням технологічних процесів та обмеженими ресурсами, запропонованої Згуровським М.З. та Павловим О.А., шляхом включення до її складу задачі мінімізації сумарного випередження і запізнення при виконанні завдань одним приладом з налагодженнями та методів і алгоритмів її розв’язання, що дало змогу підвищити ефективність системи, розширити її функції та коло прикладних задач її застосовування. Це обумовлено тим, що більшість практичних задач складання розкладів пов’язані з налагодженнями приладів, з іншого боку відсутність врахування налагоджень при плануванні може призвести до збільшення тривалості виготовлення виробів, їх вартості та штрафів за зрив директивних строків виконання робіт. Побудована ієрархічна модель може використовуватися для планування та управління в складних організаційно-виробничих системах.

Створено систему моделювання, що дало змогу автоматизувати процес виконання розроблених алгоритмів та провести статистичне дослідження їх ефективності.

Усі запропоновані методи і алгоритми мають самостійне значення, а також є основою для створення евристик для застосування в складніших моделях. Зокрема, практичні задачі для багатьох приладів розкладаються на підзадачі для одного приладу, які розв’язуються окремо, що суттєво спрощує розв’язання багатоприладних задач. Це обумовлює можливість широкого використання запропонованих моделей і методів у системах планування різного призначення.

Результати дисертаційного дослідження використано в ТОВ "СТС" для диспетчеризації виробничих процесів, в ТОВ "Сезпарксервіс" для удосконалення методології багаторівневого планування. Теоретичні та практичні результати використовуються у навчальному процесі Закарпатського державного університету.

Особистий внесок здобувача. Усі наукові результати дисертаційної роботи отримані автором самостійно. У друкованих працях, опублікованих у співавторстві, автору належать:

–       система моделювання [116];

–       інформаційні технології та реалізація у вигляді алгоритмів розроблених методів розв’язання досліджуваних задач у багаторівневій системі планування та управління з мережевим представленням технологічних процесів та обмеженими ресурсами [116, 129];

–      

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

У дисертаційній роботі розв’язано актуальну наукову задачу розроблення ефективних методів вирішення задач теорії розкладів за критерієм мінімізації сумарного випередження і запізнення одним приладом з налагодженнями в багаторівневій системі планування з мережевим представленням технологічних процесів та обмеженими ресурсами. При цьому отримано такі основні результати:

1.           Проведено аналіз сучасного стану розвитку методів і алгоритмів розв'язання задач теорії розкладів за критерієм мінімізації сумарного випередження і запізнення одним приладом, що дало можливість визначити недоліки методів, алгоритмів і технологій планування процесів.

2.           Обґрунтовано актуальність та необхідність вирішення наукової задачі розроблення методів розв'язання задач теорії розкладів за критерієм мінімізації сумарного випередження і запізнення з урахуванням налагодження приладів, а також необхідність вдосконалення технології планування процесів для автоматизації виконання завдань виробничого управління в багаторівневій системі з мережевим представленням технологічних процесів та обмеженими ресурсами, що дасть можливість у процесі планування враховувати тривалість налагодження обладнання.

3.           У результаті аналізу ієрархічної моделі планування та управління в складних виробничих системах, що враховують мережеве представлення технологічних процесів та обмежені ресурси, запропонованій Згуровським М.З. та Павловим О.А., показано, що її вдосконалення шляхом включення до складу математичного забезпечення моделей задач планування, пов’язаних з налагодженням приладів, дасть можливість максимізувати прибуток підприємств, зменшити собівартість продукції та забезпечити раціональніше використання устаткування.

4.           Вперше показано взаємозв’язок між методами розв’язання задач мінімізації сумарного запізнення завдань відносно директивних строків (МСЗ), мінімізації сумарного випередження і запізнення відносно директивних строків при виконанні незалежних завдань одним приладом (МВЗ), мінімізації сумарного випередження та запізнення при виконанні завдань одним приладом з налагодженнями (1-МВЗН), що дало змогу на основі методів розв’язання задач МСЗ та МВЗ побудувати нові ефективні евристичні методи розв’язання задачі 1-МВЗН, які, на відміну від існуючих, дають можливість одержати розв’язок задач великої розмірності.

5.           Розроблено нові евристичні методи мінімізації сумарного випередження та запізнення при виконанні завдань одним приладом з налагодженнями для таких задач: у разі, коли простої обладнання дозволені (алгоритм А1), для випадку, коли простої обладнання заборонені (алгоритм А2), у разі, коли налагодження залежать від послідовності завдань (алгоритми А3, А4), що дало змогу отримати високоякісні наближені розв’язки з невеликими часовими витратами, у тому числі для задач великої розмірності.

6.           Створено систему моделювання, що дало змогу автоматизувати процес виконання розроблених алгоритмів А1-А4 та провести статистичне дослідження їх ефективності.

7.           Обґрунтовано, що розроблені евристичні методи забезпечують одержання розв’язків оптимізаційних задач з урахуванням налагодження приладів з високою якістю за значно менший час порівняно з методом гілок і границь (близько 17–407.5 разів для досліджених задач розмірністю 10-25 завдань, для яких можливе застосування точного методу; середнє відхилення значення функціоналу від оптимального знаходиться в межах 1-8.3%).

8.           Обґрунтовано, що ефективність алгоритмів А3, А4 якісно залежить від визначення околу поточних рішень. Алгоритм А3, який базується на розробленій евристиці, забезпечує одержання розв’язку за середній час менший у 23.8 разів порівняно з алгоритмом А4. Алгоритм А4, який базується на розробленій евристиці та відомому методі локального пошуку, дає змогу одержати більш точні результати, оскільки розглядає більший окіл поточних рішень (середнє відхилення значення функціоналу від оптимального для алгоритму А4 становить близько 2%, для А3 − близько 8,3%).

9.           Формалізовано змістову постановку задачі 1-МВЗН, що дало змогу вдосконалити модель багаторівневої системи планування з мережевим представленням технологічних процесів та обмеженими ресурсами шляхом включення до її третього рівня методів розв’язання задачі 1-МВЗН, реалізованих у вигляді  алгоритмів А1–А4 .

10.      Розроблено інформаційні технології та вдосконалено програмне забезпечення багаторівневої системи планування з мережевим представленням технологічних процесів та обмеженими ресурсами шляхом включення до її складу задачі 1-МВЗН та методів її розв’язання (алгоритмів А1–А4), що дало змогу підвищити ефективність системи, розширити її функції та коло прикладних задач її застосовування.

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

3.           A survey of scheduling problems with setup times or costs / Ali Allahverdi,
C.T. Ng, T.C.E. Cheng, Mikhail Y. Kovalyov // European Journal of Operational Research. – 2008. – Vol.187, №3. – P. 985-1032.

5.           Allahverdi A. A review of scheduling research involving setup considerations / Ali Allahverdi, Jatinder N.D Gupta, Tariq Aldowaisan // Omega. – 1999. –
Vol. 27(2). – P. 219-239.

8.           Azizoglu M. Scheduling job families about an unrestricted common due date on a single machine / Azizoglu M., Webster S. // International Journal of Production Research. – 1997. – Vol. 35. – P. 1321-1330.

9.           Baker K.R. Finding an optimal sequence by dynamic programming: an extension to precedence-related tasks / Kenneth R. Baker, Linus E. Schrage // Operations Research. – 1978. – № 26(1). – Р.111-120.

Sequencing with earliness and tardiness penalties: a review /
Baker K.R., Scudder G.D. // Operations Research. – 1990. –№ 38(1). –
Р. 22–36.

11.      Baptiste P. Batching identical jobs / Baptiste P. // Mathematical Methods of Operations Research. – 2000. – Vol. 52. – P. 355-367.

12.      Baptiste P. On minimizing total tardiness in a serial batching problem /
Baptiste P., Jouglet A. // RAIRO Recherche Operationnelle. – 2001. – Vol. 35. – P. 107-115.

2011” (Singapore, 6-9 December 2011). – 2011. –
P. 794 – 798.

15.      Bitran G.R. One the design of hierarchical production planning systems /
Bitran G.R., Hax A.C. // Decision Science. – 1977.– Vol.8. – P. 28-55.

16.      Chang P.C. Genetic algorithms applied in BOPP film scheduling problems: minimizing total absolute deviation and setup times / Chang P.C., Hsieh J.C., Wang Y.W. // Applied Soft Computing. – 2003. – Vol. 3. – P. 139-148.

17.      Chang T.Y. A heuristic algorithm to minimize total weighted tardiness on a single machine with release dates and sequence-dependent setup times /
Chang T.Y., Chou F.D., Lee C.E. // Journal of the Chinese Institute of Industrial Engineers. – 2004. – Vol. 21. – P. 289-300.

19.      Cheng T.C.E. A note on the complexity of family scheduling to minimize the number of late jobs / T. C. Edwin Cheng, Zhaohui Liu, Yakov M. Shafransky // Journal of Scheduling. – 2001. – Vol.4, №4. − Р. 225-229.

20.      Cheng T.C.E. A stronger complexity result for the single machine multi-operation jobs scheduling problem to minimize the number of tardy jobs /
Cheng T.C.E., Ng C.T., Yuan J.J. // Journal of Scheduling. – 2003. – Vol.6,
№6. − Р. 551-555.

21.      Cheng T.C.E. The single machine batching problem with family setup times to minimize maximum lateness is strongly NP-hard / Cheng T.C.E., Ng C.T.,
Yuan J.J. // Journal of Scheduling. – 2003. – Vol.6, №5. − Р. 483-490.

A simple model for optimizing the single machine early/tardy problem with sequence dependent setups / B. JAY Coleman // Production and Operations Management. – 1992. – Vol. 1 (2). – P. 225–228.

Single-machine scheduling with early and tardy completion costs /
J. Steve Davis, John J. Kanet // Naval Research Logistics. – 1993. – Vol. 40 (1). – Р. 85–101.

26.      Dunstall S. Lower bounds and algorithms for flowtime minimization on a single machine with set-up times / Dunstall S., Wirth A., Baker K. // Journal of Scheduling. – 2000. – Vol.3, №1. − Р. 51-69.

27.      Eren T. A bicriteria scheduling with sequence-dependent setup times / Eren T., Guner E. // Applied Mathematics and Computation. – 2006. – Vol.179(1). –
P. 378-385.

A dual algorithm for the one-machine scheduling problem / Marshall L. Fisher // Mathematical Programming. –1976. – Vol. 11 (1). – P. 229–251.

Minimizing weighted absolute deviation in single machine scheduling / Fry T.D., Armstrong R.D., Blackstone J.H. // IIE Transactions. – 1987. –
Vol. 19 (4). – Р. 445–450.

One-processor scheduling with symmetric earliness and tardiness penalties / Garey M.R., Tarjan R.E., Wilfong G.T. // Mathematics of Operations Research. – 1988. – Vol.13, № 2. – Р. 330-348.

32.      Gendreau M. A divide and merge heuristic for the multiprocessor scheduling problem with sequence dependent setup times / Michel Gendreau, Gilbert Laporte, Eduardo Morais Guimaraes // European Journal of Operational Research. – 2001. – Vol. 133, №1. – P. 183-189.

33.      Gerodimos A.E. Minimizing weighted absolute deviation in single machine scheduling / Gerodimos A.E., Glass C.A., Potts C.N. // IIE Transactions. – 2001. – Vol. 33 (11). – Р. 975-984.

34.      Gerodimos A.E. Scheduling the production of two-component jobs on a single machine / Alex E. Gerodimos, Celia A. Glass, Chris N. Potts // European Journal of Operational Research. – 2000. – Vol. 120, № 2. – P. 250-259.

.

36.      Graves G.H. Scheduling maintenance and semiresumable jobs on a single machine / Gregory H. Graves, Chung-Yee Lee // Naval Research Logistics. – 1999. – Vol. 46 (7). – Р. 845-863.

37.      Group technology in a hybrid flowshop environment: A case study / [Carlos Andres, Jose Miguel Albarracin, Guillermina Tormo, Eduardo Vicens, Jose Pedro Garcia-Sabater] // European Journal of Operational Research. – 2005. – Vol.167, №1. – P. 272-281.

53-69.

39.      Kanet J.J. Scheduling with inserted idle time: Problem taxonomy and literature review / Kanet J.J., Sridharan V. // Operations Research. – 2000. – №48 (1). –
Р. 99–110.

40.      Karabati S. Minimizing sum of completion times on a single machine with sequence-dependent family setup times / Karabati S., Akkan C. // Journal of the Operational Research Society. – 2006. – Vol. 57. – P. 271-280.

http://dx.doi.org/10.1016/j.cie.2011.08.019.

Minimizing mean tardiness and earliness in single-machine scheduling problems with unequal due dates / Kim Y.-D., Yano C.A. // Naval Research Logistics. – 1994. – Vol. 41 (7). – Р. 913–933.

44.      Koulamas C. Single-machine scheduling problems with past-sequence-dependent setup times / Christos Koulamas, George J. Kyparisis // European Journal of Operational Research. – 2008. – Vol. 187, № 3. – P. 1045–1049.

45.      Laguna M. A heuristic for production scheduling and inventory control in the presence of sequence-dependent setup times / Manuel Laguna // IIE Transactions. – 1999. – Vol. 31 (2). – Р. 125-134.

46.      Lawrence S. Supplement to resource constrained project scheduling: An experimental investigation of heuristic scheduling techniques / Lawrence S. –Pittsburgh: Graduate School of Industrial Administration, Carnegie-Mellon University, 1984. – 120 p.

– Vol. 22 (1). – P. 31-40.

48.      Lee S.M. Job scheduling with dual criteria and sequence-dependent setups: mathematical versus genetic programming / Sang M. Lee, Arben A. Asllani // Omega. – 2004. – Vol. 32(2). –145-153.

51.      Liaee M.M. Scheduling families of jobs with setup times / Liaee M.M., Emmons H. // International Journal of Production Economics. – 1997. – Vol. 51. –
P. 165-176.

52.      Liu Z. Minimizing total completion time subject to job release dates and preemption penalties / Zhaohui Liu, T.C. Edwin Cheng // Journal of Scheduling. – 2004. – Vol.7, №4. − Р. 313-327.

53.      Liu Z. Scheduling with job release dates, delivery times and preemption penalties / Liu Z., Cheng T.C.E. // Information Processing Letters/ – 2002. – Vol. 82. – P. 107-111.

54.      Liu Z., Yu W. Minimizing the number of late jobs under the group technology assumption / Liu Z., Yu W. // Journal of Combinatorial Optimization. – 1999. – Vol. 3. – P. 5-15.

/ Mehdi Mahnama, Ghasem Moslehia // Engineering Optimization. – 2009. – Volume 41, Issue 6. – P. 521-536.

Pablo Moscato // New Ideas in Optimization. – Maidenhead (UK): McGraw-Hill Ltd., 1999. –
P. 219-234.

60.      Moscato P. On evolution, search, optimization, genetic algorithms and martial arts: towards memetic algorithms / Moscato P. // Technical Report Caltech Concurrent Computation Program. – Pasadena: California Institute of Technology, 1989. – Report 826.

61.      Ng C.T. Strong NP-hardness of the single machine multi-operation jobs total completion time scheduling problem / Ng C.T., Cheng T.C.E., Yuan J.J. // Information Processing Letters. – 2002. – Vol. 82. – P. 187-191.

/ R. Tavakkoli-Moghaddam,
G. Moslehi, M. Vasei, A. Azaron // Applied Mathematics and Computation. – 2005. – Volume 167, Issue 2. – P. 1430–1450.

The Single Machine Early/Tardy Problem / Peng Si Ow, Thomas E. Morton // Management Science. – 1989. – Vol.35, № 2. – Р. 177–191.

65.      Pan J.C.H. A heuristic approach for single-machine scheduling with due dates and class setups /  Jason Chao-Hsien Pan, Jen-Shiang Chen, Hung-Liang Cheng // Computers & Operations Research. – 2001. – Vol. 28, № 11. – P. 1111-1130.

66.      Park Y. Scheduling jobs on parallel machines applying neural network and heuristic rules / Youngshin Park, Sooyoung Kim, Young-Hoon Lee // Computers & Industrial Engineering. – 2000. – Vol.38, №1. – P. 189-202.

Michael Pinedo. – New Jersey: Prentice Hall, 2002. – 586 p.

68.      Potts C.N. Scheduling with batching: A review / Chris N. Potts, Mikhail Y. Kovalyov // European Journal of Operational Research. – 2000. – Vol.120, №2. – P. 228-249.

–
2012. – Vol. 23 (4). – P.1207-1224.

Troyes: Univ. of Technol. of Troyes, 2009. –
P. 23-27.

A comparison of lower bounds for the single-machine early/tardy problem / Schaller J. // Computers & Operations Research. – 2007. – Vol. 34,
№ 8. – P. 2279–2292.

78.      Schaller J. Scheduling a flowline manufacturing cell with sequence dependent family setup times / Jeffrey E. Schaller, Jatinder N.D. Gupta, Asoo J. Vakharia // European Journal of Operational Research. – 2000. – Vol.125, №2. –
P. 324-339.

79.      Schaller J. Scheduling on a single machine with family setups to minimize total tardiness / Jeffrey Schaller // International Journal of Production Economic. – 2007. – Vol. 105, № 2. – P. 329-344.

80.      Schaller J. Single machine scheduling with family setups to minimize total earliness and tardiness / Jeffrey E. Schaller, Jatinder N.D. Gupta // European Journal of Operational Research. – 2008. – Vol. 187, № 3. – P. 1050–1068.

81.      Schaller J.E. Single machine scheduling with family setups to minimize total earliness and tardiness / Schaller J.E., Gupta J.N.D. // European Journal of Operational Research. − 2008. − Vol. 187, №3. – P. 1050–1068.

82.      Scheduling multi-operation jobs on a single machine / Gerodimos A.E., Glass C.A., Potts C.N., Tautenhahn T. // Annals of Operations Research. – 1999. – Vol. 92. – P. 87-105.

83.      Sequencing and scheduling: Algorithms and complexity / Lawler E.L.,
Lenstra J.K., Rinnooy Kan A.H.G., Shmoys D.B. // Handbook in Operations Research and Management Science. – 1993. – Vol. 4. Logistics of Production and Inventory. – P. 445-522.

84.      Shin H.J. A tabu search algorithm for single machine scheduling with release times, due dates, and sequence-dependent set-up times / Shin H.J., Kim C.O., Kim S.S. // International Journal of Advanced Manufacturing Technology. – 2002. – Vol. 19. – P. 859-866.

Babak Shirazi, Hamed Fazlollahtabar, Navid Sahebjamnia // Materials and Manufacturing Processes. – 2010. – Vol. 25, № 6. – P. 515-525.

86.      Shufeng W., Yiren Z. Scheduling to minimize the maximum lateness with multiple product classes in batch processing / Shufeng W., Yiren Z. // Proceedings of IEEE Region Io Conference On Computers, Communications, Control And Power Engineering "IEEE TENCON’02" (Beijing (China), 28-31 Oct. 2002). – 2002. – P. 1595-1598.

87.      Simons J.V. A case study of batching in a mass service operation / Simons J.V., Russel G.R. // Journal of Operations Management. – 2002. – Vol. 20. –
P. 577-592.

88.      Single machine batch scheduling problem with family setup times and release dates to minimize makespan / Yuan J.J., Liu Z.H., Ng C.T., Cheng T.C.E. // Journal of Scheduling. – 2006. – Vol.9, №6. − Р. 499-513.

89.      Single machine serial-batching scheduling problem with a common batch size to minimize total weighted completion time / Yuan J.J., Lin Y.X., Cheng T.C.E., Ng C.T. // International Journal of Production Economics. – 2007. – Vol. 105,
№ 2. – P. 402–406.

Earliness–tardiness scheduling with setup considerations / F. Sourd // Computers & Operations Research. – 2005. – Vol. 32, № 7. – P. 1849–1865. 

New exact algorithms for one-machine earliness-tardiness scheduling / Francis Sourd // INFORMS Journal on Computing. – 2009. –Vol. 21 (1). –
P. 167-175.

The one-machine problem with earliness and tardiness penalties /
Sourd F., Kedad-Sidhoum S. // Journal of Scheduling. – 2003. – Vol.6, №6. −
Р. 533–549.

Adjacent orderings in single-machine scheduling with earliness and tardiness penalties / Wlodzimierz Szwarc // Naval Research Logistics. – 1993. – Vol. 40 (2). – Р. 229–244.

Just-in-Time Systems / editors: Roger Z. Ríos-Mercado, Yasmín A. Ríos-Solís. – Springer, 2012. – P. 21-40. – (Springer Optimization and Its Applications; Vol. 60).

99.      Unrelated parallel machine scheduling with setup times using simulated annealing / Kim D.W., Kim K.H., Jang W., Chen F.F. // Robotics and Computer-Integrated Manufacturing. – 2002. – Vol. 18. – P. 223-231.

101. Vaschuk F. Research of efficiency of algorithm machine scheduling of minimizing the total earliness and tardiness that depend on sequence /
Vaschuk F., Melnyk O. // Міжнародний науковий вісник Закарпатського державного університету. Наукові праці кафедри виробничої техніки та робототехніки Кошицького технічного університету / Ред. кол. Ф.Г. Ващук (голова), Вархола Міхал, Дубровка Мігаль, Луговий В.І. та ін. – Ужгород: ЗакДУ, 2012. –  С. 258 – 266.

102. Wagelmans A.P.M. Improved dynamic programs for some batching problems involving maximum lateness criterion / A.P.M Wagelmans, A.E Gerodimos // Operations Research Letters. – 2000. – Vol.27, № 3. – Р. 109-118.

Tabu search for single machine scheduling with distinct due windows and weighted earliness/tardiness penalties / Wan G., Yen B.P.-C. // European Journal of Operational Research. – 2002. – Vol.142, №2. – P. 271-281.

104.     Wang L. Hybrid algorithm for earliness-tardiness scheduling problem with sequence dependent setup time / Wang L., Wang M. // Proceedings of the IEEE Conference on Decision and Control (San Diego (USA), 10-12 December 1997) – 1997. – P. 1219-1222.

M. X. A Tabu Search Approach To Solve The Early/Tardy Scheduling Problem : Working Paper / Weng M. X., Sedani M. M. – Tampa, FL: University of South Florida, 2001. – 6 p.

106. Woeginger G.J. A polynomial-time approximation scheme for single-machine sequencing with delivery times and sequence-independent batch set-up times / Gerhard J. Woeginger // Journal of Scheduling. – 1998. – Vol.1, №2. − Р. 79-87.

107. Yang W.H. Batching and sequencing of jobs with order availability at a single facility / Yang W.H., Liao C.J. // International Journal of Systems Science. – 1998. – Vol. 29. – P. 13-20.

108. Yang W.H. Learning and forgetting effects on a group scheduling problem / Wen-Hua Yang, Suresh Chand // European Journal of Operational Research. – 2008. – Vol. 187, № 3. – P. 1033–1044.

109. Yang W.H. Optimal scheduling of two-component products on a single facility / Yang W.H. // International Journal of Systems Science. – 2004. – Vol. 35. –
P. 49-53.

110. Yang W.H. Survey of scheduling research involving setup times / Yang W.H., Liao C.J. // International Journal of Systems Science. –1999. – Vol. 30. –
P. 143-155.

Algorithms for a class of single-machine weighted tardiness and earliness problems / Yano C. A., Kim Y. D. // European Journal of Operational Research. – 1991. – Vol. 52, №2. – Р. 167-178.

112. Yi Y. Soft computing for scheduling with batch setup times and earliness-tardiness penalties on parallel machines / Yi Y., Wang D.W. // Journal of Intelligent Manufacturing. – 2003. – Vol. 14. – P. 311-322.

113. Автоматизированные системы управления гибкими технологиями / Скурихин В.И., Павлов А.А., Путилов Э.П., Гриша С.Н. – К.: Техніка, 1987. – 184 с.

114. Ващук Ф.Г. Алгебраический подход к описанию структуры сети программно-технических комплек