Новый подход к решению задачи «Минимизация суммарного взвешенного опоздания при выполнении независимых заданий с директивными сроками одним прибором»

摘要

На основании исследования свойств данной задачи предложен новый подход к ее решению и разработанный на его основе эффективный приближенный алгоритм. Сформулированы условия, при выполнении которых оптимальное решение достигается за полиномиальное время. При невыполнении этих условий предлагаются правила отсечений, позволяющие существенно сократить время решения задачи. Данный алгоритм позволил получить точные решения для ряда задач с числом переменных существенно большим 50-ти. Оптимальные значения функционала, полученные данным алгоритмом для тестовых примеров, совпали со значениями функционала, рассчитанными другими известными методами.