论文标题
使用调度解决方案树的多处理器调度的硬度的注释
A Note on Hardness of Multiprocessor Scheduling with Scheduling Solution Space Tree
论文作者
论文摘要
我们研究了一组具有MakePAN最小化目标的相同并行处理器上的独立作业列表的非首次调度问题问题的计算复杂性。我们通过定义\ textIt {调度解决方案太空树（SSST）}数据结构来探索探索组合结构的组合结构。 \ textit {ssst}的属性通过我们的分析结果正式定义和表征。我们开发了一种独特的技术来使用SSST和\ textIt {加权调度解决方案太空树（WSSST）}数据结构来显示问题$ \ MATHCAL {NP} $。我们根据减少框架为问题设计了第一个名为\ textit {魔术{魔术调度（MS）}的非确定性多项式时间算法。我们还通过将用户作为附加输入参数（将用户包含在内）来定义多处理器调度的新变体。我们通过还原原理正式建立变体的复杂性类别。最后，我们通过探索几个有趣的开放问题来进行未来的研究调查来结束这篇文章。
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 \textit{Scheduling Solution Space Tree (SSST)} data structure. The properties of the \textit{SSST} are formally defined and characterized through our analytical results. We develop a unique technique to show the problem $\mathcal{NP}$ using the SSST and the \textit{Weighted Scheduling Solution Space Tree (WSSST)} data structures. We design the first non-deterministic polynomial-time algorithm named \textit{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.
