Реферат: В работе рассматривается задача составления расписаний на нескольких машинах и исследуется ее вычислительная сложность в случае дополнительных ограничений. Здесь исследуются варианты задачи c предписаниями операций в позициях машин и учетом ресурсов невозобновимого типа. Выделяются NP- трудные частные случаи и строятся алгоритмы с гарантированными оценками точности на основе подходов списочного типа для критерия минимизации длины расписания. Устанавливаются новые свойства дополнительных ограничений, позволяющие обобщать известные ранее результаты при выполнении условий на нижнюю границу целевой функции.

Библиографическая ссылка: Захарова Ю.В.
Вычислительная сложность задачи составления расписаний с дополнительными ограничениями на размещение операций и потребление ресурсов
В сборнике Труды XX Международной научной конференции "Проблемы теоретической кибернетики". МГУ имени М.В. Ломоносова. – ООО «МАКС Пресс»., 2025. – C.44-47. – ISBN 978-5-317-07402-9. РИНЦ

Идентификаторы БД:

РИНЦ:

82553407

Цитирование в БД: Пока нет цитирований