工期約束下加工型產(chǎn)品準(zhǔn)確率串歸約算法研究

羅智勇，汪 鵬，尤 波，蘇 潔

?

工期約束下加工型產(chǎn)品準(zhǔn)確率串歸約算法研究

羅智勇1,2，汪 鵬1，尤 波2，蘇 潔1

(1. 哈爾濱理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 哈爾濱 150080；2. 哈爾濱理工大學(xué)機(jī)械動(dòng)力工程學(xué)院 哈爾濱 150080)

完工時(shí)間和準(zhǔn)確率是生產(chǎn)調(diào)度的兩個(gè)重要屬性，然而單屬性優(yōu)化算法只能完成單個(gè)屬性的優(yōu)化，無法動(dòng)態(tài)平衡這些屬性。針對(duì)此問題，提出了基于有向無環(huán)圖的串歸約優(yōu)化算法。算法通過約束每個(gè)任務(wù)的活動(dòng)區(qū)間并采用逆向迭代進(jìn)行歸約，達(dá)到每層選擇最優(yōu)服務(wù)的目的，從而實(shí)現(xiàn)了這兩個(gè)屬性的優(yōu)化。實(shí)驗(yàn)表明，該算法可準(zhǔn)確地得到一條完工時(shí)間和準(zhǔn)確率相互平衡的優(yōu)化路徑，但其優(yōu)化效率受限于完工截止期和任務(wù)數(shù)。最后，研究結(jié)論對(duì)生產(chǎn)調(diào)度多屬性的優(yōu)化提供了一定的參考。

準(zhǔn)確率優(yōu)化; 截止期; 時(shí)間一致性; 工作流調(diào)度

現(xiàn)代業(yè)務(wù)的工作流技術(shù)是在網(wǎng)絡(luò)流的基礎(chǔ)上以服務(wù)為基本元素進(jìn)行架構(gòu)，使多個(gè)服務(wù)相互協(xié)作來完成整個(gè)業(yè)務(wù)。工作流系統(tǒng)將業(yè)務(wù)流程抽象化，劃分為諸多工序，并結(jié)合工序中的服務(wù)屬性，確定最佳完工路徑。然而，目前企業(yè)的項(xiàng)目流程，往往因?yàn)橐粋€(gè)或者幾個(gè)工序出現(xiàn)問題而影響整體，如追求效率而忽略了服務(wù)質(zhì)量或者追求服務(wù)質(zhì)量而拖延了完工時(shí)間，使得整個(gè)項(xiàng)目的完工時(shí)間和完工質(zhì)量失衡。為此，應(yīng)該使用更合理的方法，在業(yè)務(wù)流程規(guī)定的截止期內(nèi)，選擇一條能夠有效提升復(fù)雜項(xiàng)目準(zhǔn)確率的路徑，達(dá)到既能充分利用資源，又能使效率和準(zhǔn)確率實(shí)現(xiàn)平衡的目的[1]。

本文提出了一種加工型產(chǎn)品工作流在限定完工時(shí)間內(nèi)，保證工序完工質(zhì)量最高的算法，即實(shí)現(xiàn)了完工路徑質(zhì)量的串歸約優(yōu)化。

1 相關(guān)工作

工作流模型包含任務(wù)和服務(wù)兩大要點(diǎn)，服務(wù)在工作流模型中承載著時(shí)間、費(fèi)用和服務(wù)質(zhì)量等屬性，合理搭配服務(wù)之間的聯(lián)系對(duì)優(yōu)化任務(wù)的順利進(jìn)行起著關(guān)鍵性作用[2-3]。隨著工作流結(jié)構(gòu)的不斷拓展，工作流的優(yōu)化不再以時(shí)間為根本，而是對(duì)其完工時(shí)間和完工質(zhì)量有了更高的要求。文獻(xiàn)[4]結(jié)合時(shí)間啟發(fā)函數(shù)和遺傳算法的優(yōu)點(diǎn)，提出一種混合式算法，通過實(shí)驗(yàn)證明了該策略的優(yōu)化效果；文獻(xiàn)[5]針對(duì)資源配置可能存在的不確定性弊端，提出了一種截止驅(qū)動(dòng)調(diào)度算法，有效地降低了成本并保證了完工時(shí)間；文獻(xiàn)[6]在混合式工作流的基礎(chǔ)上提出了類似VM的并行任務(wù)處理方案，有效地降低了執(zhí)行成本；文獻(xiàn)[7]利用任務(wù)在進(jìn)程中的靈活性并結(jié)合工作流的健壯性，提出了一種任務(wù)動(dòng)態(tài)重排的方法，能夠有效降低前驅(qū)任務(wù)對(duì)后續(xù)任務(wù)的影響，以達(dá)到資源合理分配的目標(biāo)。

