资源定时投放的单机排序问题

陈 蕾，张 安，陈 永，陈光亭

(杭州电子科技大学理学院，浙江 杭州 310018)

资源定时投放的单机排序问题

陈 蕾，张 安，陈 永，陈光亭

(杭州电子科技大学理学院，浙江 杭州 310018)

资源需求；单机排序；NP-难；最坏情况界

0 引 言

排序问题是经典的组合优化问题之一，单机排序是被广泛研究的一类排序模型，尤其是以极小化工件总完工时间为目标的单机排序.文献[1]证明了无资源需求的情形下通过最短时间最先(Shortest Processing Time first，SPT)算法在多项式时间内求得最优解.文献[2]最早提出了有资源需求的排序问题，文献[3]证明了只有两个资源投放时刻的情形是NP-难的.此外，文献[3]还对该情形设计了完全多项式时间近似方案(Fully Polynomial Time Algorithm Scheme，FPTAS).一类与有资源需求排序相关的问题是带禁用区间的排序问题，文献[4-5]研究发现，单台机情形下，尽管没有资源需求，但禁用区间的存在也能直接影响机器的持续加工能力.本文通过多项式时间归约法，证明即使工件的加工时间与资源需求成比例的情形也是NP-难的，并通过分析得出SPT算法的最坏情况紧界.

1 问题定义及复杂性证明

接着，证明П1与П2的解之间存在一一对应关系.

1)若划分问题有解，则排序问题一定有解.

2)若排序问题有解，则划分问题一定有解.

两组患者生活质量 VAS 评分（±s），治疗前、后情绪状态和心理状态评分（见表3）及两组患者术后生活质量VAS评分对比（见表4）显示比较差异P＜0.05。

综上，定理1得证.

2 SPT算法及其最坏情况分析

本节分析pj=aj情形SPT算法最坏情况界，结论对pj与aj成比例也成立……