Новини освіти і науки:

G+

Тлумачний словник
Авто
Автоматизація
Архітектура
Астрономія
Аудит
Біологія
Будівництво
Бухгалтерія
Винахідництво
Виробництво
Військова справа
Генетика
Географія
Геологія
Господарство
Держава
Дім
Екологія
Економетрика
Економіка
Електроніка
Журналістика та ЗМІ
Зв'язок
Іноземні мови
Інформатика
Історія
Комп'ютери
Креслення
Кулінарія
Культура
Лексикологія
Література
Логіка
Маркетинг
Математика
Машинобудування
Медицина
Менеджмент
Метали і Зварювання
Механіка
Мистецтво
Музика
Населення
Освіта
Охорона безпеки життя
Охорона Праці
Педагогіка
Політика
Право
Програмування
Промисловість
Психологія
Радіо
Регилия
Соціологія
Спорт
Стандартизація
Технології
Торгівля
Туризм
Фізика
Фізіологія
Філософія
Фінанси
Хімія
Юриспунденкция

Методи пошуку розв’язання на прикладах задач планування

Пошук у просторі станів.Розглянемо можливе подання задачі стосовно формування плану-графіка завантаження устаткування. Початковий його стан характеризується множиною завдань, які складаються з частково впорядкованих наборів операцій (рис. 9.10). Дія кожного оператора полягає в перенесенні найближчої операції одного з наборів у чергу до одного з відповідних верстатів. У кінцевому стані устаткування всі операції переміщуються в черзі. Процесу розв’язання такої задачі відповідає граф послідовності подій (рис. 9.11).

Якщо мета полягає лише у виконанні операцій, а часові критерії відсутні (це, мабуть, нереально для практики), то кожна термінальна вершина графа служить розв’язком. При накладенні обмежень типу директивних строків без використання будь-якої цільової функції розв’язання досягається «пошуком у глибину» або «пошуком у ширину» з перевіркою виконання обмежень у кожній новій вершині та із завершенням пошуку в першій термінальній вершині, що задовольняє обмеження.

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

Рис. 9.10. Частково впорядковані набори операцій

Скорочення кількості варіантів оптимальних (або раціональних) розв’язків досягається використанням спеціальних оцінних функцій, евристичних правил, додаткових обмежуючих узгоджень. Так, в основі багатьох практичних методів лежить схема, що імітує послідовність подій у реальній системі (див. рис. 9.11). Ця схема реалізовує односпрямований рух уздовж тільки одного з шляхів графа G, які об’єднують початкову та термінальну вершини.

Рис. 9.11. Послідовність подій у реальній системі

Справді, в цьому разі хоча й існують альтернативні варіанти в кожній з вершин, однак після прийняття рішення (вибору партії серед претендентів) повернення не здійснюються, а всі потенційно можливі наступні стани подій локалізуються розташованим нижче підграфом. При цьому оптимальний розв’язок не гарантується, оскільки він може розміщуватися поза цим підграфом. Як компенсація цього недоліку — простота реалізації, скорочення простору пошуку при прийнятних показниках одержуваного субоптимального розв’язку.

Практично описана схема розв’язання наведеної задачі доцільна в алгоритмічному вигляді, а не засобами EC, хоча в спрощеному вигляді вона може моделюватися набором таких правил:

(9.1)

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

Тоді за наявності тільки вимоги виконання завдання (без критерію оптимальності) можливі правила матимуть вигляд:

ЯКЩО здійснюється вибір кращого претендента І використовуються обмеження за …, І …, ТО вибрати партію з …,

а за наявності критерію оптимальності — вигляд:

ЯКЩО здійснюється вибір кращого претендента І використовуються обмеження за …, І критерій оптимальності …, І …, ТО вибрати партію з ….

У подальшому для зручності опису наведених нижче прикладів загальні елементи в лівій частині правил (тобто умови «вибір кращого претендента» та «використовуються обмеження за...») упускатимемо. Спочатку розглянемо випадок наявності тільки вимоги виконання завдань. Як правило, в цьому разі фігурують директивні строки їх завершення і можуть використовуватися, наприклад, такі евристичні правила для визначення напрямку перебирання кращого претендента:

ЯКЩО значення директивних строків наближаються, ТО вибрати завдання з мінімальною тривалістю операцій, що залишилися;
ЯКЩО директивні строки відрізняються, ТО вибрати завдання з мінімальною різницею

де тривалість обслуговування партії деталей i на j^*-й операції її технологічного маршруту (ТМ); номери решти операцій; директивний строк обслуговування партії деталей і.

