劉岳鐳,馮祖仁,任曉棟

(西安交通大學(xué)機(jī)械制造系統(tǒng)工程國家重點(diǎn)實(shí)驗(yàn)室,710049,西安)

?

具有惡化效應(yīng)的雙代理單機(jī)最優(yōu)調(diào)度算法

劉岳鐳,馮祖仁,任曉棟

(西安交通大學(xué)機(jī)械制造系統(tǒng)工程國家重點(diǎn)實(shí)驗(yàn)室,710049,西安)

針對(duì)單機(jī)床加工環(huán)境中待加工任務(wù)具有惡化效應(yīng)且來自2個(gè)具有不同需求的代理時(shí),無法快速求解出滿足要求且成本最低的最優(yōu)加工序列的情況,提出了可在特定約束條件下的具有惡化效應(yīng)的雙代理單機(jī)最優(yōu)調(diào)度算法。首先提出優(yōu)化目標(biāo)為:保證一個(gè)代理的任務(wù)均不延遲完工的前提下,使得另一個(gè)代理的總加權(quán)完成時(shí)間或總加權(quán)折扣完成時(shí)間最小;其次指出該優(yōu)化問題具有NP難度,并給出其在一般及特殊情況下最優(yōu)解的結(jié)構(gòu)性質(zhì);此后對(duì)于特定約束條件下的情形,提出多項(xiàng)式時(shí)間優(yōu)化算法。該算法中首先將2個(gè)代理的任務(wù)分別按照所證明的最優(yōu)策略排序,然后再按照使得2個(gè)代理能得到最小總加權(quán)完成時(shí)間和給定約束關(guān)系的算法將2個(gè)序列合并在一起,并證明得出的序列即為所求調(diào)度問題的最優(yōu)解。實(shí)驗(yàn)結(jié)果表明,該算法作為確定性算法,計(jì)算時(shí)間與最優(yōu)解平均誤差率大于0.3%的模擬退火算法相似,遠(yuǎn)遠(yuǎn)低于可求解出最優(yōu)解的分支定界算法。

調(diào)度問題;單機(jī);雙代理;惡化效應(yīng)

不同于經(jīng)典調(diào)度問題,在現(xiàn)實(shí)生產(chǎn)環(huán)境中,經(jīng)常會(huì)遇到待加工任務(wù)來自不同的代理,且任務(wù)的加工時(shí)間具有惡化效應(yīng)的情況。在這種復(fù)雜情況下,如何同時(shí)面對(duì)不同代理的不同需求,依然獲得任務(wù)加工調(diào)度的最優(yōu)解,成為了研究的難點(diǎn)。

1988年,Gutpa提出了一種任務(wù)的加工時(shí)間是它們開始(等待)時(shí)間的單調(diào)遞增函數(shù)的調(diào)度問題模型,首次提出了任務(wù)加工中的惡化效應(yīng)[1]。出乎意料的是,這一模型并未得到廣泛關(guān)注,直到十多年后才有學(xué)者對(duì)任務(wù)加工時(shí)間具有惡化效應(yīng)的不同模型的調(diào)度問題進(jìn)行了詳細(xì)的描述[2-3]。文獻(xiàn)[4]針對(duì)最大完工時(shí)間、總加權(quán)完成時(shí)間等優(yōu)化目標(biāo)的單機(jī)線性惡化調(diào)度問題給出了多項(xiàng)式時(shí)間算法;文獻(xiàn)[5]在引入釋放時(shí)間的基礎(chǔ)上,對(duì)特殊約束下的惡化調(diào)度問題給出了最優(yōu)算法。

在此前的調(diào)度問題中,大部分待加工任務(wù)均來自同一代理,然而實(shí)際生產(chǎn)活動(dòng)中,這一假設(shè)可能在某些情況下無效,即需要加工的任務(wù)可能來自于多個(gè)代理。涉及多個(gè)代理的調(diào)度問題在近年來成為了一個(gè)新興的研究課題。大量研究者證明了多種調(diào)度問題在單機(jī)模型下具有NP難度:多代理的優(yōu)化目標(biāo)同時(shí)為最小化總加權(quán)延遲完工任務(wù)數(shù)或最小化任務(wù)最大完成時(shí)間[6];保證一個(gè)代理最大提前完工時(shí)間不超過給定值的前提下最小化另一個(gè)代理的最大提前完成時(shí)間或加權(quán)提前完成時(shí)間和[7];最小化一個(gè)代理的加權(quán)最大完成時(shí)間與另一個(gè)代理的加權(quán)完成時(shí)間和的總和[8]等。

