«Мінімізація сумарного зваженого моменту закінчення робіт» як перший рівень моделі дрібносерійного виробництва та способи її розв’язання

В статті розглянуто перший рівень багаторівневої моделі планування дрібносерійного виробництва в умовах ринку, математична модель якого задається важкорозв’язною задачею теорії розкладу «Мінімізація сумарного зваженого моменту закінчення робіт» (МЗМ). Наведено схему поліноміальної складової ПДС алго...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2002
Автори:	Павлов, О.А., Аксьонова, Л.О.
Формат:	Стаття
Мова:	Ukrainian
Опубліковано:	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України 2002
Назва видання:	Системні дослідження та інформаційні технології
Теми:	Автоматизовані системи управління
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/50216
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	«Мінімізація сумарного зваженого моменту закінчення робіт» як перший рівень моделі дрібносерійного виробництва та способи її розв’язання / О.А. Павлов, Л.О. Аксьонова // Систем. дослідж. та інформ. технології. — 2002. — № 1. — С. 119-130. — Бібліогр.: 6 назв. — укр.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-50216
record_format	dspace
spelling	irk-123456789-502162013-10-07T03:06:29Z «Мінімізація сумарного зваженого моменту закінчення робіт» як перший рівень моделі дрібносерійного виробництва та способи її розв’язання Павлов, О.А. Аксьонова, Л.О. Автоматизовані системи управління В статті розглянуто перший рівень багаторівневої моделі планування дрібносерійного виробництва в умовах ринку, математична модель якого задається важкорозв’язною задачею теорії розкладу «Мінімізація сумарного зваженого моменту закінчення робіт» (МЗМ). Наведено схему поліноміальної складової ПДС алгоритму заданої задачі та приклади поліноміальної розв’язності індивідуальних задач МЗМ, для яких даний алгоритм отримує оптимальний розклад. В статье рассмотрен первый уровень многоуровневой модели планирования мелкосерийного производства в условиях рынка, математическая модель которого задается труднорешаемой задачей теории расписания «Минимизация суммарного взвешенного момента окончания работ» (МВМ). Рассмотрена схема полиномиальной составляющей ПДС-алгоритма данной задачи и приведены примеры полиномиальной разрешимости индивидуальных задач МВМ, для которых данный алгоритм получает оптимальное расписание. In the given paper it was considered the first level of multilevel planning model of small-scale production at market conditions, mathematical model which was of assumed by intractable problem of schedule theory «Minimisation of total weighted completion time» (MTWCT). Here were also presented the scheme of polynomial component of PDC-algorithm for the given problem and the examples of polynomial solvability of instant MTWCT problems, for which the algorithm gets optimal schedule. 2002 Article «Мінімізація сумарного зваженого моменту закінчення робіт» як перший рівень моделі дрібносерійного виробництва та способи її розв’язання / О.А. Павлов, Л.О. Аксьонова // Систем. дослідж. та інформ. технології. — 2002. — № 1. — С. 119-130. — Бібліогр.: 6 назв. — укр. 1681–6048 http://dspace.nbuv.gov.ua/handle/123456789/50216 681:513 uk Системні дослідження та інформаційні технології Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
topic	Автоматизовані системи управління Автоматизовані системи управління
spellingShingle	Автоматизовані системи управління Автоматизовані системи управління Павлов, О.А. Аксьонова, Л.О. «Мінімізація сумарного зваженого моменту закінчення робіт» як перший рівень моделі дрібносерійного виробництва та способи її розв’язання Системні дослідження та інформаційні технології
description	В статті розглянуто перший рівень багаторівневої моделі планування дрібносерійного виробництва в умовах ринку, математична модель якого задається важкорозв’язною задачею теорії розкладу «Мінімізація сумарного зваженого моменту закінчення робіт» (МЗМ). Наведено схему поліноміальної складової ПДС алгоритму заданої задачі та приклади поліноміальної розв’язності індивідуальних задач МЗМ, для яких даний алгоритм отримує оптимальний розклад.
format	Article
author	Павлов, О.А. Аксьонова, Л.О.
author_facet	Павлов, О.А. Аксьонова, Л.О.
author_sort	Павлов, О.А.
title	«Мінімізація сумарного зваженого моменту закінчення робіт» як перший рівень моделі дрібносерійного виробництва та способи її розв’язання
title_short	«Мінімізація сумарного зваженого моменту закінчення робіт» як перший рівень моделі дрібносерійного виробництва та способи її розв’язання
title_full	«Мінімізація сумарного зваженого моменту закінчення робіт» як перший рівень моделі дрібносерійного виробництва та способи її розв’язання
title_fullStr	«Мінімізація сумарного зваженого моменту закінчення робіт» як перший рівень моделі дрібносерійного виробництва та способи її розв’язання
title_full_unstemmed	«Мінімізація сумарного зваженого моменту закінчення робіт» як перший рівень моделі дрібносерійного виробництва та способи її розв’язання
title_sort	«мінімізація сумарного зваженого моменту закінчення робіт» як перший рівень моделі дрібносерійного виробництва та способи її розв’язання
publisher	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
publishDate	2002
topic_facet	Автоматизовані системи управління
url	http://dspace.nbuv.gov.ua/handle/123456789/50216
citation_txt	«Мінімізація сумарного зваженого моменту закінчення робіт» як перший рівень моделі дрібносерійного виробництва та способи її розв’язання / О.А. Павлов, Л.О. Аксьонова // Систем. дослідж. та інформ. технології. — 2002. — № 1. — С. 119-130. — Бібліогр.: 6 назв. — укр.
series	Системні дослідження та інформаційні технології
work_keys_str_mv	AT pavlovoa mínímízacíâsumarnogozvaženogomomentuzakínčennârobítâkperšijrívenʹmodelídríbnoseríjnogovirobnictvatasposobiíírozvâzannâ AT aksʹonovalo mínímízacíâsumarnogozvaženogomomentuzakínčennârobítâkperšijrívenʹmodelídríbnoseríjnogovirobnictvatasposobiíírozvâzannâ
first_indexed	2025-07-04T11:47:13Z
last_indexed	2025-07-04T11:47:13Z
_version_	1836716798161977344
fulltext	© О.А. Павлов, Л.О. Аксенова Системні дослідження та інформаійні технології, 2002, 1 119 TIДC АВТОМАТИЗОВАНІ СИСТЕМИ УПРАВЛІННЯ УДК 681:513 «МІНІМІЗАЦІЯ СУМАРНОГО ЗВАЖЕНОГО МОМЕНТУ ЗАКІНЧЕННЯ РОБІТ» ЯК ПЕРШИЙ РІВЕНЬ МОДЕЛІ ДРІБНОСЕРІЙНОГО ВИРОБНИЦТВА ТА СПОСОБИ ЇЇ РОЗВ’ЯЗАННЯ О.А. ПАВЛОВ, Л.О. АКСЬОНОВА В статті розглянуто перший рівень багаторівневої моделі планування дрібносерійного виробництва в умовах ринку, математична модель якого задається важкорозв’язною задачею теорії розкладу «Мінімізація сумарного зваженого моменту закінчення робіт» (МЗМ). Наведено схему поліноміальної складової ПДС-алгоритму заданої задачі та приклади поліноміальної розв’язності індивідуальних задач МЗМ, для яких даний алгоритм отримує оптимальний розклад. ВСТУП Для сучасного економічного розвитку народного господарства характерна швидка зміна технологічних процесів, «зростання» кількості багатоно- менклатурних виробництв, для яких оптимальне планування та управління є запорукою нормального функціонування та виживання в умовах гострої конкурентної боротьби, ускладнення внутрішніх та зовнішніх зв’язків. Все це стимулює необхідність впровадження засобів автоматизації, обчислювальної техніки, економіко-математичних методів прийняття рішень і створює умови для розвитку нових концепцій виробництва (інтегрованих автоматизованих виробництв, гнучких виробничих систем), а також для автоматизації управління шляхом розробки та впровадження багаторівневих ієрархічних автоматизованих систем управління виробництвом. В умовах ринкової економіки конче потрібна принципово нова організація виробничих процесів. Це пов’язано із необхідністю миттєвої реакції виробництва на потреби ринку при одночасному зростанні асортименту продукції та зниженні трудових витрат. Отже, сучасне підприємство повинно бути адаптованим до умов випуску продукції невеликими партіями з частими змінами асортименту виробів (тобто до умов дрібносерійного та одиничного виробництв) відповідно до принципу «виробляти тільки те, що потрібно, тоді, коли потрібно і стільки, скільки потрібно». О.А. Павлов, Л.О. Аксьонова ISSN 1681–6048 System Research & Information Technologies, 2002, 1 120 Основа автоматизованих систем планування та управління дрібносерійним виробництвом — це реалізація моделей достатньо складної структури, що належать до класу важкорозв’язних, зокрема моделей оперативно-календарного планування і управління. Комп’ютеризоване виробництво, як якісно новий об’єкт управління, потребує вдосконалення систем оперативного планування і управління виробництвом, що, в свою чергу, неможливо без розробки алгоритмів планування і управління взаємодією елементів таких виробництв. Динамічність сучасних виробничих систем, концепція комп’ютеризованого виробництва як такого, що легко адаптується до зміни зовнішніх факторів, обумовлює створення гнучкої системи оперативного управління, здатної ефективно функціонувати та забезпечувати стійкість виробничого процесу за наявності різного роду зовнішніх та внутрішніх відхилень. Така система базується на комплексі економіко-математичних моделей та методів, що реалізують технологію застосування оптимальних планових рішень за рівнями системи. 1. БАГАТОРІВНЕВА МОДЕЛЬ ДРІБНОСЕРІЙНОГО ВИРОБНИЦТВА Автори досліджують дрібносерійне виробництво як об'єкт автоматизованого управління. На жаль існуючі методи планування не забезпечують ефективної діяльності підприємства у конкурентній ринковій боротьбі, і тому необхідні розробка та впровадження нової, науково обгрунтованої методології планування та управління сучасним виробництвом. Зазначимо, що задачі календарного планування у переважній більшості мають комбінаторний характер та відносяться до важкорозв'язних комбінаторних задач. Існуючі методи розв'язання таких задач не дозволяють отримувати не тільки оптимальні, але й ефективні наближені розв'язки, що зумовлює необхідність розробки нового підходу до розв'язання задач складання календарних планів з метою отримання розв'язків задач великої розмірності, які відповідатимуть вимогам сучасного виробництва. На кафедрі АСОІУ ФІОТ НТУУ «КПІ» створено багаторівневу модель планування дрібносерійного виробництва в умовах ринку, що покладена в основу розробленої системи планування та управління дрібносерійним виробництвом (СПУДВ). На першому рівні будується агрегована модель, в якій підприємство представлено у вигляді одного станка (приладу). В результаті роботи першого блоку задається послідовність виконання коміркокомплектів виробничої програми, що визначає пріоритети виконання коміркокомплектів, які використовуються алгоритмами другого рівня. Задача другого рівня полягає у побудові виробничої програми та ії розподілі за плановими періодами. Розглянемо загальну постановку першої задачі, що розв'язується в рамках моделі. Задано множину операцій { }nJJJJ ,...,, 21= по виготовленню n виробів (мається на увазі серія однотипних виробів), що розглядаються при формуванні портфеля замовлень. На кожній підмножині Jk задано частковий порядок орієнтованим ациклічним графом. Вершини графу відповідають операціям, зв'язки вказують на відношення передування, або входження. Відношення передування задається на основі «Мінімізація сумарного зваженого моменту закінчення робіт» як перший рівень… Системні дослідження та інформаційні технології, 2002, 1 121 конструкторсько-технологічної документації по виготовленню виробів, що входять до портфеля замовлень. Для кожної операції nkJj kl ,1, =∈ відома тривалість виконання ljl ; для кожної кінцевої операції nkJj kr ,1, =∈ (не є попередником інших) задано вагу rjω , що визначається як одиничний прибуток від реалізації. Кінцеві вершини відповідають готовим виробам. Для виконання операцій використовується система обслуговування у вигляді множини обмежених ресурсів. Сукупність виробничих засобів та станків поділено на окремі виробничі модулі (комірки), що є достатньо автономними. Виробництво характеризується різними технологічними циклами, широкими взаємозв'язками між підрозділами (комірками) для передачі виробленої продукції. Необхідно скласти номенклатурно-об'ємний план кожної структурної одиниці підприємства (комірки) з розподілом по планових періодах за наступними критеріями оптимальності та їхніми комбінаціями: а) максимізація прибутку; б) максимізація прибутку за наявності штрафів за порушення директивних строків; в) максимізація прибутку при виконанні замовлень «точно в строк» при наступних обмеженнях: • тривалість виготовлення кожного виробу визначається його критичним шляхом; • продуктивність у кожній групі технологічно взаємозамінюваного устаткування однакова. Такі задачі мають комбінаторно-оптимізаційний характер та відносяться до важкорозв'язних задач календарного планування. Класичні методи оптимізації та інші точні методи їх розв'язання неприйнятні з огляду на складну структуру та велику розмірність цих задач. Неефективними виявились також спроби застосування існуючих наближених методів, що скорочують перебір припустимих варіантів розв'язання. Суть нового підходу до розв'язання важкорозв'язних задач календарного планування, розробленого на кафедрі АСОІУ ФІОТ НТУУ «КПІ», полягає у розробці основних положень, правил, які відображають загальні властивості класів моделей, що розглядаються, та дозволяють організувати єдині принципи обчислень. Розглянемо розроблену схему розв'язання задач у системі СПУДВ. Граф G, побудований на критичних шляхах виробів на основі агрегованої інформації, складається з n кінцевих вершин, що відповідають n виробам. Під вершинами розуміємо коміркокомплекти (сукупність операцій, що виконуються в одній комірці в межах одного заходу по одному виробу), дуги інтерпретуються як зв'язки між комірками, що регламентують технологію виготовлення виробів. Якщо для деяких груп коміркокомплектів потрібно багато часу на настроювання приладів, то формується один спільний коміркокомплект, що на графі зв'язності відображено спільними вершинами. Для кожної вершини i відома тривалість il , для кожного виробу (кінцевої вершини) i задано вагу iw , що визначається як одиничний О.А. Павлов, Л.О. Аксьонова ISSN 1681–6048 System Research & Information Technologies, 2002, 1 122 прибуток від реалізації виробу. Загальний прибуток від реалізації виробу є функцією часу: )()( iii CTwtw −= , де T — період, необхідний для виконання усіх виробів; iC — момент закінчення виготовлення виробу i. Потрібно виготовити N виробів, максимізуючи сумарний прибуток підприємства ( ) = →∑ i ii C-TwF max при наступних обмеженнях: • тривалість виготовлення кожного виробу (а також коміркокомп- лекту) визначається його критичним шляхом; • коміркокомплект не передається в інші комірки до його повного завершення; • продуктивність у кожній групі технологічно взаємно замінюваного устаткування однакова. Критерій F є еквівалентним критерію важкорозв’язних задач теорії розкладу «Мінімізація сумарного зваженого моменту закінчення виготовлення виробів при заданому відношенні порядку» на множині операцій кожного виробу. Ми розглянемо важкорозв’язну задачу теорії розкладу МЗМ і наведемо умови, коли індивідуальні задачі МЗМ, постановка якої розглядається як перший рівень багаторівневої ієрархічної моделі СПУДВ, можуть бути розв’язані за поліноміальний час. Як раніше було визначено, належність задач до класу важкорозв’язних створює суттєві проблеми при отриманні їх точного розв’язку для задач достатньо великого розміру, бо за умови P ≠ NP для задач даного класу не можна побудувати поліноміальний алгоритм. Для подолання цих труднощів авторами раніше було запропоновано методологію по створенню ПДС- алгоритмів, тобто створення точних алгоритмів, які визначають належність індивідуальної задачі, що розглядається, до класу задач, які поліноміально розв’язуються в процесі розв’язку. У статті ми розглянемо ПДС-алгоритм задачі МЗМ першого типу з адитивною структурою. Тобто це ПДС- алгоритм, що є статистично ефективним для індивідуальних задач МЗМ, параметри яких моделюються випадково. Структура поданого алгоритму складається з двох незалежних алгоритмів — поліноміального та експоненційного. Розв’язок початкової індивідуальної задачі починається з застосування поліноміального алгоритму, на кожному кроці його застосування перевіряються умови можливості його використання. У випадку їх порушення розв’язок продовжується експоненційним алгоритмом. «Мінімізація сумарного зваженого моменту закінчення робіт» як перший рівень… Системні дослідження та інформаційні технології, 2002, 1 123 2. МАТЕМАТИЧНА МОДЕЛЬ ТА ВЛАСТИВОСТІ ЗАДАЧІ «МІНІМІЗАЦІЯ СУМАРНОГО ЗВАЖЕНОГО МОМЕНТУ ЗАКІНЧЕННЯ РОБІТ» Постановка та властивості задачі. Задано частково впорядковану множину робіт { }nJJJJ ,...,, 21= , які починаючи з нульового моменту обслуговуються одним приладом, без перерв, не більше ніж одна в одиницю часу. Для кожного завдання j поставлена у відповідь його тривалість lj >0 та вага ωj (довільне дійсне число, в додатку > 0). Орграф часткового впорядкування має ациклічну структуру. Необхідно знайти таку послідовність обслуговування завдань, сумарний зважений момент закінчення виконання робіт в котрій є мінімальним: [ ] [ ] →=∑ = n k jj kk cF 1 ω min, (1) де cj ][k — момент закінчення виконання завдання, що стоїть у припустимому розкладі на k-й позиції, [ ] [ ]∑ = = k s jj sk lc 1 . На множині завдань орієнтованим ациклічним графом задане відношення часткового порядку, тобто якщо lk jj ≺ , то обслуговування завдання kj в будь-якій припустимій послідовності повинне завершитися раніше ніж обслуговування завдання lj . Запис [ ]( )ks gg αβ ≺≺)( ][ означає попередження останньої роботи підпослідовності )( ][sgβ першій роботі підпослідовності )( ][kgα . Ця задача може бути розв’язана за поліноміальний час, якщо порядок задано, наприклад, лісом чи послідовно-паралельним графом [1]. Теорема 1 [2]. Нехай на множині всіх припустимих розкладів P задана функція ][][ 1 )( kk j n k j cwF ∑ = =Π . Тоді для двох довільних перестановок ),,,,("),,,,(' )2()()()1()2()()()1( ΠΠΠΠ=ΠΠΠΠΠ=Π abba що належать до P, існує функція )(Πf , що задовольняє наступному: з вимоги )()( )()( ba ff Π>Π випливає нерівність )''()'( Π<Π FF і з вимоги )()( )()( ba ff Π=Π — рівність )"()'( Π=Π FF . Ця функція має назву пріоритет перестановки і позначається ∑ ∑ Π∈ Π∈=Π }{ }{)( j j j j l w P . (2) О.А. Павлов, Л.О. Аксьонова ISSN 1681–6048 System Research & Information Technologies, 2002, 1 124 Визначення 1 [2]. P-впорядкованим розкладом є припустима послідов- ність робіт, що задовольняє наступним умовам: 1) множина S1 ⊂ J (J ⎯ множина всіх робіт), що має максимальний можливий пріоритет, тобто P(S1) > P(U), ∀ U ⊂ J, повинна бути оброблена першою; 2) множина S2, що задовольняє умові 1 на множині J \ S1, повинна бути оброблена другою і т.д. У P-впорядкованому розкладі початкова множина робіт розбивається на підмножини максимальних пріоритетів (ММП). Теорема 2. Оптимальний розклад є P-впорядкованим [3]. Примітка. ММП iS повинна містити мінімально можливу кількість робіт, тому що розбиття вихідної множини робіт на ММП є декомпозицією вихідної задачі на підзадачі меншої розмірності. Множини робіт, що мають однакові значення пріоритетів, розглядаються як різні ММП. 3. СТРУКТУРА ПДС-АЛГОРИТМУ ЗАДАЧІ «МІНІМІЗАЦІЯ СУМАРНОГО ЗВАЖЕНОГО МОМЕНТУ ЗАКІНЧЕННЯ РОБІТ» Розглянемо поліноміальну частину ПДС-алгоритму задачі МЗМ. Алгоритм складається з двох частин [4]: 1) отримання наближеного алгоритму; 2) ітераційна процедура отримання оптимального розкладу на початковій множині завдань наближеного розкладу. Алгоритм, починаючи з першої роботи, розглядає на кожній k -й ітерації перші k завдань наближеного розкладу. Важливим є те, що на попередній ( k –1)-й ітерації ми отримали р-впорядковане або оптимальне рішення для перших ( k –1)-х завдань наближеного розкладу. Розглянемо умови, задовільнення яким на кожній ітерації множиною завдань початкової індивідуальної задачі, приводить до її розв’язку за поліно- міальний час. За властивостями задачі МЗМ початкова множина завдань в оптимальному рішенні декомпозується на ММП [3]. В [4] були введені поняття ланцюга та конструкції. Визначення 2. Ланцюгом ми називаємо послідовність завдань ][][ ,..., fl jj таких, що [ ] [ ] [ ] [ ]( ) [ ] [ ]( )fiilii jjpjjpfiljj ,...,,...,;, 11 +− <≤<≺≺ . Визначення 3. Простою конструкцією називається послідовність завдань pi ααββ ,...,,,..., 11 , що задовольняє умовам: ( ) ( )ip ppppp ββααα ≥≥≥≥≥ ...),(...)()( 121 , (3) де iββ ,...,1 та pαα ,...,1 — несуміжні та пріоритетно-впорядковані поміж собою ланцюги або завдання; та має наступну структуру: «Мінімізація сумарного зваженого моменту закінчення робіт» як перший рівень… Системні дослідження та інформаційні технології, 2002, 1 125 Складною конструкцією першого рівня є конструкція аналогічна за структурою простій, у якій замість довільного ланцюга iα може стояти проста конструкція K (рис. 2). Аналогічним чиною визначається складна конструкція довільного рівня вкладеності. Визначення 4. Підпослідовності iββ ,...,1 , що задовольняють умовам ijsiKij ,1,,1, ==≺≺β на множині { si KK ,...,,,..., 11 ββ }, ми будемо називати замикаючими підмножинами, а підпослідовності sKK ,...,1 ⎯ приймачами першого рівня. Так, наприклад, на рис. 2 підпослідовності iββ ,...,1 є замикаючими, а підпослідовності pKKK ,...,,, 121 α — приймачі першого рівня. Рис. 1 α2 αp α1 • • • β i β1 • • • K1 K2 Kp α1 β1 βi • • • Рис. 2 О.А. Павлов, Л.О. Аксьонова ISSN 1681–6048 System Research & Information Technologies, 2002, 1 126 4. УМОВИ ПОЛІНОМІАЛЬНОЇ РОЗВ’ЯЗНОСТІ ІНДИВІДУАЛЬНИХ ЗАДАЧ МЗМ В [5] було показано наступне: 1) якщо ММП початкової індивідуальної задачі є завдання, ланцюги або конструкції довільного рівня вкладеності, то ПДС-алгоритм задачі МЗМ, запропонований у [4], знаходить оптимальний розклад за поліноміальний час; 2) відношення попередження від максимальної множини з більшим значенням пріоритету до максимальної множини з меншим може бути довільним. Наступний ряд умов поліноміальної розв’язності було визначено для підмножини робіт ММП. Нехай останні роботи ланцюгів iββ ,...,1 зв’язані повним підграфом з першими роботами ланцюгів pαα ,...,1 або конструкцій pKK ,...,1 . Примітка. Якщо конструкція jK має структуру jK = ( j p jj i j KK ,...,,,..., 11 ββ ), то останні роботи ланцюгів iββ ,...,1 зв’язані повним підграфом також з першими роботами ланцюгів j i j ββ ,...,1 . Умова 1. Тоді довільна робота ланцюга jβ , ij ,1= може бути довільним чином зв’язана з довільними роботами ланцюгів pαα ,...,1 або конструкцій pKK ,...,1 , тобто psqqgg sj ,1,,: =∈∈∀ αβ ≺≺ , psKqqgg sj ,1,,: =∈∈∀ ≺≺β . Примітка. Вищеподана умова виконується для конструкції jK довільного рівня вкладеності. Умова 2. Якщо справедливі умови )(...)()( 21 ippp βββ ≥≥≥ , то відношення попередження від довільної роботи ланцюга jβ до робіт ланцюга jss >,β (тобто )()( sj pp ββ > ) може бути довільним. Умова 3. При виконанні умов )(...)()( 21 pppp ααα ≥≥≥ або )(...)()( 21 pKpKpKp ≥≥≥ відношення попередження від робіт iα до робіт ланцюга jij <,α (тобто )()( ji pp αα ≥ ) може бути довільним. Аналогічним чином визначаються умови відношення попередження і для конструкцій. Умова 4. Подані вище мови справедливі для конструкцій довільного рівня вкладеності. На рис. 3 наведено приклади додаткових відношень попередження, що були запропоновані в умовах 1–4. «Мінімізація сумарного зваженого моменту закінчення робіт» як перший рівень… Системні дослідження та інформаційні технології, 2002, 1 127 В обмеженнях умов 1–4 суттєвою є вимога безпосереднього попередження останніх робіт ланцюгів iββ ,...,1 (замикаючих підмножин) першим роботам ланцюгів pαα ,...,1 або конструкцій pKK ,...,1 (приймачів першого рівня). Далі розглянемо умови, в яких знімається вимога безпосереднього попередження останніх робіт ланцюгів iββ ,...,1 усім першим роботам конструкцій і ланцюгів, що є приймачами першого рівня. Для наступного ряду вимог суттєвою залишається вимога попередження першим роботам приймачів першого рівня [6]. Нехай для ланцюгів jβ та iα таких, що ij αβ ≺ і jβ = i кін ji поч j кін j поч j αβαβββ −= ≺≺≺ ;),,( , виконується нерівність ( ) ( )i кін j pp αβ ≥ . (4) Умова 5. Якщо для довільного приймача першого рівня jK такого, що для нього існують замикаючі підмножини ( ) i поч si поч s кін s поч ss αβαββββ ≺≺≺ ;,,= , виконується формула (4), тобто ( ) ( )j кін s Kpp ≥β , і наведена умова справедлива для кожного j поч jj βββ ⊂: (тобто порушується умова попередження останньої роботи (рис.4)), то оптимальне рішення для означеної вище множини робіт збігається з оптимальним розкладом на ММП, що задовольняє вимогам конструкції і має вигляд iββ ,...,1 , pKK ,...,1 . Примітка. В обмеженнях умови 5 можливі додаткові відношення попередження, аналогічні тим, що були введені в умовах 1–4. K1 K2 Kp β1 βi • • • α1 Рис. 3 О.А. Павлов, Л.О. Аксьонова ISSN 1681–6048 System Research & Information Technologies, 2002, 1 128 Далі розглянемо обмеження на відношення попередження, при яких вилучається вимога безпосереднього попередження замикаючих ланцюгів першим роботам приймачів першого рівня. Суттєвою залишається вимога безпосереднього попередження останньої роботи замикаючих ланцюгів. Введемо наступні позначення: iji KK ≺β:∀ ; поч iK — початкова послідовність iK така, що ),(,, кінпоч i кін j поч j iiii KKKKK =≺≺≺ ββ . Нехай ММПМ має наступний вигляд: ,...,,,...,,,,...,,,..., 1111 222111 ++ i кін i поч ii кін i поч ii KKKKKKKββ pi кін i поч i KKKK jjj ,...,,,..., 1+ . (5) K поч i1 K кін ji K поч ji K 2i β1 βsi • • • K кін i1 Рис. 5 β1 βs • • • α1 α2 • • • кін sβпоч sβ Рис. 4 «Мінімізація сумарного зваженого моменту закінчення робіт» як перший рівень… Системні дослідження та інформаційні технології, 2002, 1 129 Примітка. Розклад (5) є оптимальним для множини робіт, що задовольняє вимогам конструкції, де iββ ,...,1 — замикаючі ланцюги, а pKK ,...,1 — приймачі першого рівня. Справедливе наступне твердження. Твердження. Нехай справедливі умови ( ) ( ) ( ) ( ) ( )кін ii поч i поч i поч i KpKpKpKpKp j 1121 1; ≥≥≥≥ −… ; ( ) ( ) ( ) ( )кін ii кін ii jj KpKpKpKp ≥≥ −− 11 ;; 22 … . Тоді якщо ( ) ( )поч iiif KpKKp 11 11 ,,,,, ≥−…… ββ , де ( ) ( )поч if Kpp 11 ≥−β та ( ) ( )поч if Kpp 1 <β , то розклад (5) є оптимальним для множини робіт М. В умовах розглянутого твердження розклад (5) залишається оптимальним і для наступних додаткових відношень попередження: 1) при довільному попередженні робіт ланцюгів { }iff ,1, =β роботам початкової частини конструкції pjK поч i j ,1, = ; 2) при довільному попередженні робіт початкової частини конструкції поч i j K роботам початкової частини конструкції поч il K , jl > ; 3) при довільному попередженні робіт конструкцій jK роботам ланцюжків початкової частини конструкції jiK l поч il >, . Примітка. Доведення всіх розглянутих нами умов та тверджень базується на тому факті, що ММП підграфа вихідної множини робіт, у якому були вилучені розглянуті вище додаткові обмеження, задовольняють вимогам ланцюгів або конструкцій довільного рівня вкладеності. ВИСНОВОК Системи планування й оперативного керування виробництвом повинні забезпечити високий рівень узгодженості різних виробничих підрозділів у просторі і часі. Виготовлення і постачання кожної складової одиниці повинні здійснюватися в строго встановлений час, обумовлений термінами випуску виробу в цілому. При цьому необхідно забезпечити найбільш повне завантаження обладнання, максимальне скорочення тривалості виробничого циклу з урахуванням технологічної гнучкості. Більш високі вимоги висуваються до узгодження календарних розкладів. Усе це реально виконується за наявності науково обґрунтованих методологій планування і керування виробництвом у нових умовах і математичному апараті, що дозволяє одержувати ефективні розв’язки важкорозв’язних задач календарного планування. Запропонована модель дрібносерійного виробництва спирається на ряд важкорозв’язних задач теорії розкладу, на прикладі яких автори успішно застосували методологію проектування нового класу точних алгоритмів О.А. Павлов, Л.О. Аксьонова ISSN 1681–6048 System Research & Information Technologies, 2002, 1 130 (ПДС-алгоритмів ), що мають значні переваги з теоретичної та практичної точки зору. В статті наведено нові умови поліноміальної розв’язності важкорозв’язної задачі «Мінімізація сумарного зваженого моменту закінчення робіт», що аналізуються в процесі розв’язання індивідуальних задач МЗМ і на відміну від початкового аналізу параметрів задачі мають значну практичну ефективність. Це дає можливість статистично значимо отримувати точний розв’язок задач за поліноміальний від їх розміру час. ЛІТЕРАТУРА 1. Lawler E.L. Sequencing jobs to minimize total weighted completion time subject to precedence constraints // Ann. Discrete Math. — 1978. — № 2. — Р.75–90. 2. Павлов А.А. Конструктивные полиномиальные алгоритмы решения индиви- дуальных задач из класса NP. — Киев: Техника, 1993.— 128 с. 3. Sidney J.B. Decomposition algorithm for Single-Machine Sequencing with Precedence Relations and Deferral Costs. Operation Res. — 1975. — № 23. –– Р.283–298. 4. Pavlov A., Pavlova L.. PDC-algorithms for intractable combinatorial problems. Theory and methodology of design. –– Uzhhorod: «Karpatskij region» shelf, 1997. — 320 р. 5. Pavlov A.A., Pavlova L.A.. About one subclass of polynomially solvable problems from class «Sequencing jobs to minimize total weighted completion time subject to precedence constraints». Киев, Весті междунар. Соломонов. ун-т. — 1999. — № 1. –– C. 109–116. 6. Павлов А.А., Аксенова Л.А. Новые условия полиномиальной составляющей ПДС-алгоритма задачи «Минимизация суммарного взвешенного момента» // Проблемы программирования. –– 2001. –– № 1. –– C. 69–75. Надійшла 6.11.2001

«Мінімізація сумарного зваженого моменту закінчення робіт» як перший рівень моделі дрібносерійного виробництва та способи її розв’язання

Репозитарії

Схожі ресурси