陳 蕾，張 安，陳 永，陳光亭

(杭州電子科技大學(xué)理學(xué)院，浙江 杭州 310018)

資源定時投放的單機(jī)排序問題

陳 蕾，張 安，陳 永，陳光亭

(杭州電子科技大學(xué)理學(xué)院，浙江 杭州 310018)

資源需求；單機(jī)排序；NP-難；最壞情況界

0 引 言

排序問題是經(jīng)典的組合優(yōu)化問題之一，單機(jī)排序是被廣泛研究的一類排序模型，尤其是以極小化工件總完工時間為目標(biāo)的單機(jī)排序.文獻(xiàn)[1]證明了無資源需求的情形下通過最短時間最先(Shortest Processing Time first，SPT)算法在多項式時間內(nèi)求得最優(yōu)解.文獻(xiàn)[2]最早提出了有資源需求的排序問題，文獻(xiàn)[3]證明了只有兩個資源投放時刻的情形是NP-難的.此外，文獻(xiàn)[3]還對該情形設(shè)計了完全多項式時間近似方案(Fully Polynomial Time Algorithm Scheme，F(xiàn)PTAS).一類與有資源需求排序相關(guān)的問題是帶禁用區(qū)間的排序問題，文獻(xiàn)[4-5]研究發(fā)現(xiàn)，單臺機(jī)情形下，盡管沒有資源需求，但禁用區(qū)間的存在也能直接影響機(jī)器的持續(xù)加工能力.本文通過多項式時間歸約法，證明即使工件的加工時間與資源需求成比例的情形也是NP-難的，并通過分析得出SPT算法的最壞情況緊界.

1 問題定義及復(fù)雜性證明

接著，證明П1與П2的解之間存在一一對應(yīng)關(guān)系.

1)若劃分問題有解，則排序問題一定有解.

2)若排序問題有解，則劃分問題一定有解.

兩組患者生活質(zhì)量 VAS 評分（±s），治療前、后情緒狀態(tài)和心理狀態(tài)評分（見表3）及兩組患者術(shù)后生活質(zhì)量VAS評分對比（見表4）顯示比較差異P＜0.05。

綜上，定理1得證.

2 SPT算法及其最壞情況分析

本節(jié)分析pj=aj情形SPT算法最壞情況界，結(jié)論對pj與aj成比例也成立.

SPT算法是從0時刻開始按p1≤p2≤…≤pn的次序依次選擇加工工件，若當(dāng)前剩余資源不能滿足當(dāng)前工件的資源需求，則將當(dāng)前工件及剩余所有工件從t時刻開始依次加工.

圖1 SPT排序σ與最優(yōu)排序σ*

引理1 若δ=0，則SPT排序已是最優(yōu).

證明 若δ=0，則與無資源需求問題的SPT排序一致，故此排序是最優(yōu)的[1].證畢.

(1)

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

(2)

又SPT不是最優(yōu)排序，故P與X中工件不完全相同，即至少存在一個Jj∈PX，則有

fP(σ*)≥δ-δ*.

(3)

(4)

設(shè)工件集J={J1,J2,J3,J4}，其中p1=1，p2=N，p3=N，p4=N.0時刻資源投放量為b1=N，t=N時刻資源投放量為b2=2N+1，則SPT排序與最優(yōu)排序如圖2所示.

圖2 SPT排序與最優(yōu)排序?qū)嵗?/p>

3 結(jié)束語

[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

國家自然科學(xué)基金資助項目(11571252，11401149)

陳蕾(1991-)，女，黑龍江雞西人，碩士研究生，組合優(yōu)化.通信作者：陳光亭教授，E-mail：gtchen@hdu.edu.cn.

O224

A

1001-9146(2017)02-0085-04