直到2010年以后,才有學(xué)者將惡化效應(yīng)引入到雙代理問題中來,并取得了一系列研究成果:文獻(xiàn)[9]針對(duì)一個(gè)代理最大延遲完成時(shí)間小于給定上界、另一個(gè)代理加權(quán)延遲完工任務(wù)數(shù)總和最小的調(diào)度問題,提出了分支定界算法和禁忌搜索算法求解最優(yōu)和近優(yōu)解;文獻(xiàn)[10]討論一個(gè)代理的最大完工時(shí)間不超過一個(gè)給定上界的約束下,另一個(gè)代理的總完工時(shí)間最小的調(diào)度問題,給出多項(xiàng)式時(shí)間最優(yōu)算法;文獻(xiàn)[11-12]分別針對(duì)特殊情況下,優(yōu)化目標(biāo)關(guān)于推遲/提前完工時(shí)間的一些調(diào)度問題模型,同樣給出了多項(xiàng)式時(shí)間算法。本文針對(duì)單機(jī)環(huán)境下具有惡化效應(yīng)的雙代理調(diào)度問題下的一個(gè)模型的多個(gè)加權(quán)優(yōu)化目標(biāo)進(jìn)行了研究,指出了問題的NP難度,討論最優(yōu)解結(jié)構(gòu)特征,并以此為依據(jù)給出特定情形下的多項(xiàng)式時(shí)間算法。

1 惡化效應(yīng)的單機(jī)雙代理問題模型

本文主要討論單機(jī)環(huán)境下的以下調(diào)度問題:假設(shè)存在n個(gè)任務(wù),J={J1,J2,…,Jn},來自2個(gè)不同的代理X={A,B},n=nA+nB,其中nA和nB分別為來自代理A和B的任務(wù)數(shù)量。對(duì)于每項(xiàng)任務(wù)Jj都有初始(基礎(chǔ))加工時(shí)間pj,權(quán)值wj,交貨日期dj以及代理參數(shù)Ij,且有當(dāng)Jj∈A時(shí)Ij=0,Jj∈B時(shí)Ij=1。考慮到惡化效應(yīng),若任務(wù)Jj在t時(shí)刻開始加工,則實(shí)際加工時(shí)間為pj(a+bt),其中a>0為給定參數(shù),b≥0為給定惡化參數(shù)。對(duì)于一個(gè)調(diào)度解S,任務(wù)Jj的完工時(shí)間表示為Cj(S),任務(wù)Jj的延遲交貨時(shí)間表示為Tj(S)=max{0,Cj(S)-dj},當(dāng)Tj(S)>0時(shí)有Uj(S)=1,否則Uj(S)=0。

使用α|β|γ三參數(shù)表示法[13],本文討論的問題模型可以分別被寫作

(1)

(2)

式中:α域中的1表示單機(jī)床加工環(huán)境;γ域中的符號(hào)∶表示其之前的部分為優(yōu)化目標(biāo),而其之后的部分為需保證的約束條件。

2 優(yōu)化調(diào)度算法

2.1 代理B不延遲且代理A總加權(quán)完成時(shí)間最小的調(diào)度問題

證明 采用數(shù)學(xué)歸納法證明

引理1得證。

引理3 該問題最優(yōu)解的任務(wù)加工序列中,代理B的任務(wù)按照其交貨日期dj非降序排列。

引理4 假設(shè)有調(diào)度解S,其中有2個(gè)相鄰任務(wù)Ji和Jj,其中Ji先于Jj被加工。現(xiàn)將任務(wù)Ji與Jj的加工次序互換,得到新的調(diào)度解S′,在此基礎(chǔ)上假設(shè)任務(wù)Ji在調(diào)度解S中的開始加工時(shí)間為t。若Ji,Jj∈A且有wjpi(1+bpj)

