具有惡化效應的雙代理單機最優調度算法

劉岳鐳,馮祖仁,任曉棟

(西安交通大學機械制造系統工程國家重點實驗室,710049,西安)

?

具有惡化效應的雙代理單機最優調度算法

劉岳鐳,馮祖仁,任曉棟

(西安交通大學機械制造系統工程國家重點實驗室,710049,西安)

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

調度問題;單機;雙代理;惡化效應

不同于經典調度問題,在現實生產環境中,經常會遇到待加工任務來自不同的代理,且任務的加工時間具有惡化效應的情況。在這種復雜情況下,如何同時面對不同代理的不同需求,依然獲得任務加工調度的最優解,成為了研究的難點。

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

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

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

1 惡化效應的單機雙代理問題模型

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

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

(1)

(2)

式中:α域中的1表示單機床加工環境;γ域中的符號∶表示其之前的部分為優化目標,而其之后的部分為需保證的約束條件。

2 優化調度算法

2.1 代理B不延遲且代理A總加權完成時間最小的調度問題

證明 采用數學歸納法證明

引理1得證。

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

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

證明 任務Ji在調度解S和調度解S′中的加工完成時間分別為

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)

則當wjpi(1+bpj)

引理5 若該調度問題中,代理A的任務具有權值與初始加工時間的反相關約束,則最優解中代理A的任務按照加權最短加工時間優先規則(WSPT)排序(即按照pj/wj非降序排列)。

(8)

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

算法1 代理B不延遲且代理A總加權完成時間最小問題的最優解算法步驟如下。

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

定理1 如果代理A的任務遵循權值與初始加工時間反相關的約束,則對于該調度問題,算法1可求解出最優解,且其計算的時間復雜度為O(nAlognA+nBlognB)。

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

2.2 代理B不延遲且代理A總加權折扣完成時間最小的調度問題

引理6 若該調度問題中,代理A的任務具有權值與初始加工時間的反相關約束,則存在一個最優解,其中代理A的任務按照加權折扣最短加工時間優先規則(WDSPT)排序(即按照(1-exp(-rpj))/wjexp(-rpj)非降序排列)。

(9)

由此可得

(10)

這與S為最優解的假設相矛盾,故最優解中代理A的任務按照WDSPT規則排序,證畢。

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

算法2 代理B不延遲且代理A總加權折扣完成時間最小問題的最優解算法步驟如下。

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

定理2 如果代理A的任務遵循權值與初始加工時間反相關的約束,則對于該調度問題,算法2可求解出最優解,且其計算的時間復雜度為O(nAlognA+nBlognB)。

證明 同定理1。

3 仿真結果

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

(11)

式中:SSA表示SA算法得到的近優解;T表示最優解所對應的代理A的總加權完成時間。

表1為3種算法計算時間的對比。從表1中可以看出:B&B算法的CPU時間遠大于其他2種算法,這是因為為了求解出問題的最優解,B&B算法需要經歷大量節點的計算,并且B&B算法的CPU時間會隨著問題規模的小幅增大而劇烈增加;另一方面,SA算法所需計算時間與本文的確定性最優解算法1類似,但卻只能在接近的計算時間內獲得問題的近優解,且SA算法的解質量的平均誤差率也會隨著問題規模增加而變大(當n=10時,rerror≈0.3% ;當n=14時,rerror≈1.4% )。

表1 3種算法的計算時間對比

4 結 論

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

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

[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] 趙傳立, 張慶靈, 唐恒永. 具有線性惡化加工時間的調度問題 [J]. 自動化學報, 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] 趙曉麗, 唐立新. 帶有線性惡化工件和釋放時間的2個代理單機調度問題 [J]. 自動化學報, 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]劉鵬, 周曉曄, 榮楠. 帶有學習效應和惡化工件的雙代理調度問題 [J]. 系統工程學報, 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.

[本刊相關文獻鏈接]

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

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

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

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

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

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

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

陳江城,張小棟,李睿,等.利用表面肌電信號的下肢動態關節力矩預測模型.2015,49(12):26-33.[doi:10.7652/xjtuxb201512005]

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

張蕾,張愛民,景軍鋒,等.靜止無功補償器與發電機勵磁系統的自適應魯棒協調控制策略2015,49(11):96-101.[doi:10.7652/xjtuxb201511016]

王海龍,王剛,陳曦,等.仿海蟹機器人游泳足水動力學分析與實驗研究.2015,49(8):75-83.[doi:10.7652/xjtuxb 201508013]

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

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

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

卜祥偉,吳曉燕,張蕊,等.雙曲正弦非線性跟蹤微分器設計.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—),男,博士生;馮祖仁(通信作者),男,教授,博士生導師。 基金項目:國家自然科學基金資助項目(61203350)。

時間:2016-04-03

10.7652/xjtuxb201606002

TP29

A

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

網絡出版地址:http:∥www.cnki.net/kcms/detail/61.1069.T.20160403.1822.006.html