Warning: session_start() [function.session-start]: Cannot send session cookie - headers already sent by (output started at /var/www/nelvin/data/www/ebooktime.net/index.php:6) in /var/www/nelvin/data/www/ebooktime.net/index.php on line 7

Warning: session_start() [function.session-start]: Cannot send session cache limiter - headers already sent (output started at /var/www/nelvin/data/www/ebooktime.net/index.php:6) in /var/www/nelvin/data/www/ebooktime.net/index.php on line 7

Warning: file_get_contents(files/survey) [function.file-get-contents]: failed to open stream: No such file or directory in /var/www/nelvin/data/www/ebooktime.net/index.php on line 82
6.2. Постановка задач оптимізації : Дослідження операцій : Бібліотека для студентів

6.2. Постановка задач оптимізації


Повернутися на початок книги
1 2 3 4 5 6 7 8 9 10 11 12 13 14 
15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 
30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 
45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 
60 61 62 63 64 65 66 67 

Загрузка...

послідовності виконання робіт

та аналіз методівїх розв'язування

Основна відмінність між детермінованими і стохастичними задачами календарного планування заключається в тому, що в першому випадку параметри вважаються відомими, в другому — змінюються випадково.

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

Задача календарного планування для одного верстата має без-сумнівний інтерес з двох причин:

1)         вона має місце на практиці, коли необхідно розробити роз-пис виконання робіт для унікальних верстатів (особливо верста-тів з програмним управлінням);

2)         вона становить інтерес з точки зору методу знаходження оптимальної послідовності виконання робіт.

Припустимо, що на агрегаті необхідно обробити п деталей,

знаючи, що час виконання дій по обробці і-ої деталі (і = 1, п) ві-домий і дорівнює ti, час підготовки агрегату до обробки і-ої де-талі   після   завершення   обробки    j -ої   деталі   дорівнює    т!у,

і, j = 1, п, і Ф j.

Потрібно знайти таку послідовність, при якій мінімізується час проходження всіх деталей:

t    \    п

R{t,T) = ^tj +   J]  x;y->min.    (6-1)

7=1      (і,у)ЕІ1

Послідовність, при якій R(t,i)  досягає мінімальної довжини (тривалості), називається П — послідовністю і позначається П*. Очевидно, що оптимальна довжина R(t,x) залежить від друго-

п

го доданку в (6.1) і коригується на незмінну величину ^tt.

і=\

Оскільки х4. для всіх і = \,п відсутнє, позначимо діагональні

елементи матриці М тривалостей переналадок да, тоді приходимо до задачі, яка має назву «задача комівояжера», для знаходження оптимального розв'язку якої використовується метод гілок та меж [19], [25].

Вперше метод гілок та меж був запропонований у 1960 р. в роботі Ленд і Дойг для розв'язування цілочисельних лінійних за-дач. Розглянемо ідею методу на прикладі загальної задачі дис-кретного програмування:

f\x) -> min,       (6-2)

x&D,   (6-3)

де D — скінчена множина.

3 метою зменшення числа переборів допустимих планів задачі множина D розбивається на підмножини (гілки)

Dt, і = \,к\ [jDi = D,Dsf]D   = О, s Ф р, р = \,к

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

Оцінкою множин D називається таке число а(р), що для всіх ієД   f(x) > а(р).

Якщо Д є підмножиною D , тоді очевидно

 

mm

XE-D

 

f(x)>mmf{x),

 

тому сс(Д.) > а[рр J.

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

Критерій оптимальності.  Нехай   D = (jDt   і в результаті

і=\

розв'язування задачі:

fix) —» min,

хє D,

знайдено  розв'язок   х',  який  задовольняє умову  (6.3).  Якщо a\Ds) = f\xs) не більше оцінок ще не розгалужених підмножин

D , то х  = х .

Важливою реалізацією методу гілок та меж є алгоритм, який запропонували у 1963 р. Літтл, Мурті, Суїні та Керол для розв'язування задачі комівояжера.

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

Розглянемо конкретизацію методу гілок та меж для задачі ко-мівояжера.

Вхідні дані задачі представлені у вигляді матриці відстаней

між пунктами С = |с;у}, і, j = 1, п , де ctj > 0, сй = оо, і = 1, п , що відпо-відає   умові    об’їзду   п    пунктів.    Причому   не    обов'язково

С. =С, ІФ  і.

1. Обчислення оцінки множини   D0. Позначимо маршрут d = (іиі2,...,іп,іх). Тоді пройдена відстань дорівнює

sid) = chll + с,л + --- + с.„ч-   (6-4)

Нехай аі = minctJ,і = \,п . Розглянемо матрицю с' = \с'у},, і, j = \,п

ДЄ с'ц = ctj - аі > 0 . Тоді