證明 任務(wù)Ji在調(diào)度解S和調(diào)度解S′中的加工完成時(shí)間分別為

Ci(S)=pi(a+bt)+t

(3)

Cj(S)=pj(a+bCi(S))+Ci(S)=

pi(a+bt)+pj(a+bt)+pipjb(a+bt)+t

(4)

Cj(S′)=pj(a+bt)+t

(5)

Ci(S′)=pi(a+bCj(S′))+Cj(S′)=

pi(a+bt)+pj(a+bt)+pipjb(a+bt)+t

(6)

由此可得

wiCi(S)+wjCj(S)-(wiCi(S′)+wjCj(S′))=

wjpi(1+bpj)(a+bt)-wipj(1+bpi)(a+bt)

(7)

則當(dāng)wjpi(1+bpj)

引理5 若該調(diào)度問題中,代理A的任務(wù)具有權(quán)值與初始加工時(shí)間的反相關(guān)約束,則最優(yōu)解中代理A的任務(wù)按照加權(quán)最短加工時(shí)間優(yōu)先規(guī)則(WSPT)排序(即按照pj/wj非降序排列)。

(8)

對(duì)于代理B不延遲且代理A總加權(quán)完成時(shí)間性最小的調(diào)度問題,在來自代理A的任務(wù)遵循權(quán)值與初始加工時(shí)間的反相關(guān)約束這一特殊情況下,由引理2、3和5,可給出如下算法。

算法1 代理B不延遲且代理A總加權(quán)完成時(shí)間最小問題的最優(yōu)解算法步驟如下。

步驟4 如果i≥1或j≥1,則跳轉(zhuǎn)至步驟2,否則輸出加工序列S=(J[1],J[2],…,J[nA+nB]),算法結(jié)束。

定理1 如果代理A的任務(wù)遵循權(quán)值與初始加工時(shí)間反相關(guān)的約束,則對(duì)于該調(diào)度問題,算法1可求解出最優(yōu)解,且其計(jì)算的時(shí)間復(fù)雜度為O(nAlognA+nBlognB)。

證明 算法1中,代理B和代理A的任務(wù)分別依照引理3和引理5的方式排序,再根據(jù)引理2將2個(gè)排序組合為可行解。引理2、引理3以及引理5的證明保障了算法1可以求得最優(yōu)解。步驟1中關(guān)于代理A和代理B的任務(wù)排序,其時(shí)間復(fù)雜度分別為O(nAlognA)和O(nBlognB),故整個(gè)算法的時(shí)間復(fù)雜度為O(nAlognA+nBlognB)。證畢。

2.2 代理B不延遲且代理A總加權(quán)折扣完成時(shí)間最小的調(diào)度問題

引理6 若該調(diào)度問題中,代理A的任務(wù)具有權(quán)值與初始加工時(shí)間的反相關(guān)約束,則存在一個(gè)最優(yōu)解,其中代理A的任務(wù)按照加權(quán)折扣最短加工時(shí)間優(yōu)先規(guī)則(WDSPT)排序(即按照(1-exp(-rpj))/wjexp(-rpj)非降序排列)。

(9)

由此可得

(10)

這與S為最優(yōu)解的假設(shè)相矛盾,故最優(yōu)解中代理A的任務(wù)按照WDSPT規(guī)則排序,證畢。

對(duì)于代理B不延遲且代理A總加權(quán)折扣完成時(shí)間最小的調(diào)度問題,在來自代理A的任務(wù)遵循權(quán)值與初始加工時(shí)間的反相關(guān)約束這一特殊情況下,由引理2、3和6,可給出如下算法。

算法2 代理B不延遲且代理A總加權(quán)折扣完成時(shí)間最小問題的最優(yōu)解算法步驟如下。

步驟4 如果i≥1或j≥1,則跳轉(zhuǎn)至步驟2,否則輸出加工序列S=(J[1],J[2],…,J[nA+nB]),算法結(jié)束。

定理2 如果代理A的任務(wù)遵循權(quán)值與初始加工時(shí)間反相關(guān)的約束,則對(duì)于該調(diào)度問題,算法2可求解出最優(yōu)解,且其計(jì)算的時(shí)間復(fù)雜度為O(nAlognA+nBlognB)。

