Моделі послідовно-паралельного впорядкування транспортних операцій

Abstract

Предметом розгляду в роботі є задача, що належить до детермінованої теорії розкладів. У роботі запропоновано модель задачі складання розкладу мінімальної довжини. Також розглядаються змістовні та математичні постановки задач, які є узагальненнями цієї задачі. Необхідність формулювання і розв’язання узагальнень задачі продиктовано потребою оптимізації виробничих процесів. Зокрема, розглядається процес функціонування гнучкого автоматизованого підприємства, до складу якого належить транспортно-складська система і паралельнодіючі технологічні лінії. При цьому під технологічними лініями можуть розглядатися конвеєри, обробні центри, лінії збирання тощо. Розглянута в роботі математична модель задачі описує процес взаємодії транспортного механізму з деякою кількістю паралельно діючих технологічних ліній, на яких виконується певна множина робіт. Є інформація про роботи, призначені на кожну лінію. Також задано час виконання кожної роботи. Роботи є неперервними і не можуть розриватися. Виробничі лінії є незалежними, тобто функціонують незалежно одна від одної. Функції транспортного засобу полягають у забезпеченні ліній засобами, без яких не може бути розпочато певну роботу. Для її виконання транспортний механізм за вказаний час доставляє зі складу на лінію необхідні засоби і повертає на склад, затративши за тим же маршрутом на зворотній шлях задану кількість часу. Кожна робота не може розпочинатися раніше моменту доставки ресурсів, необхідних для її виконання. Потрібно знайти таку траєкторію руху транспортного засобу, що мінімізувала би час функціонування всієї системи. Показано, що задача може бути зведеною до задачі Джонсона 2-x n.