Browsing by Subject "NP-completeness"

Now showing 1 - 1 of 1

Access status: Open Access ,
A note on hardness of multiprocessor scheduling with scheduling solution space tree
(Wydawnictwa AGH, 2023) Dwibedy, Debasis; Mohanty, Rakesh
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 $\cal {NP}$-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 $\cal {NP}$-complete. We conclude the article by exploring several non-trivial research challenges for future research investigations.