DOI: https://doi.org/10.26642/tn-2017-2(80)-159-165

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

Тамара Миколаївна Локтікова, Андрій Васильович Морозов, Володимир Олександрович Скачков

Анотація


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

Ключові слова


теорія розкладів; перестановки; дискретні оптимізаційні задачі; задача Джонсона

Повний текст:

PDF

Посилання


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


Пристатейна бібліографія ГОСТ


  1. Панішев А.В. Вступ до теорії складності дискретних задач / А.В. Панішев, О.М. Данильченко, В.О. Скаков. – Житомир : ЖДТУ, 2004. –236 с.
  2. Танаев В.С. Введение в теорию расписаний / В.С. Танаев, В.В. Шкурба. – М. : Наука, 1975. – 256 с.
  3. Панишев А.В. Модели и методы оптимизации замкнутых маршрутов на транспортных сетях / А.В. Панишев, А.В. Морозов. – Житомир : ЖГТУ, 2014. – 316 с.
  4. Панишев А.В. Модели и методы оптимизации в проблеме коммивояжера / А.В. Панишев, Д.Д. Плечистый. – Житомир : ЖГТУ, 2006. – 300 с.
  5. Гэри М. Вычислительные машины и труднорешаемые задачи / М.Гэри, Д.Джонсон. – М. : Мир, 1982. – 416 с.
  6. Бронштейн Е.М. Детерминированные оптимизационные задачи транспортной логистики / Е.М. Бронштейн, Т.А. Зайко // Автоматика и телемеханика. – 2010. – № 10. – С. 133–147.
  7. Майника Э. Алгоритмы оптимизации на сетях и графах / Э.Майника – М. : Мир, 1981. – 323 с.
  8. Ловас Л. Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии / Л.Ловас, М.Пламмер. – М. : Мир, 1998. – 653 с.
  9. Пападимитриу Х. Комбинаторная оптимизация. Алгоритмы и сложность / Х.Пападимитриу, К.Стайглиц. – М. : Мир, 1985. – 510 с. 
  10. Matsiy O.B. A Recurrent Algorithm to Solve the Weighted Matching Problem / O.B. Matsiy, A.V. Morozov, A.V. Panishev // Cybernetics and Systems Analysis. – 2016. – Vol. 52, Issue 5. – Pp. 748–757. – Access mode : DOI: 10.1007/s10559-016-9876-4.




Copyright (c) 2017 Тамара Миколаївна Локтікова, Андрій Васильович Морозов, Володимир Олександрович Скачков

Ліцензія Creative Commons
Це видання ліцензовано за ліцензією Creative Commons Із Зазначенням Авторства - Некомерційна 4.0 Міжнародна.