資源定時(shí)投放的單機(jī)排序問(wèn)題

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

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

資源定時(shí)投放的單機(jī)排序問(wèn)題

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

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

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

0 引 言

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

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

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

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

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

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

綜上，定理1得證.

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

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

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

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

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

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

(1)

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

(2)

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

fP(σ*)≥δ-δ*.

(3)

(4)

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

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

3 結(jié)束語(yǔ)

[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

國(guó)家自然科學(xué)基金資助項(xiàng)目(11571252，11401149)

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

O224

A

1001-9146(2017)02-0085-04