Побудова ПДС-алгоритму розв’язання задачі мінімізації сумарного зваженого запізнення виконання робіт на одному приладі
Павлов А.А., Мисюра Е.Б., Шевченко К.Ю.
На основі попередніх досліджень властивостей задачі мінімізації сумарного зваженого запізнення виконання робіт на одному приладі побудований ПДС-алгоритм її розв’язання. Для запропонованого алгоритму виділені поліноміальна та декомпозиційна складові, сформульовані умови реалізації цих складових для окремої індивідуальної задачі. Даний алгоритм дозволяє отримувати точні розв’язки для широкого класу індивідуальних задач великої потужності за прийнятний час, а також близькі до оптимальних розв’язки, якщо обчислення перериваються передчасно. Алгоритм пристосований до паралельних розрахунків.
