Упреждающее планирование задач в C

Question

У меня есть список задач, которые имеют 3 параметра, которые необходимо учитывать при планировании: время выпуска, продолжительность и срок.

Время выпуска - самое раннее возможное время начала задачи. Продолжительность - количество времени, затрачиваемое на выполнение задачи. Срок - самое позднее возможное время окончания задачи.

Например, ввод:

4  
2   3   5  
4   2   8  
1   2   6  
6   4   11

Это означает, что есть 4 задачи, как указанопервая строка.Начиная со следующей строки, первый столбец - время выпуска, второй столбец - продолжительность, а третий столбец - крайний срок для каждой задачи.

Способ планирования этих задач будет следующим:

Time    Task

1-2     3
2-5     1
5-6     3
6-8     2
8-12    4 <--- Deadline Violation

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

Итак, для вышеприведенного случая мы должны иметь вывод:

1   2   3
2   5   1
5   6   3
6   8   2
8   12  4

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

Я думаю, что для этой цели нам нужно использовать жадный алгоритм, но я не совсем уверен.

Поэтому я ищу возможные алгоритмы / подходы для решения этой проблемы.

Answer 1

Предлагаю подойти к проблеме с помощью теории расписаний относительно точных методов.Написание математической модели вашей задачи приводит к следующему оптимальному решению.

1 3 3

3 6 1

6 8 2

8 12 4

Целевая функция минимизирует задержку, т.е. количество «опозданий».Для вашего примера есть 2 дня с опозданием.

Answer 2

В теории планирования ваша проблема может быть выражена с помощью следующих обозначений:

1|r_j|sum(U_j)

(Вы можете посмотреть эту вики-страницу для более подробного объяснения обозначений)

Согласно этому веб-сайту , ваша проблема является NP-сложной, поскольку, например, 1 | r_j | L_max является NP-сложной.

Это означает, что вы не можете найти жадный алгоритм, которыйрешит вашу проблему за полиномиальное время (если только P = NP, то есть открытый вопрос на миллион долларов , но никто в это не верит).