Вертушка планирования

В математике и информатике проблема планирования «вертушка» — это проблема планирования в реальном времени с повторяющимися задачами единичной длины и жесткими ограничениями на время между повторениями.

Если у проблемы планирования с вращением есть решение, то оно предполагает, что расписание периодически повторяется. Этот повторяющийся узор напоминает повторяющийся узор установленных и снятых штифтов на шестернях шифровальной машины с вращающимся колесом , что оправдывает название. ^[1] Если часть времени, необходимая для каждой задачи, составляет менее 3/4 общего времени, решение всегда существует, но некоторые проблемы планирования с использованием «вертушки», задачи которых в общей сложности занимают чуть более 5/6 общего времени, не работают. иметь решения.

Некоторые формулировки задачи планирования «вертушки» являются NP-трудными .

Определение

Входные данные для планирования «вертушки» состоят из списка задач, каждая из которых, как предполагается, занимает единицу времени на реализацию. С каждой задачей связано положительное целое значение, ее максимальное время повторения (максимальное время от начала одного экземпляра задачи до следующего). В любой момент времени может быть выполнена только одна задача. ^[1]

Желаемый результат — это бесконечная последовательность, определяющая, какую задачу выполнять в каждую единицу времени. Каждая входная задача должна появляться в последовательности бесконечно часто, при этом наибольший разрыв между двумя последовательными реализациями задачи не должен превышать время повторения задачи. ^[1]

Например, бесконечно повторяющаяся последовательность ABACABACABAC... будет действительным графиком вертушки для трех задач A, B и C с временем повторения не менее 2, 4 и 4 соответственно.

Плотность

Если задачи, которые необходимо запланировать, пронумерованы $1$ к $n$ , позволять $t_{i}$ обозначают время повторения задачи $i$ . В любом допустимом расписании задача $i$ должен использовать $1/t_{i}$ доля общего времени, количество, которое будет использоваться в расписании, повторяющем эту задачу точно в указанное время повторения. Плотность задачи планирования «вертушки » определяется как сумма этих дробей: $\textstyle \sum 1/t_{i}$ . Чтобы решение существовало, время, затрачиваемое на каждую задачу, не может в сумме превышать общее доступное время, поэтому необходимо, чтобы плотность была не более $1$ . ^[2]

Этого условия плотности также достаточно для существования расписания в том особом случае, когда все времена повторения кратны друг другу. Например, это будет верно, если все времена повторения являются степенями двойки . В этом случае можно решить задачу, используя непересекающуюся накрывающую систему . ^[1] Имея максимальную плотность $1$ также достаточно, когда имеется ровно два различных времени повторения. ^[2] Однако в некоторых других случаях плотности не более 1 недостаточно. В частности, нет расписания для трех предметов с периодами повторения. $t_{1}=2$ , $t_{2}=3$ , и $t_{3}$ , независимо от того, насколько велик $t_{3}$ может быть, даже несмотря на то, что плотность этой системы всего лишь $5/6+1/t_{3}$ . ^[3]

Нерешенная задача в информатике :

Есть ли решение у каждой проблемы планирования с плотностью не более 5/6?

(еще нерешенные проблемы по информатике)

Каждый случай вертушки планирования с максимальной плотностью $3/4$ имеет решение, ^[4] и было высказано предположение, что каждый экземпляр с плотностью не более $5/6$ имеет решение. ^[3]^[5] Каждый экземпляр с тремя различными периодами повторения и максимальной плотностью. $5/6$ имеет решение. ^[5] Кроме того, анализ случая подтвердил, что каждый экземпляр с максимум 12 задачами и максимальной плотностью $5/6$ имеет решение. ^[6]^[7]

Периодичность и сложность

Если решение существует, его можно считать периодическим с периодом, не превышающим произведение времени повторения. Однако не всегда возможно найти повторяющийся график субэкспоненциальной длины. ^[2]

При компактном входном представлении, которое определяет для каждого отдельного времени повторения количество объектов, имеющих это время повторения, планирование в виде вертушки является NP-сложным . ^[2]

Алгоритмы

