Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › Рецензирование
Multiprocessor Scheduling Problem with Release and Delivery Times. / Grigoreva, Natalia .
Proceedings of the 2020 Federated Conference on Computer Science and Information Systems, FedCSIS 2020. ред. / Maria Ganzha; Leszek Maciaszek; Leszek Maciaszek; Marcin Paprzycki. 2020. стр. 263-269 9223012 (Proceedings of the 2020 Federated Conference on Computer Science and Information Systems, FedCSIS 2020).Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › Рецензирование
}
TY - GEN
T1 - Multiprocessor Scheduling Problem with Release and Delivery Times
AU - Grigoreva, Natalia
PY - 2020/9
Y1 - 2020/9
N2 - The multiprocessor scheduling problem is defined as follows: set of jobs have to be executed on parallel identical processors. For each job we know release time, processing time and delivery time. At most one job can be performed on every processor at a time, but all jobs may be simultaneously delivered. Preemption on processors is not allowed. The goal is to minimize the time, by which all tasks are delivered. Scheduling tasks among parallel processors is a NP-hard problem in the strong sense. The best known approximation algorithm is Jackson's algorithm, which generates the list schedule by selecting the ready job with the largest delivery time. This algorithm generates no delay schedules. We define an IIT (inserted idle time) schedule as a feasible schedule in which a processor can be idle at a time when it could begin performing a ready job. The paper proposes the approximation inserted idle time algorithm for the multiprocessor scheduling. We proved that deviation of this algorithm from the optimum is smaller then twice the largest processing time. 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: set of jobs have to be executed on parallel identical processors. For each job we know release time, processing time and delivery time. At most one job can be performed on every processor at a time, but all jobs may be simultaneously delivered. Preemption on processors is not allowed. The goal is to minimize the time, by which all tasks are delivered. Scheduling tasks among parallel processors is a NP-hard problem in the strong sense. The best known approximation algorithm is Jackson's algorithm, which generates the list schedule by selecting the ready job with the largest delivery time. This algorithm generates no delay schedules. We define an IIT (inserted idle time) schedule as a feasible schedule in which a processor can be idle at a time when it could begin performing a ready job. The paper proposes the approximation inserted idle time algorithm for the multiprocessor scheduling. We proved that deviation of this algorithm from the optimum is smaller then twice the largest processing time. To illustrate the efficiency of our approach we compared two algorithms on randomly generated sets of jobs.
UR - https://annals-csis.org/Volume_21/
UR - http://www.scopus.com/inward/record.url?scp=85095766937&partnerID=8YFLogxK
UR - https://www.mendeley.com/catalogue/4f3eaf46-71eb-3ad2-a9ed-37284450283f/
U2 - 10.15439/2020F33
DO - 10.15439/2020F33
M3 - Conference contribution
SN - 978-83-955416-7-4
T3 - Proceedings of the 2020 Federated Conference on Computer Science and Information Systems, FedCSIS 2020
SP - 263
EP - 269
BT - Proceedings of the 2020 Federated Conference on Computer Science and Information Systems, FedCSIS 2020
A2 - Ganzha, Maria
A2 - Maciaszek, Leszek
A2 - Maciaszek, Leszek
A2 - Paprzycki, Marcin
ER -
ID: 70921162