Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
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.
Translated title of the contribution | Приближенные несписочные алгоритмы для многопроцессорных систем |
---|---|
Original language | English |
Title of host publication | Mathematical Optimization Theory and Operations Research: Recent Trends |
Subtitle of host publication | 21st International Conference, MOTOR 2022, Petrozavodsk, Russia, July 2–6, 2022, Revised Selected Papers |
Publisher | Springer Nature |
Pages | 76-88 |
ISBN (Electronic) | 9783031162244 |
ISBN (Print) | 9783031162237 |
DOIs | |
State | Published - 2022 |
Event | Mathematical Optimization Theory and Operations Research - Петрозаводск, Russian Federation Duration: 2 Jul 2022 → 6 Jul 2022 http://motor2022.krc.karelia.ru/en/section/1 |
Name | Communications in Computer and Information Science |
---|---|
Publisher | Springer Nature |
Volume | 1661 |
ISSN (Print) | 1865-0929 |
Conference | Mathematical Optimization Theory and Operations Research |
---|---|
Abbreviated title | MOTOR 2022 |
Country/Territory | Russian Federation |
City | Петрозаводск |
Period | 2/07/22 → 6/07/22 |
Internet address |
ID: 106984312