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

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

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

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

Типовим завданням теорії розкладів являється проблема складання розкладу роботи технологічної лінії, що складається з m станків (і=l,t), на якій треба обробити партії з n деталей (j=l,n).

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

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

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

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

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

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

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

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

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

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

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

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

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

<== попередня сторінка	\|	наступна сторінка ==>
Теорія масового обслуговування.	\|	Завдання теорії корисності і підхід Байєса.

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

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