Методи теорії розкладу

Розділ дослідження операцій, що вивчає ефективність вико­нання операцій в залежності від порядку поступання, нази­вається теорією розкладу.

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

Одною з перших математичних моделей теорії розкладів г відома в теорії заощаджень найпростіша модель оптимальної партії поставки, яку можна використати для визначення оптималь­ної партії випуску виробів. Завдання пов'язані з впорядкуванням операцій. Вони виникають при виборі черговості їх виконання [22].

Типовим завданням теорії розкладів являється проблема складання розкладу роботи технологічної лінії, що складається з m станків (i=l,t), на якій треба обробити партії з n деталей (j=1,п). Критерієм оптимальності розкладу стане мінімальний час оброб­ки всіх п деталей. При цьому кожна деталь повинна послідовно пройти обробку на кожному станку. Вхідними даними служить протяжність tij обробки на i-ому станку j-ої деталі. Треба визна­чити порядок обробки цих деталей, мінімізуючий загальний період їх виготовлення. При цьому приймаються обмеження: об­робка кожної деталі на i-ому станку повинна починатися не раніше, ніж закінчиться обробка на станку і-1; на кожному стан­ку одночасно може оброблятися не більше одної деталі; операція, що почалася, не переривається до повного її завершення.

Складність розв'язання завдання для t станків і п деталей полягає в переборі великої кількості можливих варіантів порядку запуску й порівняння їх за довжиною розкладу. Так як для одної машини можна скласти п! різних розкладів, то кількість допусти­мих планів для t станків складе (п!)t.

До перших робіт в даній галузі відноситься робота С. Джонсона для випадку двох станків. С. Джонсоном був одержа­ний простий алгоритм розв'язання, що викликав спроби узагаль­нити його для більш складних випадків.

Завдання для двох станків

Є два станки і п деталей. Кожна з деталей повинна пройти обробку спочатку на першій, а потім на другій машині. Час опе­рації j-ої деталі на першому станку позначимо через aj, на дру­гій — через bj,. Треба дати розклад, мінімізуючий загальний час обробки всіх деталей.

Опишемо алгоритм для одержання оптимального розкла­ду. Ідея його полягає в прагненні максимально скоротити про­стої другої машини при повному виключенні переривів роботи і штучних простоїв першої (табл. 5.2).

Таблиця 5.2

Матриця тривалості робіт

1. Переглядаємо тривалості робіт ai i bj, j=l, n і знаходимо серед них найменшу.

2. Якщо вона відноситься до першого станка, то відповіді І:І деталь для обробки розміщується першою.

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

4. Викреслюємо стовпчик, що відповідає цій деталі.

5. Процес повторюється по відношенню до деталей,що за­ лишилися.

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

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

Тема 6. Методи математичного програмування і планування