Несмотря на NP-трудность задачи планирования «вертушки» для общих входных данных, некоторые типы входных данных можно планировать эффективно. Пример этого происходит для входных данных, где (при перечислении в отсортированном порядке) каждое время повторения равномерно делит следующее, а плотность не превышает единицы. В этом случае проблему можно решить с помощью жадного алгоритма , который планирует задачи в отсортированном порядке, планируя повторение каждой задачи точно в ее время повторения. На каждом этапе этого алгоритма уже назначенные временные интервалы образуют повторяющуюся последовательность с периодом, равным времени повторения последней запланированной задачи. Этот шаблон позволяет жадно планировать каждую последующую задачу, сохраняя один и тот же инвариант. ^[1]

Эту же идею можно использовать для произвольных случаев с плотностью не более 1/2,округляя каждое время повторения до степени двойки , которая меньше или равна ему. Этот процесс округления увеличивает плотность не более чем в два раза, сохраняя ее не более единицы. После округления все плотности кратны друг другу, что позволяет работать жадному алгоритму. Полученное расписание повторяет каждую задачу с округленным временем повторения; поскольку это округленное время не превышает входное время, расписание является действительным. ^[1] Вместо округления до степени двойки, большего порога плотности можно достичь за счет округления до других последовательностей кратных, например чисел вида $x\cdot 2^{i}$ за тщательный выбор коэффициента $x$ , ^[3] или округлив до двух разных геометрических рядов и обобщив идею о том, что задачи с двумя разными временами повторения можно планировать до плотности один. ^[3]^[8]

Приложения

В оригинальной работе по планированию с помощью вертушки оно предлагалось для приложения, в котором одна базовая станция должна взаимодействовать с несколькими спутниками или удаленными датчиками по одному за раз, с различными требованиями к связи. В этом приложении каждый спутник становится задачей в задаче планирования «вертушки», при этом время повторения выбирается так, чтобы обеспечить достаточную полосу пропускания. Полученное расписание используется для назначения временных интервалов каждому спутнику для связи с базовой станцией. ^[1]

Другие применения планирования «вертушки» включают планирование сеансов технического обслуживания для набора объектов (например, замену масла в автомобилях), расположение повторяющихся символов в цепочках печати построчных принтеров , ^[3] компьютерная обработка мультимедийных данных, ^[5] и разрешение конфликтов в беспроводных компьютерных сетях реального времени. ^[9]

Ссылки

^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г Холт, Роберт; Мок, Ал; Розье, Луи; Тульчинский Игорь; Варвел, Дональд (1989), «Вертушка: проблема планирования в реальном времени», Труды двадцать второй ежегодной Гавайской международной конференции по системным наукам, Том II: Программное обеспечение , IEEE Computer Society Press, стр. 693–702, doi : 10.1109/hicss.1989.48075 , S2CID 62617897
^ Jump up to: ^а ^б ^с ^д Холт, Роберт; Розье, Луи; Тульчинский Игорь; Варвел, Дональд (1992), «Планирование вертушки с двумя разными числами», Theoretical Computer Science , 100 (1): 105–135, doi : 10.1016/0304-3975(92)90365-M , MR 1171436 . Ранее было объявлено на MFCS 1989.
^ Jump up to: ^а ^б ^с ^д ^и Чан, МОЙ; Чин, Фрэнсис (1993), «Планировщики для больших классов экземпляров вертушки», Algorithmica , 9 (5): 425–462, doi : 10.1007/BF01187034 , MR 1212158 , S2CID 6069661
^ Фишберн, ПК ; Лагариас, Дж. К. (2002), «Планирование вертушки: достижимые плотности», Algorithmica , 34 (1): 14–38, doi : 10.1007/s00453-002-0938-9 , MR 1912925 , S2CID 25561199
^ Jump up to: ^а ^б ^с Лин, Шун-Шии; Лин, Квей-Джей (1997), «Планировщик-вертушка для трех различных чисел с жесткой границей планирования», Algorithmica , 19 (4): 411–426, doi : 10.1007/PL00009181 , MR 1470043 , S2CID 22001959
^ Дин, Вэй (июнь 2020 г.), «Разветвленный подход к исследованию гарантии максимальной плотности для вертушки для планирования низкоразмерных векторов», Real-Time Systems , 56 (3): 293–314, doi : 10.1007/ s11241-020-09349-w
^ Гонсенец, Лешек ; Смит, Бенджамин; Уайлд, Себастьян (2022), «К гипотезе плотности 5/6 о вертушке планирования», Филлипс, Синтия А .; Спекманн, Беттина (ред.), Труды симпозиума по разработке алгоритмов и экспериментам, ALENEX 2022, Александрия, Вирджиния, США, 9–10 января 2022 г. , Общество промышленной и прикладной математики, стр. 91–103, arXiv : 2111.01784 , дои : 10.1137/1.9781611977042.8
^ Чан, МОЙ; Чин, Фрэнсис (июнь 1992 г.), «Общие планировщики проблемы вертушки на основе сокращения двойных целых чисел», IEEE Transactions on Computers , 41 (6): 755–768, doi : 10.1109/12.144627
^ Ву, Жан-Льен К.; Шин, Хау-Юн; Ву, И-Сянь (июнь 2005 г.), «Вихревая схема планирования пакетов для широкополосных беспроводных сетей», Журнал Китайского инженерного института , 28 (4): 701–711, doi : 10.1080/02533839.2005.9671037 , S2CID 62761108