基于在約束時(shí)間下降低成本的問題，國內(nèi)也開展了相應(yīng)的研究。文獻(xiàn)[8-9]都是在混合式復(fù)雜工作流上約束時(shí)間進(jìn)而優(yōu)化成本，分別利用逆向分層策略和串歸約策略對(duì)每個(gè)活動(dòng)結(jié)點(diǎn)劃分活動(dòng)區(qū)間，以局部選擇最優(yōu)服務(wù)來達(dá)到全局的優(yōu)化。文獻(xiàn)[10]采用優(yōu)先級(jí)因子技術(shù)來優(yōu)化復(fù)雜工作流的時(shí)間和成本的算法，并對(duì)不同的算法進(jìn)行了比較分析。文獻(xiàn)[11]對(duì)粒子進(jìn)行初始化并進(jìn)行了篩選，在此基礎(chǔ)上提出了基于粒子群算法的優(yōu)化調(diào)度策略，同時(shí)減少搜索時(shí)間。可見，現(xiàn)代工作流技術(shù)大部分追求的是時(shí)間和成本的平衡，而在約束時(shí)間下有效優(yōu)化準(zhǔn)確率也是一個(gè)研究熱點(diǎn)。

2 問題描述

2.1 工作流模型的相關(guān)定義

工作流建模是對(duì)業(yè)務(wù)過程的一個(gè)合理安排，能夠有效地將服務(wù)安排到對(duì)應(yīng)任務(wù)的服務(wù)集合中[12]，并將加工型產(chǎn)品生產(chǎn)工序組成一個(gè)有向無環(huán)圖。

定義1 任務(wù)池。是指在給定業(yè)務(wù)的流程中，將所有任務(wù)構(gòu)成一個(gè)集合，若用表示，則=(1,2,…,p,…,p)。

定義2 服務(wù)池。指對(duì)于任務(wù)集合中的任意一個(gè)任務(wù)p，所對(duì)應(yīng)的所有服務(wù)構(gòu)成的集合。用S=(1,2,…,s,…,s)表示。

定義3 服務(wù)池的秩。指對(duì)于任務(wù)集合中的任意一個(gè)任務(wù)，其服務(wù)集合S中服務(wù)的數(shù)目，用r表示。

定義4 工作流圖。即是網(wǎng)格環(huán)境下的有向無環(huán)圖DAG與任務(wù)池、服務(wù)池相結(jié)合用來清楚描述業(yè)務(wù)流程的圖，表示為={s,}，∈，0<≤r。其中，s表示任務(wù)用服務(wù)集合S中的第個(gè)服務(wù)完成；為有向邊，表示每層的服務(wù)之間存在著順序關(guān)系。工作流圖中，沒有前驅(qū)的結(jié)點(diǎn)為開始結(jié)點(diǎn)，記為結(jié)點(diǎn)Start，用p表示虛擬的任務(wù)，S表示虛擬的服務(wù)集合，并指向Start結(jié)點(diǎn)；沒有后繼的結(jié)點(diǎn)為完成結(jié)點(diǎn)End，用p表示虛擬的任務(wù)，用S表示虛擬的服務(wù)集合，并指向End結(jié)點(diǎn)。

