Планирование работы, чтобы минимизировать потери
У меня проблема с планированием работы. Нам дают время начала, время
завершить заказ, срок.
Дано что start time + time в
complete <= deadline,
Мне также дали потери, которые произойдут, если я не смогу
завершить работу до истечения срока. Я должен разработать алгоритм, чтобы минимизировать потери.
Я пытался изменить стандартный алгоритм динамического программирования для максимизации прибыли при планировании работы, но безуспешно.
Какой алгоритм я могу использовать для решения вопроса?
Решение
Динамическое программирование — это не правильный подход, основанный на том, что вы хотите оптимизировать. Вы можете найти оптимизированное расписание, используя жадный подход.
Вот тщательный руководство с примером кода для вашего языка желаний (C ++), в руководстве предполагается, что каждая работа занимает всего 1 единицу времени, которую вы можете легко изменить, используя time_to_complete вместо.
Другие решения
Ваша проблема похожа на рюкзак. Использование жадного подхода удобно, если вы на самом деле не ищете лучшее из возможных решений, а просто «достаточно хорошее».
Преимущество жадного подхода в том, что его стоимость значительно ниже, чем в других «более тщательных» подходах, но, если вам нужно Лучшее решение вашей проблемы, я бы сказал, что возвращение — это путь.