Внешние ссылки

Планирование вертушки (1989) , Дуглас Б. Уэст, Университет Иллинойса

[hmrtv-1] Jump up to: ^а ^б ^с ^д ^и ^ж ^г Холт, Роберт; Мок, Ал; Розье, Луи; Тульчинский Игорь; Варвел, Дональд (1989), «Вертушка: проблема планирования в реальном времени», Труды двадцать второй ежегодной Гавайской международной конференции по системным наукам, Том II: Программное обеспечение , IEEE Computer Society Press, стр. 693–702, doi : 10.1109/hicss.1989.48075 , S2CID 62617897

[hrtv-2] Jump up to: ^а ^б ^с ^д Холт, Роберт; Розье, Луи; Тульчинский Игорь; Варвел, Дональд (1992), «Планирование вертушки с двумя разными числами», Theoretical Computer Science , 100 (1): 105–135, doi : 10.1016/0304-3975(92)90365-M , MR 1171436 . Ранее было объявлено на MFCS 1989.

[cc-3] Jump up to: ^а ^б ^с ^д ^и Чан, МОЙ; Чин, Фрэнсис (1993), «Планировщики для больших классов экземпляров вертушки», Algorithmica , 9 (5): 425–462, doi : 10.1007/BF01187034 , MR 1212158 , S2CID 6069661

[fl-4] Фишберн, ПК ; Лагариас, Дж. К. (2002), «Планирование вертушки: достижимые плотности», Algorithmica , 34 (1): 14–38, doi : 10.1007/s00453-002-0938-9 , MR 1912925 , S2CID 25561199

[ll-5] Jump up to: ^а ^б ^с Лин, Шун-Шии; Лин, Квей-Джей (1997), «Планировщик-вертушка для трех различных чисел с жесткой границей планирования», Algorithmica , 19 (4): 411–426, doi : 10.1007/PL00009181 , MR 1470043 , S2CID 22001959

[ding-6] Дин, Вэй (июнь 2020 г.), «Разветвленный подход к исследованию гарантии максимальной плотности для вертушки для планирования низкоразмерных векторов», Real-Time Systems , 56 (3): 293–314, doi : 10.1007/ s11241-020-09349-w

[gsw-7] Гонсенец, Лешек ; Смит, Бенджамин; Уайлд, Себастьян (2022), «К гипотезе плотности 5/6 о вертушке планирования», Филлипс, Синтия А .; Спекманн, Беттина (ред.), Труды симпозиума по разработке алгоритмов и экспериментам, ALENEX 2022, Александрия, Вирджиния, США, 9–10 января 2022 г. , Общество промышленной и прикладной математики, стр. 91–103, arXiv : 2111.01784 , дои : 10.1137/1.9781611977042.8

[cc2-8] Чан, МОЙ; Чин, Фрэнсис (июнь 1992 г.), «Общие планировщики проблемы вертушки на основе сокращения двойных целых чисел», IEEE Transactions on Computers , 41 (6): 755–768, doi : 10.1109/12.144627

[wsw-9] Ву, Жан-Льен К.; Шин, Хау-Юн; Ву, И-Сянь (июнь 2005 г.), «Вихревая схема планирования пакетов для широкополосных беспроводных сетей», Журнал Китайского инженерного института , 28 (4): 701–711, doi : 10.1080/02533839.2005.9671037 , S2CID 62761108

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]