- Tytuł:
- A note on hardness of multiprocessor scheduling with scheduling solution space tree
- Autorzy:
-
Dwibedy, Debasis
Mohanty, Rakesh - Powiązania:
- https://bibliotekanauki.pl/articles/27312879.pdf
- Data publikacji:
- 2023
- Wydawca:
- Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
- Tematy:
-
combinatorial structures
computational complexity
hardness
makespan
multiprocessor scheduling
multiuser
NP-completeness
nondeterministic algorithms
reduction
scheduling solution space tree - Opis:
- We study the hardness of the non-preemptive scheduling problem of a list of independent jobs on a set of identical parallel processors with a makespan minimization objective. We make a maiden attempt to explore the combinatorial structure of the problem by introducing a scheduling solution space tree (SSST) as a novel data structure. We formally define and characterize the properties of SSST through our analytical results. We show that the multiprocessor scheduling problem is N P-complete with an alternative technique using SSST and weighted scheduling solution space tree (WSSST) data structures. We propose a non-deterministic polynomial-time algorithm called magic scheduling (MS) based on the reduction framework. We also define a new variant of multiprocessor scheduling by including the user as an additional input parameter, which we called the multiuser multiprocessor scheduling problem (MUMPSP). We also show that MUMPSP is N P-complete. We conclude the article by exploring several non-trivial research challenges for future research investigations.
- Źródło:
-
Computer Science; 2023, 24 (1); 53--74
1508-2806
2300-7036 - Pojawia się w:
- Computer Science
- Dostawca treści:
- Biblioteka Nauki
Artykuł