Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › Рецензирование
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 |
Событие | 21st International Conference on Mathematical Optimization Theory and Operations Research , MOTOR 2022 - Petrozavodsk, Российская Федерация Продолжительность: 2 июл 2022 → 6 июл 2022 http://motor2022.krc.karelia.ru/en/section/1 |
Название | Communications in Computer and Information Science |
---|---|
Издатель | Springer Nature |
Том | 1661 |
ISSN (печатное издание) | 1865-0929 |
конференция | 21st International Conference on Mathematical Optimization Theory and Operations Research , MOTOR 2022 |
---|---|
Сокращенное название | MOTOR 2022 |
Страна/Tерритория | Российская Федерация |
Город | Petrozavodsk |
Период | 2/07/22 → 6/07/22 |
Сайт в сети Internet |
ID: 106984312