s[d) = £ at + (с■ і   + c'j j   + ... + сі J

7=1

або

s(d)= Yjat + s'\d),

7=1

ДЄ s'(d)=c'jj +с'. +... + с'. .

Далі виберемо   Ь. =minc'     j = l,n   і перейдемо до матриці

с" = |с"},   г, j = 1, и , де с" = с;у -Ьj > 0 . Тоді

!(</)=iflf + У>,- +(с,",    +С"     +... + С"    )

\   )     J-*    і       І->   )       \ hli          1іЧ       'п'і )

VI        <2<3

або

s{d)=YJai + YJbj+s"{d),         (6-5)

7=1      >1

ДЄ   5"(j)=C,";   +с".   +... + С,".  .

V     /   V2       1211    'п'і

Константи а.,г' = 1,и,   Ь,і = \,п  називаються константами зее-

I  7       7          j  7   J  7

дення.

Так  як   s"(d)>0,   TO   s(d)> YJai + ^Ь. .   Таким   чином   сума

7 = 1    j=\

П         П         \

YJ at + У, bj    дає оцінку знизу для значення цільової функції на

множині всіх допустимих маршрутів, тобто скінченність алгори-тму Літтла, Мурті, Суїні та Керола випливає зі скінченності чис-ла маршрутів для фіксованого числа пунктів п.

Нехай D0 — множина всіх замкнених маршрутів.

Sai + S^, •       (6-6)

Спраеедлиео теердження. Оптимальний маршрут, визначе-ний за зведеною матрщею С", є оптимальним і для задачі з мат-рицею С.

Воно випливає зі співвідношень (6.5) та (6.6).

2.         Перерахунок оцінок. Побудова замкненого маршруту від-

бувається поступово. На кожному кроці алгоритму визначається

тільки одна пара пунктів, які включаються до маршруту.

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

3.         Вибір фрагментів оптимального маршруту. У зведеній

матриці С" у кожному рядку та у кожному стовпчику є хоча б по

одному нульовому елементу. Пари пунктів \is,jp), для яких

с".   = 0 є претендентами для включення до оптимального марш-

lsJp      -1        -1

руту. Пару пунктів (ir,jk) треба вибрати так, щоб маршрутам, до яких не буде включена ця пара, відповідала довша відстань. Роз-глянемо деякий з таких маршрутів, в якому перехід з пункту іг відбувається в пункт z\, j^k, і в пункт jk комівояжер попадає тільки не з пункту j . Зрозуміло, що довжина такого маршруту буде не менше, ніж

.   = mm с . + mine.

Л         j(i*Jk)     rl        i(i*ir)    JP

Тоді

 

 

max A.

с' ,•   =0     's lsJp

4. Розгалуження множин. Множина розбивається на дві під-множини за принципом: переїзд з пункту і до пункту ік може належати оптимальному маршруту або не належати D0=D1\JD2, D1 - - множина фрагмента маршрутів після прийн-яття рішення про включення до оптимального маршруту пари пунктів (ir,jk), D2 — множина маршрутів, до яких пара пунктів (ir,jk) не включається.

Множині Д  відповідає матриця Q = {с*1' ],   і, j = 1, п -1. Щоб

отримати матрицю Сі, необхідно з матриці С" викреслити г-тий рядок (комівояжер з кожного пункту має виїжджати тільки один раз) та к-тий стовпчик (в кожний пункт комівояжер в'їжджає тільки один раз), а також з метою уникнення підциклів замінити значення с"j на cf\ = оо . Нумерація рядків та стовпчиків матри-ці С\ відповідає нумерації матриці С". Множині   D2   відповідає матриця

С2 =

|с*2) ], і, j = 1, п , в якій

!   .'   '

(2)

= С-

 

У

j = \,п і тільки с

 

a\Dl) = a{D0) + £ a

 

(i)

 

+ ІМЧ

 

 

 

a[D2) = a[D0) + £ a

 

(2)

 

+ZM2)

 

де af, йу(1) та a;(2), йу(2) - - константи зведення відповідно матриць

С\ та Сг.

5. Критерій оптимальності. Після того, як буде знайдений замкнутий маршрут ds, його треба перевірити на оптимальність. Ознакою того, що маршрут замкнений, є отримання матриці 2x2 (тобто 2 строчки та 2 стовпчики), яка має рівно дві дозволені па-ри пунктів. Маршрут ds є оптимальним, якщо його оцінка не пе-

РЄВЗаТ.™я:ІНШИХ КШЦЄВИХ ПЗР ДЄРЄВа Р°ЗВ'ЯЗКІВ-

1.         На кожному наступному кроці алгоритму треба враховува-ти весь фрагмент маршруту для розстановки додаткових заборон на переміщення.

2.         Коли фрагмент маршруту проходить (п - 1) пункт, то зали-шається однозначно спланувати два переходи.

3.         Якщо існує п операцій, які здійснюються на одному агрега-ті, то матриця, на основі якої застосовується алгоритм гілок та веж, має вигляд табл. 6.1,

Таблщя 6.1

 

            1          2          3                      п          п+ 1

