拟阵下的单位时间任务调度问题

问题描述

单位时间任务的最优调度问题的原型是操作系统在单核CPU上的调度，其需要的输入信息如下。问题的目标是找到\(S\)的一个调度(排序)，可以使得超过截止时间后的总惩罚值最小。

1) \(n\)个单位时间(耗费时间为1)任务的集合\(S=\{a_1,a_2…\} \)；

2) \(n\)个整数的期望的截止时间\(\{d_1,d_2…\} \)，显然\(1 \leq d_i \leq n\)；

3) \(n\)个非负的惩罚值\(\{w_1,w_2…\} \)；

在讨论问题前，预先给出更进一步的定义与相关性质如下：

1) 提前任务：任务在某个调度的截止时间前完成，称该任务为该调度的提前任务；

2) 延迟任务：任务在某个调度的截止时间后完成，称该任务为该调度的延迟任务；

3) 提前优先调度：任意调度可在总惩罚值不变时，把所有提前任务排在延迟任务前；

证明：设提前任务\(a_i\)排在延迟任务\(a_j\)后，交换二者次序，二者的提前性延迟性都不变。

4) 规范形式调度：将提前优先调度中的提前任务按截止时间递增排序，总惩罚值不变；

证明：对任意两个\(k\)与\(k+1\)时间完成的提前任务\(a_i\)与\(a_j\)，若\(d_i > d_j\)，交换二者次序二者仍提前，不影响总惩罚值。故对所有非严格的按截止时间排序的序列，都可通过交换得到。

独立任务集与拟阵

\(S\)的独立任务集是存在调度使所有任务都没有延迟的\(S\)的子集，其有两种等价表示：

0) 任务集\(A\)是独立的；

1) 令\(N_t(A)\)为截止时间小于等于\(t\)(非负整数)的任务数，对任意\(t\)有\(N_t(A)\leq t\)；

2) 将任务按截止时间递增排序所得到的调度无延迟任务；

证明：考虑(1)的逆否命题“若存在\(t\)使得\(N_t(A)>t\)，则任何调度都存在延迟任务(\(A\)不是独立的)”，若有大于\(t\)个任务在\(t\)之前截止，显然无论如何排列这些任务都必然会有任务是延迟的，故(0)=>(1)。考虑(1)=>(2)的逆否命题“若将任务按截止时间递增排序后存在延迟任务，则存在\(t\)有\(N_t(A)>t\)”。那么对排序后的任务序列中的延迟任务(排序为\(j\))，其截止时间为小于等于\(j-1\)的非负整数，由于任务序列按截止时间排序，故\(N_{j-1}\geq j>j-1\)。所以(1)=>(2)。最后由于(2)=>(0)是显然的，故三个命题形成推导闭环，三者两两等价。

设\(S\)为任务集，\(L\)为\(\{ A | A\subseteq S ~且~ A为独立任务集 \}\)。则\((S,L)\)为拟阵。

证明：遗传性易得，只需证交换性。设\(S\)有\(n\)个元素，\(|B|>|A|\)为两个独立任务集，\(k=max\{t|N_t(B)\leq N_t(A) \}\)。由于\(N_n(B)=|B| > N_n(A)=|A|\)。因此对\(j>k\)有\(N_j(B)>N_j(A)\)。所以\(B\)比\(A\)包含更多\(k+1\)截止时间的任务。再令\(a_i\)为\(B-A\)中\(k+1\)截止时间的任务，\(A’=A\bigcup\{a_i\}\)。当\(0 \leq t \leq k\)，\(N_t(A’)=N_t(A)\leq t\)。当\(t >k\)，\(N_t(A’) \leq N_t(B)\leq t\)。综上\(N_t(A’)\leq t\)，为独立任务集条件(1)，交换性证毕。

将惩罚值设为拟阵的加权函数，然后利用拟阵通用贪心算法求得序列\(A\)，令\(A\)按截止时间递增排序，再按任意次序追加\(S-A\)中的全部元素即得其中一种最优调度。这是因为\(A\)中的任务可作为最优提前优先调度\(X\)的提前任务部分，将提前部分按截止时间递增排序其仍为最优调度。对于\(X\)的延迟任务部分，无论如何排序其总惩罚值都是相等的。

基于拟阵的具体实现

拟阵的通用贪心算法流程：

1) 把集合\(S\)按权重排为降序序列；

2) 初始化\(A\)为空集；

3) 遍历\(S\)序列元素(计为\(x\))，若\(A\bigcup x \in L\)，则\(A = A\bigcup x\)；

其中流程(3)需要判断\(A\bigcup x\)是否为独立集(独立任务集)，此时利用独立任务集的充要条件(2)即可实现。分析该算法的时间复杂度，每次insert/independ的最坏代价为输入规模\(O(n)\)，因为要遍历任务故总代价为\(O(n^2)\)。