定義5 服務(wù)屬性。是指工作流圖中服務(wù)s帶有的屬性參數(shù)，表示為pt=(t,a)，t表示使用服務(wù)池S中的第個(gè)服務(wù)完成任務(wù)的時(shí)間，a表示達(dá)到的準(zhǔn)確率。

2.2 約束定義

定義6 完工時(shí)間。指產(chǎn)品的生產(chǎn)從開始到結(jié)束耗費(fèi)的時(shí)間，記為。

定義7 完工準(zhǔn)確率。指產(chǎn)品的生產(chǎn)從開始到結(jié)束達(dá)到的準(zhǔn)確率，記為。

定義8 截止期。指產(chǎn)品的生產(chǎn)約束限定時(shí)間，記為。

對(duì)于建立的工作模型，此時(shí)需要有規(guī)定的約束策略，對(duì)流程的形式化為：

即表示一條能夠完成加工型產(chǎn)品路徑的準(zhǔn)確率。當(dāng)執(zhí)行一個(gè)任務(wù)時(shí)，只能選擇一個(gè)服務(wù)來完成該任務(wù)，即：

完成加工型產(chǎn)品所用的時(shí)間必須低于或等于截止時(shí)間，即；

式中，l是一個(gè)變量，即：

在截止期下，以式(1)為啟發(fā)目標(biāo)函數(shù)，在式(2)～式(4)的約束條件下，求得能夠完成加工型產(chǎn)品路徑的準(zhǔn)確率，此時(shí)采用不同的算法策略求得對(duì)應(yīng)路徑的準(zhǔn)確率。

3 傳統(tǒng)單向目標(biāo)算法

一個(gè)加工型產(chǎn)品的生產(chǎn)工序，承載著完工時(shí)間和完工準(zhǔn)確率的屬性，傳統(tǒng)單向目標(biāo)的算法策略是指在生產(chǎn)過程中，僅僅保證了完工時(shí)間最小或者僅保證了完工準(zhǔn)確率最大。

3.1 最小時(shí)間的單向目標(biāo)優(yōu)化算法(TMG)

選擇每個(gè)工序完成時(shí)間最小的服務(wù)組成工作序列，即：

式中，min為限定條件，即時(shí)間最小化；在限定條件min下可求得完工準(zhǔn)確率。

3.2 最大準(zhǔn)確率的單向目標(biāo)優(yōu)化算法(AMG)

選擇每個(gè)工序完成準(zhǔn)確率最大的服務(wù)組成工作序列，即：

式中，max為限定條件，即達(dá)到完工準(zhǔn)確率最大化；在限定條件max下可求得完工時(shí)間。

4 基于串歸約的時(shí)間-準(zhǔn)確率優(yōu)化策略

4.1 相關(guān)定義

4.2 算法描述

串歸約優(yōu)化算法是在每層任務(wù)的活動(dòng)區(qū)間內(nèi)選擇合適的服務(wù)，實(shí)現(xiàn)復(fù)雜產(chǎn)品的完工時(shí)間和準(zhǔn)確率平衡的目標(biāo)。由于在活動(dòng)區(qū)間內(nèi)的服務(wù)存在不能充分利用時(shí)間的問題，因此會(huì)產(chǎn)生一些時(shí)間碎片。串歸約算法充分利用在截止期范圍內(nèi)的時(shí)間，把時(shí)間碎片集中起來，產(chǎn)生一個(gè)局部最優(yōu)解。本文以任務(wù)的自由度為基礎(chǔ)，對(duì)于任務(wù)集合中的每個(gè)任務(wù)，都有一個(gè)WF=[ST,EN]，采用動(dòng)態(tài)規(guī)劃的方式，以后繼活動(dòng)不同時(shí)間點(diǎn)開始時(shí)達(dá)到的局部最優(yōu)解求得當(dāng)前活動(dòng)不同時(shí)間點(diǎn)開始時(shí)達(dá)到的最優(yōu)解，通過比較完工的準(zhǔn)確率確定最佳路徑。

