中譯：切割排程方法

Partitioned Scheduling方法將任務集合$\mathcal{T}$事先切割為多個不相交集合(Disjoint Sets) $\mathcal{T}^1, \mathcal{T}^2, \cdots, \mathcal{T}^{N^c}$，並將其分別分配到$core_1, core_2, \cdots, core_{N^c}$；被分配到核心$core_k$上的工作僅能在該核心上執行，且不允許工作遷移(Task Migration)。通常在實作上，此方法會為每個處理器核心配置一個區域的等待佇列(Local Queue)，當工作到達系統時會直接加入到所屬核心的佇列中，再由每個核心各自為其所分配到的工作進行排程。常見的方法包含了Partitioned EDF (P-EDF)\cite{Baker2005}與Partitioned RM (P-RM)\cite{Oh1998}，它們分別使用EDF與RM為分配到每個核心的工作進行排程。此方面研究的重點在於如何適切地將工作切割分配到不同核心，Carpenter等學者\cite{Carpenter2004}已證明了此問題為$\mathcal{NP}$-Hard，除非允許工作遷移否則不存在最佳解。目前大部份的工作切割方法都是以非最佳化的方式(例如Best-Fit、First-Fit、Next-Fit與Worst-Fit等切割策略)，將工作指派到不同的核心上。

• SOMETAG