УЗАГАЛЬНЕННЯ ЗАДАЧ УПОРЯДКУВАННЯ З УРАХУВАННЯМ НЕПОВНОГО ЗАВАНТАЖЕННЯ

K. D. Karavaiev; V. A. Turchyna

doi:10.15421/322207

K. D. Karavaiev Дніпровський національний університет імені Олеся Гончара
V. A. Turchyna Дніпровський національний університет імені Олеся Гончара

Ключові слова: дискретна оптимізація, теорія розкладів, оптимальні упорядкування, максимальне паросполучення, неповне завантаження

Анотація

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