Як оцінна може бути вибрана або функція де а момент завершення останньої виконаної (на поточний момент) операції над і-ю партією деталей, причому

або функція

де вагові коефіцієнти,

або функція

і т. д. (припускається, що для кожної з цих функцій ).

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

ЯКЩО критерієм оптимальності є мінімум тривалості циклу, ТО вибрати претендента з мінімальною тривалістю на цьому кроці вибору поточної операції;
ЯКЩО критерієм оптимальності є мінімум тривалості циклу, ТО вибрати претендента з мінімальною кількістю операцій, що залишилися;
ЯКЩО критерієм оптимальності є мінімум тривалості циклу, ТО вибрати претендента з мінімальною різницею
ЯКЩО критерієм оптимальності є мінімум тривалості простоїв устаткування, ТО вибрати претендента, для якого наступна операція виконується на верстаті, що простоює.

У наведених прикладах з критерієм оптимальності як оцінні можна вводити, наприклад, такі функції:

Пошук в ієрархії просторів. В основі цього підходу лежить ієрархічне подання компонентів проблемної галузі, наприклад, планування. Ієрархія може утворюватись у межах: власне простору станів (планів); множини цілей; множини операторів і стратегій щодо формування плану. Це досягається як виділенням безпосередніх складових планування, так і формуванням рівнів абстракції, коли підпростір верхнього рівня є узагальненим, абстрагованим від деяких елементів подання підпростору нижнього рівня (рис. 9.12).

Рис. 9.12. Приклад низхідного уточнення виробничого плану

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

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

· непряме подання фрагмента (наприклад, транспортні операції та їх виконавці в плані не зазначаються, але тривалості виконання операцій враховуються в тривалостях обробки відповідних партій деталей);

· ігнорування фрагмента (наприклад, коли посилання на пересування вантажів відсутні, а тривалості їх виконання не враховано).

До основних фрагментів планування, що впливають на виділення рівнів, належать: переналагодження устаткування (його наявність, тривалості використання тощо); структури завдань (партія — набір носіїв — сукупність деталей тощо); транспортні операції (розглядались вище); склад ресурсів (однотипні групи устаткування із сумарною продуктивністю, окремі одиниці устаткування тощо).

Схема розв’язання задачі будується на принципі низхідного уточнення (top-down refinement): план, одержуваний на більш високому рівні, послідовно деталізується на більш низьких рівнях.

У загальному випадку прийняття рішень на різних рівнях планування може бути рознесено в часі. До того ж, окремі рівні можуть виконуватися на різних стадіях виробничого процесу. Так, формування плану в межах етапів 1-3 (див. рис. 9.12) здійснюється до запуску партій деталей на обробку, проте рішення, що деталізують план до рівня руху носіїв (етап 4 на рис. 9.12), приймаються в процесі диспетчеризування при виконанні завдання (тобто в режимі реального часу).

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

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

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

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

Приклад 9.4.Для ілюстрації принципу найменших завершень розглянемо такий спрощений приклад. Припустимо, що при виборі конкуруючих претендентів на обслуговування (партії деталей 1 і 2 на рис. 9.13, а) ресурсом А враховується, зокрема, як скоро до нього надійдуть наступні претенденти. Проте потенціальні претенденти (партії деталей 3 і 4) на момент прийняття рішення можуть бути ще не закріпленими за тими ресурсами, які відповідають першочерговим етапам їх ТМ, тобто за верстатом 8. До того ж, вони можуть конкурувати як між собою, так і з іншими партіями деталей.

Рис. 9.13. Урахування потенційних претендентів (розв’язання конфліктів при їх виборі):

а— рівні обліку;б— тупикова ситуація

У цьому разі призначення ресурсу (верстата) А може бути відкладене, а здійснюватиметься закріплення відповідних партій деталей за ресурсом (верстатом) В з подальшим поверненням до уточнення їх закріплення за ресурсом А. Проте оскільки вибір серед партій деталей 3 і 4 здійснюється за тим самим принципом, це може призвести до досить довгих ланцюжків очікування залежних підзадач, а в гіршому разі — до появи тупикових ситуацій (рис. 9.13, б). Тут вибір серед партій деталей 1 і 2 відкладено до закріплення партії деталей 3 або 4 за ресурсом В, що, у свою чергу, залежить від вибору партій деталей, що закріплюються за ресурсом А. Практично можуть виникати довші та складніші цикли залежності.

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

