A NOTE ON HARDNESS OF MULTIPROCESSOR SCHEDULING WITH SCHEDULING SOLUTION SPACE TREE

Abstract

We study the computational complexity 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 showing the
exhaustive solution space of the problem by defining the Scheduling Solution Space Tree
(SSST) data structure. The properties of the SSST are formally defined and characterized
through our analytical results. We develop a unique technique to show the problem
NP using the SSST and the Weighted Scheduling Solution Space Tree (WSSST) data
structures. We design the first non-deterministic polynomial-time algorithm named Magic
Scheduling (MS) for the problem based on the reduction framework. We also define a
new variant of multiprocessor scheduling by including the user as an additional input
parameter. We formally establish the complexity class of the variant by the reduction
principle. Finally, we conclude the article by exploring several interesting open problems
for future research investigation.