針對(duì)含有個(gè)任務(wù)的工作流圖，用()表示工作流圖中的第個(gè)任務(wù)在時(shí)間開始時(shí)達(dá)到的最大準(zhǔn)確率，其中∈[ST,EN]。以最后一個(gè)活動(dòng)為起點(diǎn)，迭代求出前驅(qū)活動(dòng)相應(yīng)的值，最后一個(gè)活動(dòng)的由式(8)求得：

對(duì)已經(jīng)求解每個(gè)活動(dòng)自由度的業(yè)務(wù)流程，以活動(dòng)的相關(guān)值(p,t)，求解前驅(qū)活動(dòng)￠對(duì)應(yīng)的(￠,t￠)，該迭代過程由式(9)求得：

通過層層迭代，當(dāng)遍歷到初始任務(wù)時(shí)，最大準(zhǔn)確率的服務(wù)組合即為業(yè)務(wù)流程最佳路徑。

基于串歸約的時(shí)間-準(zhǔn)確率優(yōu)化算法SRO偽代碼如下：

Input：,S

Output：最佳路徑。

Val=.length();

For(int=1;≤;++) {

Figure WFby Formula (7));}

Figure(,) by Formula (8);

For(=-1;>0;--){

Figure(,) by Formula (9)};

if(=1){

Search max((,));}

經(jīng)分析：SRO算法對(duì)應(yīng)的時(shí)間復(fù)雜度為(m)。

5 案例分析

5.1 案例設(shè)計(jì)

組裝工藝的一般過程分為備料、形成坯件、零部件加工、部件組合、總組合和表面涂飾6個(gè)環(huán)節(jié)，存在虛擬的開始任務(wù)和結(jié)束任務(wù)，分別為申請(qǐng)和竣工，則該業(yè)務(wù)流程可抽象化表示1,2,3,4,5,6,s,p。此時(shí)每個(gè)環(huán)節(jié)對(duì)應(yīng)一個(gè)服務(wù)池S，對(duì)應(yīng)的服務(wù)帶有一定的屬性參數(shù)，數(shù)據(jù)如表1所示。

表1 服務(wù)時(shí)間及準(zhǔn)確率

5.2 算法分析

由以上的任務(wù)和服務(wù)列表，建立如圖1所示的工作流圖。

基于圖1的工作流圖，規(guī)定本業(yè)務(wù)流程的截止期=21，采用本文的傳統(tǒng)單向目標(biāo)算法和基于串歸約的時(shí)間-準(zhǔn)確率優(yōu)化算法進(jìn)行計(jì)算。

5.2.1 傳統(tǒng)單向目標(biāo)算法策略

1) TMG算法。調(diào)用式(5)求得對(duì)應(yīng)的工作流程為11->21->31->41->51->61，此時(shí)對(duì)應(yīng)的限定條件min=11+21+31+41+51+61=16，則可求得對(duì)應(yīng)工作流程的準(zhǔn)確率=112131415161=0.727;

2) AMG算法。調(diào)用式(6)求得對(duì)應(yīng)的工作流程為13->22->33->42->53->62，此時(shí)對(duì)應(yīng)的限定條件max=132233425362=0.859，則對(duì)應(yīng)工作流程的完工時(shí)間=13+22+33+42+53+62=31。

圖1 工作流圖

5.2.2 SRO算法

結(jié)合業(yè)務(wù)流程的任務(wù)及其對(duì)應(yīng)的服務(wù)屬性，調(diào)用算法SRO可得：任務(wù)1自由度為[0,3]，任務(wù)2自由度為[3,6]，任務(wù)3自由度為[5,8]，任務(wù)4自由度為[7,10]，任務(wù)5自由度為[12,15]，任務(wù)6自由度為[15,18]，并可求出各個(gè)任務(wù)在相應(yīng)的任務(wù)自由度內(nèi)，不同時(shí)間開始執(zhí)行取得的最大準(zhǔn)確率，其計(jì)算過程及結(jié)果如表2所示：

表2 計(jì)算結(jié)果