證明 同定理1。

3 仿真結(jié)果

為了評(píng)估本文給出的具有惡化效應(yīng)的雙代理單機(jī)最優(yōu)調(diào)度算法,將其與文獻(xiàn)[15]中給出的分支定界算法(B&B)以及模擬退火算法(SA)進(jìn)行對(duì)比。采用的算例與文獻(xiàn)[15]生成方式類似,假設(shè)2個(gè)代理的任務(wù)數(shù)量相同,分別對(duì)應(yīng)n=10,12,14,a=1,以及不同的惡化參數(shù)b=0.002,0.005,在保證代理A的任務(wù)遵循權(quán)值與初始加工時(shí)間反相關(guān)的約束的前提下,生成了多組各30個(gè)的隨機(jī)數(shù)據(jù)。由于本文的2個(gè)算法類似,故只針對(duì)算法1進(jìn)行仿真對(duì)比。此外,為了與SA算法進(jìn)行比較,定義如下最優(yōu)解平均誤差率

(11)

式中:SSA表示SA算法得到的近優(yōu)解;T表示最優(yōu)解所對(duì)應(yīng)的代理A的總加權(quán)完成時(shí)間。

表1為3種算法計(jì)算時(shí)間的對(duì)比。從表1中可以看出:B&B算法的CPU時(shí)間遠(yuǎn)大于其他2種算法,這是因?yàn)闉榱饲蠼獬鰡栴}的最優(yōu)解,B&B算法需要經(jīng)歷大量節(jié)點(diǎn)的計(jì)算,并且B&B算法的CPU時(shí)間會(huì)隨著問題規(guī)模的小幅增大而劇烈增加;另一方面,SA算法所需計(jì)算時(shí)間與本文的確定性最優(yōu)解算法1類似,但卻只能在接近的計(jì)算時(shí)間內(nèi)獲得問題的近優(yōu)解,且SA算法的解質(zhì)量的平均誤差率也會(huì)隨著問題規(guī)模增加而變大(當(dāng)n=10時(shí),rerror≈0.3% ;當(dāng)n=14時(shí),rerror≈1.4% )。

表1 3種算法的計(jì)算時(shí)間對(duì)比

4 結(jié) 論

本文針對(duì)單機(jī)床環(huán)境下任務(wù)來自2個(gè)不同的代理且任務(wù)的加工時(shí)間具有與任務(wù)開始加工時(shí)間相關(guān)的惡化效應(yīng)的調(diào)度問題,在優(yōu)化目標(biāo)為保證一個(gè)代理的任務(wù)均不延遲完工的前提下使得另一個(gè)代理的總加權(quán)完成時(shí)間或總加權(quán)折扣完成時(shí)間最小,指出問題具有NP難度,并提出在特定約束條件下的時(shí)間復(fù)雜度為O(nAlognA+nBlognB)的最優(yōu)解算法(算法1和算法2)。仿真結(jié)果表明:采用本文提出的最優(yōu)解算法可以高效地求解出滿足要求且成本最低的最優(yōu)加工序列。

雖然本文算法1和算法2僅能對(duì)這類問題的特例加以求解,但它們也為一般性問題最優(yōu)解或近優(yōu)解算法提供了有效的啟發(fā)信息。更一般性的問題仍然有待進(jìn)一步研究與解決。

[1] GUPTA J N D, GUPTA S K. Single facility scheduling with nonlinear processing times [J]. Computers & Industrial Engineering, 1988, 14(4): 387-393.

[2] ALIDAEE B, WOMER N K. Scheduling with time dependent processing times: review and extensions [J]. Journal of the Operational Research Society, 1999, 50(7): 711-720.

[3] CHENG T C E, DING Q, LIN B M T. A concise survey of scheduling with time-dependent processing times [J]. European Journal of Operational Research, 2004, 152(1): 1-13.

[4] 趙傳立, 張慶靈, 唐恒永. 具有線性惡化加工時(shí)間的調(diào)度問題 [J]. 自動(dòng)化學(xué)報(bào), 2003, 29(4): 531-535. ZHAO Chuanli,ZHANG Qingling,TANG Hengyong. Scheduling problems under linear deterioration [J]. Acta Automatica Sinica, 2003, 29(4): 531-535.

