Как решить задачу о распределении временных интервалов?

Задан один временной интервал, в рамках которого будут распределятся процессы. Например 100 дней.

Есть N количество процессов, которые имеют разную продолжительность от 1 до M дней. В один и тот же момент времени не может выполнятся более чем K процессов.

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

Исполнитель у нас один, и одновременно он может выполнять не более K процессов. Последовательность и промежутки - не имеют значения.

Под максимальной рациональностью подразумевается впихнуть в изначально заданный интервал все имеющиеся процессы, таким образом, что бы в один момент времени не выполнялось более K процессов.

Если это невозможно - то решить задачу минимально выходя за рамки. Т.е. Когда возникает ситуация что все процессы не умещаются в заданный интервал, мы можем повесить на исполнителя еще K + n процесс, но за пределы изначально заданного интервала выходить нельзя.

На выходе мы должны получить последовательность выполнения процессов.

Не могу понять как решать эту задачу. Может подскажете алгоритм, или вообще в какую сторону копать?
  • Вопрос задан
  • 484 просмотра
Пригласить эксперта
Ответы на вопрос 2
xmoonlight
@xmoonlight
https://sitecoder.blogspot.com
Ответ написан
Комментировать
sergiks
@sergiks Куратор тега Алгоритмы
♬♬
Это типичная задача упаковки (packing problem).

В «коробку» длиной 100 и шириной K надо впихнуть комплект колбас шириной 1 и разной длины.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы