Планирование работника с перекрывающимися периодическими задачами
С одним работником, который может выполнять только одну задачу за раз (но может мгновенно переключаться между задачами)
Учитывая список задач,
- определяется как «n секунд каждые m секунд» (например, 5 секунд каждые 3600 секунд)
Как мне найти лучшее время начала и посчитать для каждой задачи?
Если бы каждая задача составляла «1 секунду каждые 60 секунд», у каждой была бы уникальная начальная секунда, и счет был бы бесконечным (устойчивое состояние) .
Если бы это было «1 секунда каждые 4 секунды» и «1 секунда каждые 3 секунды», результат был бы: «0, бесконечно и 3, 3 раза».
- Надеюсь, самая простая форма
Если у меня уже есть список задач с указанием «секунды запуска и количество раз», как будет выглядеть функция, возвращающая: {start, count} для дополнительных {n секунд каждые m секунд} задачи?
-
(Чуть более сложная форма -
если вместо "n секунд каждые m секунд",
задачи были определены как «n секунд каждые 10 секунд»,
где я мог бы выбрать число m в диапазоне l - o (но мне пришлось бы зафиксировать это m, пока задача не была завершена),
позволит ли это лучше использовать рабочую силу?
Как мне выбрать лучшее «м»?
Ответы 4
Проблемы такого типа сложно решить, но относительно легко оптимизировать. Взгляните на моделирование отжига, Великого потопа или генетических алгоритмов.
Хммм, вот небольшое предложение: если наибольший общий делитель m больше или равен сумме n, решение является устойчивым.
Я бы выбрал набор задач, который имеет максимальную сумму n, так что gcd m больше или равно этой сумме.
Что имеет смысл - что-то вроде 3, 4, где они относительно простые, имеет НОД 1, так что это не стабильное состояние. Можно ли продлить это, чтобы получить что-нибудь по подсчетам?
Похоже, это не объясняет «разбиение» на три задачи: A {1 каждые 4} B {1 каждые 4} C {1 каждые 2} GCD (2, 4) = 2 Sum (N) = 3 Но это стабильно состояние ACBCACBC ... -
Это кажется довольно сложным даже с двумя задачами. Я смотрю на диаграмму «часы», где наибольшее m обозначает количество «часов», а соответствующие первые n «часов» заполнены.
Что вообще можно сделать, начав непосредственно перед заполненными слотами и вращая по часовой стрелке другую задачу на м2 «часов»?
Возврат к процедуре: да! И действительно, мой ответ дал условие «если», а не условие «если и только если». Действительно сложная проблема ...
Я думаю, это зависит от того, как вы определяете «лучший». Например, если вы хотите, чтобы задачи выполнялись каждые m секунд «в среднем», есть простой способ сделать это, используя тот же алгоритм, что и метод Брезенхэма для рисования линий (задача, выполняющая «n секунд каждые m секунд», намного как разбросать n вертикальных шагов среди m горизонтальных шагов при рисовании линии). Назначьте каждой задаче счетчик и значение шага (для «1 секунды каждые 3 секунды» шаг будет 1/3). Затем добавляйте шаг к счетчику каждый «цикл». Когда счетчик становится больше нуля, эта задача должна выполняться (и вычесть 1 из счетчика). Если у вас несколько счетчиков больше нуля, выберите самый большой. Это может дать вам решение, которое «достаточно хорошо» и для немного более сложной формы.
Пример «1/4» и «1/3» звучит так, будто у вас есть требование запускать задачи «точно» с интервалом в m секунд. Начать со списка и добавить новую задачу для максимального увеличения количества - не сложная задача поиска, но я не думаю, что это то, что вам нужно. Пример A (1/4) B (1/4) C (1/2) даст A B x x A B x x после добавления A, затем B. Тогда C нельзя добавить,
Я думаю, что есть очевидные кандидаты на функции фитнеса - таблица n, m, start может иметь функцию фитнеса, которая представляет собой часть времени, когда запланировано не более одной задачи. GA / отжиг имеет хорошие шансы найти решение для устойчивого состояния, если оно существует. Но в таких случаях, как (1/4), (1/3) w, где, кажется, нет решения в устойчивом состоянии, определение «наилучшего» также должно определять вашу фитнес-функцию.
См. w: Планирование (вычисления). Ссылка включает хороший список стратегий планирования:
[Scheduling] refers to the way processes are assigned priorities in a priority queue. This assignment is carried out by software known as a scheduler. The scheduler is concerned mainly with:
- CPU utilization - to keep the CPU as busy as possible.
- Throughput - number of process that complete their execution per time unit.
- Turnaround - amount of time to execute a particular process.
- Waiting time - amount of time a process has been waiting in the ready queue.
- Response time - amount of time it takes from when a request was submitted until the first response is produced.
Не могли бы вы предложить фитнес-функцию, которая не развивается, повторяя каждую задачу для каждого подсчета?