Планирование работника с перекрытием периодических задач

Question

С одного работника, который может выполнять только одну задачу за один раз (но может переключаться между задачами мгновенно)

Учитывая список задач,
- определяется как «N секунд , каждые m секунд "(например, 5 секунд каждые 3600 секунд)

Как я могу найти лучшее время начала и подсчет для каждой задачи?

Если каждая задача была «1 секунда, каждые 60 секунд», каждая из них имела бы уникальную начальную секунду, а счетчик был бы бесконечным (устойчивое состояние).
Если бы это было "1 секунда каждые 4 секунды" и "1 секунда каждые 3 секунды", то результат будет: "0, бесконечные и 3, 3 раза"

- Надеюсь простейшей форме

Если у меня есть список задач, разработанных с «началом второго и количества раз», что бы возвращала функция: {start, count} для дополнительной задачи {n секунд каждые m секунд}?

- (Немного более сложная форма -
, если вместо «N секунд каждые м сек»,
задачи были определены как «N секунд каждые l..o секунды»,
, где я мог выбрать число т в диапазоне л - о (но придется совершить что т пока задача не была закончена),
бы, что позволит лучше использовать работник
Как выбрать лучший «т»

Answer 1

?

Этот тип проблемы трудно решить, но относительно легко оптимизировать. Взгляните на Simulated Отжиг, Великий Поток или Генетические Алгоритмы.

Answer 2

Хм, вот небольшое предложение: если наибольший общий делитель m больше или равен сумме n, решение является устойчивым.

Я бы выбрал множество задач, которые имеют максимальную сумму n, такую, что gcd of m больше или равно этой сумме.

Answer 3

Я думаю, это зависит от того, как вы определяете «лучший». Например, если вы хотите, чтобы задачи выполнялись каждые m секунд «в среднем», есть простой способ сделать это, используя тот же алгоритм, что и метод Bresenham, для рисования линий (задача «n секунд каждые m секунд» как рассеивание n вертикальных шагов среди m горизонтальных шагов при рисовании линии). Назначьте каждой задаче счетчик и значение шага (для «1 секунда каждые 3 секунды» шаг будет 1/3). Затем добавьте шаг к счетчику каждый цикл. Когда счетчик выходит за ноль, эта задача должна выполняться (и вычитать 1 из счетчика). Если у вас несколько счетчиков выше нуля, выберите самый большой. Это может дать вам решение, которое «достаточно хорошо» для немного более сложной формы.

Пример «1/4» и «1/3», хотя звучит так, будто у вас есть требование выполнить задания «точно» на расстоянии в несколько секунд. Начиная с списка и добавления новой задачи, чтобы максимизировать количество, это не сложная проблема поиска, но я не думаю, что это то, что вам нужно. Пример A (1/4) B (1/4) C (1/2) дал бы AB xx AB xx после добавления A тогда B. Тогда C нельзя было добавить,

Я думаю, что есть очевидные кандидаты на функции фитнеса - таблица из n, m, start может иметь функцию пригодности, которая является частью времени, когда запланировано не более одной задачи. GA/отжиг имел бы хорошие шансы найти решение устойчивого состояния, если оно существует.Но в таких случаях, как (1/4), (1/3), где, как представляется, нет устойчивого решения, определение «наилучшего» также должно определять вашу функцию фитнеса.

Answer 4

См. w:Scheduling (computing). Ссылка включает в себя хороший список стратегий планирования:

[Планирование] относится к способу процессов назначаются приоритеты в очереди на приоритета. Это назначение - , выполняемое программным обеспечением, известным как планировщик . Планировщик касается в основном с:

• загрузки ЦП - держать процессор, как занят, как это возможно.
• Пропускная способность - номер процесса, который завершает их исполнение за единицу времени.
• Оборот - количество времени до Выполнение определенного процесса.
• Ожидание - время Процесс ждет в готовой очереди.
• Время отклика - сумма времени, которое требуется, когда запрос был отправлен до получения первого ответа .