Эвристические алгоритмы для максимизации дохода и количества требований, обслуживаемых на параллельных приборах

Множество требований необходимо обслужить на параллельных приборах. Для каждого требования известно время готовности к обслуживанию и установлен срок, не позднее которого требование должно быть обслужено. Если обслуживание требования завершается к установленному сроку, то начисляется определенная прибыль. В противном случае требование считается не обслуженным в срок, и прибыль за это требование не начисляется. Рассматривается критерий максимизации взвешенной суммы начисленной прибыли и количества требований, обслуженных в срок. Исследованы свойства целевой функции, которые позволяют строить оптимальные расписания обслуживания требований. Разработаны три эвристических алгоритма: алгоритм имитации отжига, поиск с запретами и генетический алгоритм. Разработанные программы протестированы на задачах средней размерности ($50$ требований и $5$ приборов) и на задачах большой размерности ($500$ требований и $50$ приборов). Даны рекомендации по использованию разработанных алгоритмов и полученных результатов в календарном планировании производства.