Моделі послідовно-паралельного впорядкування транспортних операцій
DOI:
https://doi.org/10.26642/tn-2017-2(80)-159-165Ключові слова:
теорія розкладів, перестановки, дискретні оптимізаційні задачі, задача ДжонсонаАнотація
Предметом розгляду в роботі є задача, що належить до детермінованої теорії розкладів. У роботі запропоновано модель задачі складання розкладу мінімальної довжини. Також розглядаються змістовні та математичні постановки задач, які є узагальненнями цієї задачі. Необхідність формулювання і розв’язання узагальнень задачі продиктовано потребою оптимізації виробничих процесів. Зокрема, розглядається процес функціонування гнучкого автоматизованого підприємства, до складу якого належить транспортно-складська система і паралельнодіючі технологічні лінії. При цьому під технологічними лініями можуть розглядатися конвеєри, обробні центри, лінії збирання тощо. Розглянута в роботі математична модель задачі описує процес взаємодії транспортного механізму з деякою кількістю паралельно діючих технологічних ліній, на яких виконується певна множина робіт. Є інформація про роботи, призначені на кожну лінію. Також задано час виконання кожної роботи. Роботи є неперервними і не можуть розриватися. Виробничі лінії є незалежними, тобто функціонують незалежно одна від одної. Функції транспортного засобу полягають у забезпеченні ліній засобами, без яких не може бути розпочато певну роботу. Для її виконання транспортний механізм за вказаний час доставляє зі складу на лінію необхідні засоби і повертає на склад, затративши за тим же маршрутом на зворотній шлях задану кількість часу. Кожна робота не може розпочинатися раніше моменту доставки ресурсів, необхідних для її виконання. Потрібно знайти таку траєкторію руху транспортного засобу, що мінімізувала би час функціонування всієї системи. Показано, що задача може бути зведеною до задачі Джонсона 2-x n.Посилання
Panishev, A.V., Danylchenko, O.V. and Skachkov, V.O. (2004), Vstup do teorii' skladnosti dyskretnyh zadach, ZhDTU, Zhitomir, 236 p.
Tanaev, V.S. and Shkurba, V.V. (1975), Vvedenye v teoryju raspysanyj, Moskva, 256 p.
Panishev, A.V. and Morozov, A.V. (2014), Modeli i metody optimizatsii zamknutykh marshrutov na transportnoy seti, monografiya, ZhDTU, Zhitomir, 316 p.
Panishev, A.V. and Plechistyy, D.D. (2006), Modeli i metody optimizatsii v probleme kommivoyazhera, monografiya, ZhDTU, Zhitomir, 300 p.
Gjeri, M. and Dzhonson, D. (1982), Vychislitel'nye mashiny i trudnoreshaemye zadachi, Moskva, 416 p.
Bronshteyn, E.M. and Zaiko, T.A. (2010), «Determenirovannye optimizatsionnye zadachi transportnoy logistiki», Avtomatika i telemekhanika, Vol. 10, pp. 133–147.
Maynika, E. (1981), Algoritmy optimizatsii na setyakh i grafakh, Mir, Moskva, 323 p.
Lovas, L. and Plammer, M. (1998), Prikladnye zadachi teorii grafov. Teoriya parosochetaniy v matematike, fizike, khimii, Mir, Moskva, 653 p.
Papadimitriu, Kh. and Stayglits, K. (1985), Kombinatornaya optimizatsiya. Algoritmy i slozhnost', Mir, Moskva, 510 p.
Matsiy, O.B., Morozov, A.V. and Panishev, A.V. (2016), «A Recurrent Algorithm to Solve the Weighted Matching Problem», Cybernetics and Systems Analysis, Vol. 52, Issue 5, pp 748–757, available at: DOI: 10.1007/s10559-016-9876-4
##submission.downloads##
Опубліковано
Як цитувати
Номер
Розділ
Ліцензія
Авторське право (c) 2020 Тамара Миколаївна Локтікова, Андрій Васильович Морозов, Володимир Олександрович Скачков
Ця робота ліцензується відповідно до Creative Commons Attribution-NonCommercial 4.0 International License.
Автор, який подає матеріали до друку, зберігає за собою всі авторські права та надає відповідному виданню право першої публікації, дозволяючи розповсюджувати даний матеріал із зазначенням авторства та джерела первинної публікації, а також погоджується на розміщення її електронної версії на сайті Національної бібліотеки ім. В.І. Вернадського та у відкритому доступі в електронному архіві університету та на сайті журналу.