[5] 趙曉麗, 唐立新. 帶有線性惡化工件和釋放時(shí)間的2個(gè)代理單機(jī)調(diào)度問題 [J]. 自動(dòng)化學(xué)報(bào), 2015, 41(1): 104-112. ZHAO Xiaoli, TANG Lixin. Two-agent scheduling with linear-deteriorating jobs and release dates on a single machine [J]. Acta Automatica Sinica, 2015, 41(1): 104-112.

[6] CHENG T C E, NG C T, YUAN J J. Multi-agent scheduling on a single machine with max-form criteria [J]. European Journal of Operational Research, 2008, 188(2): 603-609.

[7] MOR B, MOSHEIOV G. Scheduling problems with two competing agents to minimize minmax and minsum earliness measures [J]. European Journal of Operational Research, 2010, 206(3): 540-546.

[8] NONG Q Q, CHENG T C E, NG C T. Two-agent scheduling to minimize the total cost [J]. European Journal of Operational Research, 2011, 215(1): 39-44.

[9] WU Wen-Hsiang, XU Jianyou, WU Wen-Hung, et al. A tabu method for a two-agent single-machine scheduling with deterioration jobs [J]. Computers & Operations Re-search, 2013, 40(8): 2116-2127.

[10]劉鵬, 周曉曄, 榮楠. 帶有學(xué)習(xí)效應(yīng)和惡化工件的雙代理調(diào)度問題 [J]. 系統(tǒng)工程學(xué)報(bào), 2012, 27(6): 841-846. LIU Peng, ZHOU Xiaoye, RONG Nan. Two-agent scheduling with a learning effect and deteriorating jobs [J]. Journal of System engineering, 2012, 27(6): 841-846.

[11]LIU Peng, YI Na, ZHOU Xiaoye. Two-agent singlemachine scheduling problems under increasing linear deterioration [J]. Applied Mathematical Modelling, 2011, 35(5): 2290-2296.

[12]YIN Yunqiang, WU Chin-Chia, CHENG Shuenn-Ren. Scheduling problems with two agents and a linear non-increasing deterioration to minimize earliness penalties [J]. Information Sciences, 2012, 189(7): 282-292.

[13]AGNETIS A, BILLAUT J, GAWIEJNOWICZ S, et al. Multiagent scheduling-models and algorithms [M]. Berlin, Germany: Springer, 2014: 6-16.

[14]YIN Y, CHENG T C E, WAN L, et al. Two-agent sing-le-machine scheduling with deteriorating jobs [J]. Computers & Industrial Engineering, 2015, 81: 177-185.

[15]JIN Y C. Minimizing total weighted completion time under makespan constraint for two-agent scheduleing with job-dependent aging effects [J]. Computers & Industrial Engineering, 2015, 83: 237-243.

[本刊相關(guān)文獻(xiàn)鏈接]

董春云,蔡遠(yuǎn)利.高超聲速再入飛行器軌跡優(yōu)化算法評(píng)估策略.2016,50(4):28-34.[doi:10.7652/xjtuxb201604005]

李國梁,張合新,周鑫,等.狀態(tài)反饋事件觸發(fā)控制系統(tǒng)的分析與設(shè)計(jì).2016,50(5):146-150.[doi:10.7652/xjtuxb201605 022]

李小虎,柳松瑋,施虎,等.基于兩自由度H∞控制策略的泵控液壓系統(tǒng)研究.2016,50(4):7-13.[doi:10.7652/xjtuxb 201604002]

楊航,劉凌,閻治安,等.雙閉環(huán)Buck變換器系統(tǒng)模糊PID控制.2016,50(4):35-40.[doi:10.7652/xjtuxb201604006]

宋汝君,單小彪,李晉哲,等.壓電俘能器渦激振動(dòng)俘能的建模與實(shí)驗(yàn)研究.2016,50(2):55-60.[doi:10.7652/xjtuxb 201602010]