1          00        12        13        ...         \п         1и+1

2          х21      00        23        ...         2п        2п+\

Закінчення табл. 6.1

 

            1          2          3                      п          п+ 1

3          31        ^ 32     00                    Зп        Зи+1

;           ...         ;           ...

п          In         2й        Зй        ...         00        даг+1

п + 1   л+1,1   й + 1,2            л+1,3   ...         п+;п    оо

де: X; и+1 (г = 1, и) — заключний час, якщо /-та операція є остання в послідовності;

хп+и (і = 1,и] — підготовчий час, якщо /-та операція є перша в послідовності.

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

Для викладення алгоритму розв'язування задачі введемо по-значення:

А\ — тривалість виконання (включаючи переналадку, якщо вона необхідна) першої операції і-ої роботи.

В{ — тривалість виконання (включаючи переналадку, якщо вона необхідна) другої операції і-ої роботи.

Тоді, якщо всі роботи поступили в систему одночасно, то оп-тимальна послідовність, яка є однаковою для обох машин, задо-вольняє умову:

тіпЦ -, BJ+1) ( тіпЦ +1, В )

для будь-якої париу'-ої і(/ + 1)-ої суміжних робіт даної послідов-ності.

Цей алгоритм може бути застосований для побудови оптима-льної послідовності для трьох послідовних взаємонезамінюваних машин за умови:

min^4 - + В , С,+1) (тіп^ +1 + В-+1, С +Вф якщо

mm Аі > vox Bj

або

mm Сі > max 5 ,

ї=\,п     у=1, п

де С — тривалість виконання г-ої роботи на третій машині.

Припустимо, що є певна кількість т різних робіт, кожна з яких повинна пройти п послідовних операцій на машинах з номе-рами 1, 2,..., п. Порядок виконання операцій для кожної з робіт однаковий (рис. 6.2). Різнитися між собою роботи можуть лише тривалістю виконання окремих операцій.

Робота 1

Робота 2

Машина 1    —>І    Машина 2     —>І    Машина п

Робота т

Рис. 6.2.

Робота, яка почне виконуватися першою, після її опрацювання на першій машині одразу потрапляє на другу машину, і так само без затримок проходить весь подальший технологічний процес. Друга за першою робота почне виконуватися лише після того, як машина 1 звільниться від опрацювання першої роботи. Після то-го, як друга робота буде опрацьованою машиною 1, може знадо-битися певний час на очікування, поки машина 2 закінчить пер-шу роботу, і так далі. Потрібно визначити таку послідовність виконання робіт, за якої загальна тривалість виконання усіх робіт буде мінімальною.

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

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

В такому випадку використовуються один з чотирьох підходів:

—        комбінаторний аналіз;

—        математичне програмування;

—        керований перебір по методу гілок та меж;

—        імітаційне моделювання.

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

Приклад 6.1. Задача про дві машини (п = 2).

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

другій машині — через Ь. (і = 1,5j, (табл. 6.2).

Таблщя 6.2

 

Робота, і         12345

Тривалість   виконання   на   першій машині, а,   10        7          5          15        14

Тривалість виконання на другій ма-шині, Ь.         8          6          9          11        13

Найменше часу потрібно для виконання роботи 3 на першій машині:

а3 = 5 = min {10, 7, 5, 15, 14, 8, 6, 9, 11, 13}.

Тому роботу 3 слід розмістити в оптимальній послідовності першою.

Далі найменшою є тривалість виконання роботи 2 на другій машині:

Ь2 = 6 = min {10, 7, 15, 14, 8, 6, 11, 13}.

Тому роботу 2 потрібно виконувати останньою. Залишилося визначити порядок виконання робіт 1, 4, і 5. По-слідовно визначаємо:

min {10, 15, 14, 8, 6, 11, 13} = 8 = h

- роботу 1 виконуватимемо передостанньою;

min {15, 14, 11, 13} = 11 = ba

— роботу 4 виконуємо перед роботою 1.

Таким чином, оптимальною послідовністю виконання робіт є наступна: {3, 5, 4, 1, 2}. За цієї послідовності загальний час вико-нання робіт дорівнюватиме 59 год. Календарний графік робіт у заданій послідовності наведено на рис. 6.3.

/                                  14        19               32  34            45          53         59

Машина 1                  Ь3 = 9             Ь5 = 13                       Й4 = П            Ьу =8   й2 = 6

            5          19        34             44          51           

Машина 2      а3 = 5  а5 = 14            а4 = 15            ах = 10            а2 = 1             

            1          1          1                1              

                                   10                               20             30   40        50        6(         > Час

Рис. 6.3.

Навпаки, графік виконання робіт у послідовності {1, 2, 3, 4, 5,}, показаний у табл. 6.2, вимагатиме не 59, a 64 год. Таким чином, оптимізація послідовності виконання робіт дозволяє мінімізувати час загальної тривалості їх виконання.