由(1,0)=0.783可知，此時(shí)的完工準(zhǔn)確率最大，則可明確基于串歸約算法的最佳路徑為：任務(wù)1從0時(shí)開始，用對(duì)應(yīng)的13服務(wù)，所用時(shí)間為5；任務(wù)2從5時(shí)開始，用對(duì)應(yīng)的22服務(wù)，所用時(shí)間為3；任務(wù)3從8時(shí)開始，用對(duì)應(yīng)的31服務(wù)，所用時(shí)間為2；任務(wù)4從10時(shí)開始，用對(duì)應(yīng)的41服務(wù)，所用時(shí)間為5；任務(wù)5從15時(shí)開始，用對(duì)應(yīng)的51服務(wù)，所用時(shí)間為3；任務(wù)6從18時(shí)開始，用對(duì)應(yīng)的61服務(wù)，所用時(shí)間為3。

5.3 算法比較

結(jié)合上述不同算法求得的完工結(jié)果，可求出每種算法在不同時(shí)刻達(dá)到的準(zhǔn)確率及所用時(shí)間，如圖2a所示；并能得到不同的完工路徑，如圖2b所示。

a. 不同任務(wù)時(shí)刻的準(zhǔn)確率及所用時(shí)間

b. 不同算法對(duì)應(yīng)路徑

圖2 不同算法的對(duì)比

從圖2a中可知，對(duì)應(yīng)業(yè)務(wù)進(jìn)行到任務(wù)6時(shí)的準(zhǔn)確率即完工準(zhǔn)確率，此時(shí)可看出AMG算法的完工準(zhǔn)確率最大，但由于出現(xiàn)完工時(shí)間高于截止期的情況，因此該策略不能被執(zhí)行。TMG算法和SRO算法的完工時(shí)間滿足約束條件，因此利用完工準(zhǔn)確率10.783、20.727，可計(jì)算SRO算法相對(duì)于TMG算法的優(yōu)化率=7.7%。因此，SRO算法具有一定優(yōu)化調(diào)度優(yōu)勢(shì)。圖2b可知，SRO算法從開始到完成，其服務(wù)選擇為13->22->31->41->51->61。

6 其他參數(shù)對(duì)算法性能的影響

6.1 截止期ψ大小產(chǎn)生的影響

截止期是工作流的最晚完工時(shí)間，隨著截止期的增大，業(yè)務(wù)流程的總體準(zhǔn)確率也會(huì)得到優(yōu)化。本文采用的基于串歸約的時(shí)間-準(zhǔn)確率優(yōu)化算法主要是建立在時(shí)間約束的基礎(chǔ)上，因此通過增大截止期，某些任務(wù)的自由度也會(huì)變大，可以選擇更佳的服務(wù)來執(zhí)行。實(shí)驗(yàn)選擇任務(wù)數(shù)為10和15的業(yè)務(wù)流圖，并以區(qū)間[2,4]的隨機(jī)值作為服務(wù)池大小，每個(gè)任務(wù)具有服務(wù)及其對(duì)應(yīng)的屬性等特性。以min作為每個(gè)業(yè)務(wù)流圖的最小完工時(shí)間，并在此基礎(chǔ)上增加10%、15%、20%、25%、30%作為業(yè)務(wù)流圖的不同截止期，業(yè)務(wù)流圖在不同截止期下達(dá)到的最大完工準(zhǔn)確率如圖3所示：

通過圖3可得出，當(dāng)截止期為min時(shí)，即基于時(shí)間最小化策略。不同的業(yè)務(wù)流程，隨著截止時(shí)間的增大，相對(duì)于以時(shí)間最小化為目標(biāo)的算法，串歸約優(yōu)化算法的準(zhǔn)確率越來越大，算法性能得到了優(yōu)化。因此，在實(shí)際的業(yè)務(wù)過程中，可適當(dāng)用大點(diǎn)截止期，串歸約算法的優(yōu)化作用將會(huì)越來越明顯。

圖3 不同截止期ψ對(duì)算法性能的影響

6.2 任務(wù)的數(shù)目對(duì)性能的影響

