В теории планирования аналогичные постановки задач могут быть найдены в области планирования с контролируемым временем обработки. Модели и методы планирования для случая, когда прерывания допустимы, рассматриваются в [7]. Однако в настоящей работе мы рассматриваем постановку задачи без прерываний. Поскольку работы замедляют друг друга в основном из-за конкуренции за возобновляемые ресурсы (пропускная способность шины данных, кеш), мы ссылаемся на [8] и [9] для обзоров задач с возобновляемыми ресурсами, где распределение ресурсов может меняться с течением времени. Случай дискретных ресурсов рассматривается в [9], а непрерывные ресурсы рассматриваются в [8]. Последняя статья содержит постановку задачи, аналогичную рассматриваемой в настоящей статье, однако в [8] предполагается, что количество ресурсов, выделяемых для каждой работы, ограничено, но непрерывно и определяется планировщиком в каждый момент времени. В нашем случае скорость выполнения работ полностью определяется набором совместно запланированных работ на других ядрах (или машинах в традиционной терминологии планирования). Для такого случая в [10] предложен жадный алгоритм, в котором замедление работ рассчитывается на основе информации об использовании ими шины данных.
В недавней работе [11] авторы сосредоточились на назначении общих непрерывных ресурсов ядрам, в то время как назначение работ ядрам и их порядок фиксированы. В этом основные отличия от рассматриваемой в данной статье задачи. Авторы [11] показывают, что даже для работ единичной длительности поиск оптимального решения является NP-трудным, если число ядер является частью входных данных. Однако существует алгоритм с полиномиальным временем для любого постоянного числа ядер и работ единичной длительности.
В настоящей статье предложена математическая постановка задачи размещения работ по ядрам процессора и доказана ее NP-трудность при числе ядер, ограниченном константой. Также предлагается модель частично целочисленного линейного программирования (ЧЦЛП), использующая концепцию точек событий (см., например, [12]). Проведено сравнение результатов решений модели, найденных решателем CPLEX, с результатами, показанными библиотекой Intel TBB. Также приведены результаты сравнения значений целевой функции, полученных жадным алгоритмом, с оптимальными значениями целевой функции, полученными пакетом CPLEX при использовании алгоритма расчета скоростей выполнения работ, предложенного в [10].
