DOI

The multiprocessor scheduling problem is defined as follows: jobs have to be executed on several parallel identical processors. Each job has a positive processing time. At most one job can be processed at a time, but all jobs may be simultaneously delivered. We study the case where precedence constrains exist between jobs and preemption on processors is not allowed. The objective is to minimize the time, by which all jobs are done. The problem is NP-hard in the strong sense. The best-known approximation algorithm is the critical path algorithm, which generates the list no delay schedules. We define an IIT (inserted idle time) schedule as a feasible schedule, in which a processor is kept idle at a time when it could begin processing a job. The paper proposes a 2-1/m approximation inserted idle time algorithm for the multiprocessor scheduling. To illustrate the efficiency of our approach, we compared two algorithms on randomly generated sets of jobs.

Переведенное названиеПриближенные несписочные алгоритмы для многопроцессорных систем
Язык оригиналаанглийский
Название основной публикацииMathematical Optimization Theory and Operations Research: Recent Trends
Подзаголовок основной публикации21st International Conference, MOTOR 2022, Petrozavodsk, Russia, July 2–6, 2022, Revised Selected Papers
ИздательSpringer Nature
Страницы76-88
ISBN (электронное издание)9783031162244
ISBN (печатное издание)9783031162237
DOI
СостояниеОпубликовано - 2022
СобытиеMathematical Optimization Theory and Operations Research - Петрозаводск, Российская Федерация
Продолжительность: 2 июл 20226 июл 2022
http://motor2022.krc.karelia.ru/en/section/1

Серия публикаций

НазваниеCommunications in Computer and Information Science
ИздательSpringer Nature
Том1661
ISSN (печатное издание)1865-0929

конференция

конференцияMathematical Optimization Theory and Operations Research
Сокращенное названиеMOTOR 2022
Страна/TерриторияРоссийская Федерация
ГородПетрозаводск
Период2/07/226/07/22
Сайт в сети Internet

    Предметные области Scopus

  • Компьютерные науки (все)
  • Математика (все)

ID: 106984312