Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
Approximation Non-list Scheduling Algorithms for Multiprocessor System. / Grigoreva, Natalia .
Mathematical Optimization Theory and Operations Research: Recent Trends: 21st International Conference, MOTOR 2022, Petrozavodsk, Russia, July 2–6, 2022, Revised Selected Papers. Springer Nature, 2022. p. 76-88 (Communications in Computer and Information Science; Vol. 1661).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
}
TY - GEN
T1 - Approximation Non-list Scheduling Algorithms for Multiprocessor System
AU - Grigoreva, Natalia
N1 - Grigoreva, N. (2022). Approximation Non-list Scheduling Algorithms for Multiprocessor System. In: Kochetov, Y., Eremeev, A., Khamisov, O., Rettieva, A. (eds) Mathematical Optimization Theory and Operations Research: Recent Trends. MOTOR 2022. Communications in Computer and Information Science, vol 1661. Springer, Cham. https://doi.org/10.1007/978-3-031-16224-4_5
PY - 2022
Y1 - 2022
N2 - 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.
AB - 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.
KW - Approximation algorithm
KW - Critical path
KW - Inserted idle time
KW - Makespan
KW - Parallel identical processors
UR - http://www.scopus.com/inward/record.url?scp=85140475596&partnerID=8YFLogxK
UR - https://www.mendeley.com/catalogue/eebca45d-fe6b-3054-8367-82dd945255c4/
U2 - 10.1007/978-3-031-16224-4_5
DO - 10.1007/978-3-031-16224-4_5
M3 - Conference contribution
SN - 9783031162237
T3 - Communications in Computer and Information Science
SP - 76
EP - 88
BT - Mathematical Optimization Theory and Operations Research: Recent Trends
PB - Springer Nature
Y2 - 2 July 2022 through 6 July 2022
ER -
ID: 106984312