Приклад 9.5.Використання принципу найменших завершень у разі ієрархічного пошуку розглянемо на такому прикладі. Нехай верхній рівень (рис. 9.14) складання плану полягає у формуванні груп різних претендентів, які закріплюються за різними (чи різнотиповими) наборами ресурсів на певному часовому інтервалі, а на нижньому рівні розв’язуються конфлікти між конкуруючими претендентами (якщо такі залишаються після вибору на верхньому рівні з урахуванням конкретних значень часу), тобто власне формування розкладу запусків партій деталей.

Рис. 9.14. Урахування потенціальної конкуренції претендентів

При цьому в процесі формування груп партій деталей (верхній рівень) критерієм є зменшення їх конкуренції на подальших етапах обробки (тобто стратегія тут випливає з евристичного припущення про бажаність запуску в одночасну обробку тих партій деталей, які не створюють потенційних перешкод одна одній у подальшому). Так, згідно з рис. 9.14, на ресурси (верстати) А та В надходитимуть відповідно партії деталей 2, 3.

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

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

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

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

Приклад 9.6.Розглянемо такий спрощений приклад. Маємо один верстат і кілька деталей-претендентів на їх обробку. Вибраним критерієм оптимальності є мінімум сумарного часу очікування. Використовуємо правило, яке називається SPT-впорядкуванням (Shortest Processing Time Sequencing):

ЯКЩО критерієм є мінімум часу очікування, ТО впорядкувати заявки за низхідною тривалістю виконання операцій.

Якщо ж деякі деталі потребують обов’язкового переналагодження устаткування, то це правило набуває вигляду:

ЯКЩО критерієм є мінімум часу очікування, ТО впорядкувати заявки за низхідною сумою тривалостей переналагодження устаткування й обробки деталей.

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

ЯКЩО критерієм є … І переналагодження устаткування не потрібне, І час транспортування деталей несуттєвий, ТО впорядкувати заявки за низхідною тривалістю виконання операцій.
ЯКЩО критерієм є … І переналагодження устаткування потрібне, І …, ТО впорядкувати заявки за низхідною сумою …

і т. д.

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

Стосовно ситуації планування можна записати таке правило:

(9.2)

Очевидно також, що в БЗ будуть необхідними такі твердження (факти):

(9.3)

Тоді правило надання переваги щодо впорядкування заявок матиме вигляд:

(9.4)

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

(9.5)

Як бачимо, правила (9.2) і (9.3) не пов’язані безпосередньо з будь-яким критерієм або видом упорядкування, а виражають більш загальні закономірності і відношення, які ґрунтуються на уявленні про тривалість, причинно-наслідкові зв’язки, особливості організації виробничого процесу тощо. Водночас, саме використання цих правил дає змогу підвищити ступінь «універсальності» рішень стосовно окремих критеріїв і, що суттєво, підготувати деякий базис для можливих майбутніх рішень, у тому числі й за іншими критеріями.

Знання, що розглядаються як глибинні при розв’язанні задач планування, містять:

знання, інваріантні щодо конкретного методу формування плану;
знання, пов’язані з конкретною стратегією.

У свою чергу, перша групазнань складається:

а) із знань про загальні взаємозв’язки сутностей, що враховуються при формуванні плану. Прикладами таких знань є правило (9.2), а також правило:

ЯКЩО заявки впорядковано, ТО сумарний час очікування дорівнює сумі добутків трудомісткостей заявок на кількість подальших заявок;

б) із знань, які виражають деякі закономірності загальноматематичного характеру. Наприклад:

ЯКЩО мінімуму сумарної величини досягнуто, ТО досягнутим є й мінімум її середнього значення,

з чого випливають відповідні твердження щодо загальних і середніх простоїв, очікувань тощо. Ще один приклад таких знань: мінімум суми попарних добутків елементів двох послідовностей досягається при їх протилежному впорядкуванні, звідки з урахуванням правила (9.4) за змістом випливає правило (9.5);

в) із знань, що виражають загальні закономірності та сутності виробничого процесу. Прикладом цих знань є правило (9.5).

Друга група знань складається зі знань, які мають вузькоспеціалізований характер і пов’язані з принципами, що лежать в основі конкретних методів розв’язань.

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

Водночас використання глибинних знань є зайвим в умовах порівняно стабільного та передбачуваного потоку заявок або в умовах диспетчеризування з прийняттям рішень у реальному масштабі часу (див. розд. 10).

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Штучний інтелект у системах проектування та планування	\|	Інтелектуалізоване дискретно-подійне моделювання гнучких виробничих систем

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.009 сек.