Multi-core processor scheduling with respect to the mutual influence of jobs

В статье рассматривается задача планирования работ на многоядерном процессоре с учетом их замедления при совместном выполнении. Предложена постановка задачи и модель частично целочисленного линейного программирования, доказана NP-трудность задачи при числе ядер, ограниченном константой. Результаты планировщика Intel TBB и жадного алгоритма сравниваются с результатами, полученными в соответствии с предложенной моделью с помощью пакета CPLEX. Проведенный эксперимент показал преимущества предложенного подхода по времени завершения всех работ. The paper deals with the problem of multi-core processor scheduling with respect to the mutual influence of jobs during their joint execution. A problem formulation and a model of mixed integer linear programming are proposed, the problem is shown to be NP-hard with the number of cores bounded by a constant. The results of the Intel TBB scheduler and the greedy algorithm are compared with the results obtained in accordance with the proposed model using the CPLEX package. The conducted experiment showed the advantages of the proposed approach in terms of the completion time of all jobs.