工作流中的某條路徑的準(zhǔn)確率是通過該路徑上所有服務(wù)準(zhǔn)確率的乘積而來，隨著任務(wù)數(shù)目的增多，對(duì)整體的完工準(zhǔn)確率及SRO算法的優(yōu)化效果均會(huì)產(chǎn)生不同的影響。實(shí)驗(yàn)選擇集合{5,10,15,20}中的值為任務(wù)數(shù)，并以區(qū)間[2,4]的隨機(jī)值作為服務(wù)池大小，每個(gè)任務(wù)具有服務(wù)及其對(duì)應(yīng)的屬性等特性，生成不同的業(yè)務(wù)流圖。以min作為每個(gè)業(yè)務(wù)流圖的最小完工時(shí)間，并在此基礎(chǔ)上增加20%作為不同流圖的截止期，不同業(yè)務(wù)流圖在不同算法策略下達(dá)到的完工準(zhǔn)確率如圖4所示。

圖4 任務(wù)數(shù)目對(duì)算法性能的影響

從圖4的數(shù)據(jù)可以得出，隨著任務(wù)數(shù)目的增多，每個(gè)環(huán)節(jié)都存在著偏差，總體的完工準(zhǔn)確率會(huì)隨著降低，但串歸約優(yōu)化算法的優(yōu)化效果更加明顯，算法提高率分別為7.26%、11.4%、16.8%、25.2%。

7 結(jié)束語

針對(duì)工作流截止期約束下的準(zhǔn)確率優(yōu)化問題，本文采用了任務(wù)、服務(wù)與有向無環(huán)圖DAG相結(jié)合的方式，生成工作流模型。在此基礎(chǔ)上，提出了在截止期約束下的串歸約優(yōu)化算法，通過對(duì)工序的每個(gè)環(huán)節(jié)進(jìn)行時(shí)間約束，以逆向迭代的方式，求得每層任務(wù)在不同時(shí)刻開始時(shí)的最大準(zhǔn)確率，所有任務(wù)都完成時(shí)以最大完工準(zhǔn)確率確定優(yōu)化路徑。實(shí)驗(yàn)數(shù)據(jù)表明，相比于傳統(tǒng)的單向目標(biāo)算法，串歸約優(yōu)化算法的優(yōu)化率達(dá)到了7.7%。與此同時(shí)，本文還對(duì)影響優(yōu)化效果的因素即截止期的范圍和業(yè)務(wù)流程的任務(wù)量進(jìn)行了分析。但還存在沒能將業(yè)務(wù)流程的運(yùn)作成本考慮進(jìn)去的問題，在此還需要進(jìn)一步研究討論，充分考慮在業(yè)務(wù)流程中服務(wù)的相關(guān)屬性，真正找出一條具有效率化、準(zhǔn)確化并能充分降低成本費(fèi)用的最佳路徑，以后的研究會(huì)進(jìn)一步地改進(jìn)并加以完善。

[1] DE P, DUNNE E J, GHOSH J B, et al. Complexity of the discrete time-cost tradeoff problem for project networks[J]. Operations Research, 1997, 45(2): 302-306.

[2] BUYYA R, GIDDY J, ABRAMSON D. An evaluation of economy-based resource trading and scheduling on computational power grids for parameter sweep applications[C]//Active Middleware Services. [S.l.]: Springer, 2000: 221-230.

[3] BUYYA R, ABRAMSON D, JONAT H G, et al. Economic models for resource management and scheduling in grid computing[J]. Concurrency & Computation: Practice & Experience, 2002, 14(13-15): 1507-1542.

[4] NASONOV D, VISHERATIN A, BUTAKOV N, et al. Hybrid evolutionary workflow scheduling algorithm for dynamic heterogeneous distributed computational environment[J]. Journal of Applied Logic, 2016, 299: 83-92.

[5] MA Z, CAO J, QIAN S. DDS: a deadline driven workflow scheduling algorithm for hybrid amazon instances[M]. [S.l.]: Advances in Services Computing, 2015.