嚴(yán)惠云,張浩磊,劉小民.一種仿生魚體自主游動(dòng)的水動(dòng)力學(xué)特性分析.2016,50(2):138-144.[doi:10.7652/xjtuxb2016 02023]

黃博,苑壽同,薛嘉倫.碳纖維氣流擾動(dòng)展纖器展纖過程仿真與實(shí)驗(yàn).2015,49(12):19-25.[doi:10.7652/xjtuxb201512 004]

陳江城,張小棟,李睿,等.利用表面肌電信號(hào)的下肢動(dòng)態(tài)關(guān)節(jié)力矩預(yù)測(cè)模型.2015,49(12):26-33.[doi:10.7652/xjtuxb201512005]

連峰,王婷婷,韓崇昭.多個(gè)不可分辨目標(biāo)群的聯(lián)合檢測(cè)與估計(jì)誤差界.2015,49(11):89-95.[doi:10.7652/xjtuxb2015 11015]

張蕾,張愛民,景軍鋒,等.靜止無功補(bǔ)償器與發(fā)電機(jī)勵(lì)磁系統(tǒng)的自適應(yīng)魯棒協(xié)調(diào)控制策略2015,49(11):96-101.[doi:10.7652/xjtuxb201511016]

王海龍,王剛,陳曦,等.仿海蟹機(jī)器人游泳足水動(dòng)力學(xué)分析與實(shí)驗(yàn)研究.2015,49(8):75-83.[doi:10.7652/xjtuxb 201508013]

劉冠初,熊靜琪,喬林,等.四足機(jī)器人自由步態(tài)規(guī)劃建模與算法實(shí)現(xiàn).2015,49(6):84-89.[doi:10.7652/xjtuxb201506 014]

劉冠初,熊靜琪,喬林,等.四足機(jī)器人自由步態(tài)規(guī)劃建模與算法實(shí)現(xiàn).2015,49(6):84-89.[doi:10.7652/xjtuxb201506 014]

董恩清,劉偉,宋洋.采用三角形節(jié)點(diǎn)塊處理無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位中節(jié)點(diǎn)翻轉(zhuǎn)歧義的迭代方法.2015,49(4):84-90.[doi:10.7652/xjtuxb201504014]

卜祥偉,吳曉燕,張蕊,等.雙曲正弦非線性跟蹤微分器設(shè)計(jì).2015,49(1):107-111.[doi:10.7652/xjtuxb201501018]

(編輯 劉楊)

An Optimal Scheduling Algorithm on Single-Machine with Two-Agent and Deteriorating Jobs

LIU Yuelei,FENG Zuren,REN Xiaodong

(State Key Laboratory for Manufacturing Systems Engineering, Xi’an Jiaotong University, Xi’an 710049, China)

Two-agent single-machine scheduling problems with a deterioration job of which the actual processing time is defined as a function of its starting time are investigated. Optimization algorithms of polynomial time under some certain constraints are proposed. The optimization target of the problem is formulated as to minimize the total weighted completion time or total weighted discounted completion time of one agent while ensuring that all the jobs on the other agents are not delayed. This optimization problem is proved NP-hard and the structural properties of its optimal solutions under general and special conditions are illustrated. Optimization algorithms of polynomial time for solving these scheduling problems are proposed under some constraints. First, the jobs from two agents are respectively sequenced according to their optimal structural properties. Then, they are combined following the strategies that ensure the optimization target of two agents. Simulation results and comparisons with scheduling results of the simulated annealing (SA) and the branch-and-bound algorithms show that the CPU-times of the proposed algorithms are similar with the SA’s that has an error rate greater than 0.3% with the optimal solutions, and much smaller than that of the branch-and-bound algorithm.

scheduling; single-machine; two agents; deteriorating jobs

2015-11-09。 作者簡介:劉岳鐳(1986—),男,博士生;馮祖仁(通信作者),男,教授,博士生導(dǎo)師。 基金項(xiàng)目:國家自然科學(xué)基金資助項(xiàng)目(61203350)。

時(shí)間:2016-04-03

10.7652/xjtuxb201606002

TP29

A

0253-987X(2016)06-0009-06

網(wǎng)絡(luò)出版地址:http:∥www.cnki.net/kcms/detail/61.1069.T.20160403.1822.006.html