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

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

(杭州电子科技大学理学院，浙江 杭州 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成比例也成立.

SPT算法是从0时刻开始按p1≤p2≤…≤pn的次序依次选择加工工件，若当前剩余资源不能满足当前工件的资源需求，则将当前工件及剩余所有工件从t时刻开始依次加工.

图1 SPT排序σ与最优排序σ*

引理1 若δ=0，则SPT排序已是最优.

证明 若δ=0，则与无资源需求问题的SPT排序一致，故此排序是最优的[1].证毕.

(1)

若δ≤δ*，则f(σ)δ*.

(2)

又SPT不是最优排序，故P与X中工件不完全相同，即至少存在一个Jj∈PX，则有

fP(σ*)≥δ-δ*.

(3)

(4)

设工件集J={J1,J2,J3,J4}，其中p1=1，p2=N，p3=N，p4=N.0时刻资源投放量为b1=N，t=N时刻资源投放量为b2=2N+1，则SPT排序与最优排序如图2所示.

图2 SPT排序与最优排序实例

3 结束语

[1]BRUCKERP.SchedulingAlgorithms[M].NewYork:Springer-Verlag, 2001:72-83.

[2]CARLIERJ,KANAHGR.Schedulingsubjecttononrenewable-resourceconstraints[J].OperationsResearchLetters, 1982,1(2):52-55.

[3]KIST.Approximabilityoftotalweightedcompletiontimewithresourceconsumingjobs[J].OperationsResearchLetters, 2015,43(6):595-598.

[4]LEECY,LIMANSD.Singlemachineflow-timeschedulingwithscheduledmaintenance[J].ActaInformatica, 1992,29(4):375-382.

[5]SCHMIDTG.Schedulingwithlimitedmachineavailability[J].EuropeanJournalofOperationalResearch, 2000,121(1):1-15.

Scheduling on a Single Machine with Timing Released Resource

CHEN Lei, ZHANG An, CHEN Yong, CHEN Guangting

(SchoolofScience,HangzhouDianziUniversity,HangzhouZhejiang310018,China)

resource demand; single machine scheduling; NP-hard; worst-case analysis

10.13954/j.cnki.hdu.2017.02.018

2016-07-06

国家自然科学基金资助项目(11571252，11401149)

陈蕾(1991-)，女，黑龙江鸡西人，硕士研究生，组合优化.通信作者：陈光亭教授，E-mail：gtchen@hdu.edu.cn.

O224

A

1001-9146(2017)02-0085-04