• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Статья

Estimates of the absolute error and a scheme for an approximate solution to scheduling problems

Computational Mathematics and Mathematical Physics. 2009. Vol. 49. No. 2. P. 373-386.
A. A. Lazarev.

Предлагается новый качественный подход к нахождению оценки абсолютной погрешности и построению приближённого решения классических NP-трудных задач теории расписаний для одного и нескольких приборов с критериями минимизации максимального временного смещения и минимизации общего момента окончания обслуживания требований. Вводится понятие метрики (расстояния) между примерами. Идея предлагаемого подхода состоит в построении по исходному примеру задачи другого примера, для которого удаётся найти оптимальное или приближённое решение с минимальным расстоянием до исходного примера во введённой метрике. Полученное решение будет иметь минимальную оценку абсолютной погрешности целевой функции.