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

Cite: Захарова Ю.В.
Вычислительная сложность задачи составления расписаний с дополнительными ограничениями на размещение операций и потребление ресурсов
In compilation Труды XX Международной научной конференции "Проблемы теоретической кибернетики". МГУ имени М.В. Ломоносова. 2025.

Identifiers: No identifiers

Citing: Пока нет цитирований