[6] YOON D, KIM S H, KANG D K, et al. Hybrid workflow management in cloud broker system[C]//Cloud Computing. [S.l.]: Springer, 2015: 145-155.

[7]CHEN W, LEE Y C, FEKETE A, et al. Adaptive multiple- workflow scheduling with task rearrangement[J]. Journal of Supercomputing, 2015, 71(4): 1297-1317.

[8] 苑迎春, 李小平, 王茜, 等. 基于逆向分層的網(wǎng)格工作流調(diào)度算法[J]. 計(jì)算機(jī)學(xué)報(bào), 2008, 31(2): 282-290.

YUAN Yin-chun, LI Xiao-ping, WANG Qian, et al. Bottom level based heuristic for workflow scheduling in grids[J]. Chinese Journal of Computers, 2008, 31(2): 282-290.

[9] 苑迎春, 李小平, 王茜. 基于串歸約的網(wǎng)格工作流費(fèi)用優(yōu)化方法[J]. 計(jì)算機(jī)研究與發(fā)展, 2008, 45(2): 246-253.

YUAN Yin-chun, LI Xiao-ping, WANG Qian. Cost optimization heuristics for grid workflows scheduling based on serial reduction[J]. Journal of Computer Research and Development, 2008, 45(2): 246-253.

[10] 劉燦燦, 張衛(wèi)民, 駱志剛. 基于逆向分層的工作流時(shí)間-費(fèi)用優(yōu)化方法[J]. 國防科技大學(xué)學(xué)報(bào), 2013, 35(3): 61- 66.

LIU Can-can, ZHANG Wei-min, LUO Zhi-gang. Time and cost trade-off heuristics for workflow scheduling based on bottom level[J]. Journal of National University of Defense Technology, 2013, 35(3): 61-66.

[11] 曹斌, 王小統(tǒng), 熊麗榮, 等. 時(shí)間約束云工作流調(diào)度的粒子群搜索方法[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2016, 22(2): 372- 380.

CAO Bin, WANG Xiao-tong, XIONG Li-rong, et al. Searching method for particle swarm optimization of cloud workflow scheduling with time constraint[J]. Computer Integrated Manufacturing Systems, 2016, 22(2): 372-380.

[12] 武星, 卓少劍, 張武. 成本最優(yōu)化工作流技術(shù)驅(qū)動(dòng)的研發(fā)協(xié)同軟件即服務(wù)應(yīng)用[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2013, 19(8): 1748-1754.

WU Xing, ZHUO Shao-jian, ZHANG Wu. Cost optimization workflow-driven SssS for collaborative research and development[J]. Computer Integrated Manufacturing Systems, 2013, 19(8): 1748-1754.

編 輯 蔣 曉

Research on Serial Reduction Algorithm for Accuracy of Processing Products under Time Constraints

LUO Zhi-yong1,2, WANG Peng1, YOU Bo2, and SU Jie1

(1. School of Computer Science and Technology, Harbin University of Science and Technology Harbin 150080; 2. School of Mechanical Engineering, Harbin University of Science and Technology Harbin 150080)

Completion time and accuracy are the most important attributes of processing products’ business, however, single attribute optimization algorithm only can optimize one attribute, let alone balancing these two attributes dynamically. In order to fix this problem, a serial reduction algorithm based on directed acyclic graph is proposed. The algorithm constraints each tasks' activity section by using backwards iterative eduction to choose appropriate service for achieving the optimization of these two attributes. Statistical data shows that serial reduction algorithm does get an optimized path with time and accuracy balance, but its optimization efficiency is limited by the completion deadline and the number of tasks. The research conclusion provides a certain theoretical reference for the optimization of production scheduling.

accuracy optimization; deadline; temporal consistency; workflow schedule

TP393

A

10.3969/j.issn.1001-0548.2017.06.022

2016-06-20；

2016-12-22

國家自然科學(xué)基金青年項(xiàng)目(61403109)

羅智勇(1978-)，男，副教授，主要從事網(wǎng)絡(luò)安全、科學(xué)工作流調(diào)度方面的研究.