作業(yè)車(chē)間調(diào)度算法資源云服務(wù)化方法

劉勝輝 張星 張淑麗 馬超

摘 要：針對(duì)制造執(zhí)行系統(tǒng)間調(diào)度算法資源共享度不高，并且難以高效地從候選調(diào)度算法資源中選擇合適的求解算法進(jìn)行調(diào)度排產(chǎn)的問(wèn)題，研究了云制造環(huán)境下的作業(yè)車(chē)間調(diào)度算法資源云服務(wù)化方法。首先基于OWL-S（ontology web language for services）建立調(diào)度算法資源的本體數(shù)據(jù)模型以及發(fā)布規(guī)范，然后為了提高算法服務(wù)請(qǐng)求者滿(mǎn)意度和算法資源提供者經(jīng)濟(jì)收益，提出了基于加權(quán)多維特征融合的量化匹配與推薦方法。最后，通過(guò)搭建原型系統(tǒng)，并利用哈電機(jī)的歷史數(shù)據(jù)進(jìn)行仿真實(shí)驗(yàn)。結(jié)果表明，所提出的數(shù)據(jù)模型和推薦算法能夠有效的提升調(diào)度算法資源的共享程度和選擇速度。

關(guān)鍵詞：

云制造；算法；作業(yè)計(jì)劃與調(diào)度；本體；語(yǔ)義

DOI：10.159

38/j.jhust.2018.03.001

中圖分類(lèi)號(hào)： TP301

文獻(xiàn)標(biāo)志碼： A

文章編號(hào)： 1007-2683（2018）03-0001-08

Servitization of Job Shop Scheduling Algorithms

LIU Sheng-hui， ZHANG Xing， ZHANG Shu-li， MA Chao

（School of Software， Harbin University of Science and Technology， Harbin 150080， China）

Abstract：The scheduling algorithm resources are not yet fully shared betwwen manufacturing execution system， and it is difficult to efficiently select the appropriate scheduling algorithm for scheduling problem from the candidate scheduling resources. To resolve this issue， the servitization of job shop scheduling algorithm resource in cloud manufacturing was studied. Firstly， an OWL-S-based ontology data model and publication specification of scheduling algorithm resource was given， and then a quantitative matching and recommending method based on weighted multidimensional feature fusion was presented， in order to improve the satisfaction of algorithm service requesters and the economic benefits of algorithm resource providers. Finally， through building a prototype system and using the historical data of Harbin Electrical Machinery Plant as a verification case， the results proved that the data model and recommend algorithm can effectively promote the sharing degree and selection speed of scheduling resources.

Keywords：cloud manufacturing； algorithm； Job Shop Scheduling； ontology； semantics

0 引 言

作業(yè)車(chē)間調(diào)度是制造執(zhí)行系統(tǒng)（manufacturing execution system， MES）的核心功能之一，其是車(chē)間能否在期望的時(shí)間內(nèi)合理利用有限的制造資源完成相應(yīng)的加工任務(wù)的關(guān)鍵，因此，及時(shí)準(zhǔn)確地作業(yè)車(chē)間調(diào)度對(duì)車(chē)間生產(chǎn)系統(tǒng)的高效運(yùn)行有著重要地影響。

當(dāng)前的制造執(zhí)行系統(tǒng)多處于獨(dú)立、封閉的環(huán)境，不同制造執(zhí)行系統(tǒng)之間的調(diào)度算法資源尚不能進(jìn)行充分共享，制約了車(chē)間生產(chǎn)效率的提升。并且，現(xiàn)實(shí)生產(chǎn)中，作業(yè)車(chē)間調(diào)度是一個(gè)復(fù)雜的問(wèn)題，在不同環(huán)境下調(diào)度問(wèn)題的模型（目標(biāo)函數(shù)與約束）和求解方法[1-2]也不盡相同。針對(duì)不同的問(wèn)題模型，如何高效地從眾多的調(diào)度算法中選擇合適的求解算法，也是一直困擾著制造企業(yè)的決策者。

云制造[3-4]的核心思想就是充分利用現(xiàn)在的制造資源，進(jìn)行優(yōu)化配置，實(shí)現(xiàn)資源的共享與協(xié)作。因此，針對(duì)上述問(wèn)題，本文研究如何將作業(yè)車(chē)間調(diào)度算法這一特殊的軟制造資源進(jìn)行服務(wù)化封裝[5-9]，構(gòu)建作業(yè)車(chē)間調(diào)度算法資源云服務(wù)池，提高其資源利用率，實(shí)現(xiàn)算法資源的增值增效；同時(shí)，給出在算法資源云服務(wù)平臺(tái)中作業(yè)車(chē)間調(diào)度算法的語(yǔ)義匹配方法[10-14]和算法資源使用的評(píng)價(jià)模型，以便支持算法資源服務(wù)請(qǐng)求者獲得適宜的作業(yè)車(chē)間調(diào)度算法。

1 作業(yè)車(chē)間調(diào)度算法資源共享過(guò)程

1.1 計(jì)劃與調(diào)度算法資源的標(biāo)準(zhǔn)化接入

計(jì)劃與調(diào)度算法資源屬于制造軟資源中的軟件類(lèi)資源，同時(shí)計(jì)劃與調(diào)度算法具有與云服務(wù)使用者交互性不高的特點(diǎn)，因此適用于采取基于遠(yuǎn)程調(diào)用的方式來(lái)實(shí)現(xiàn)算法資源的接入。具體的說(shuō)，可采用Web Service技術(shù)實(shí)現(xiàn)算法資源的標(biāo)準(zhǔn)化的互聯(lián)網(wǎng)接入：利用SOAP（simple object access protocol）描述算法資源輸入和輸出消息的格式，利用WSDL（web services description language）描述如何訪(fǎng)問(wèn)云服務(wù)提供者的算法資源接口，利用UDDI（universal description discovery and integration）來(lái)管理、分發(fā)及查詢(xún)封裝成Web Service的計(jì)劃與調(diào)度算法資源。

1.2 計(jì)劃與調(diào)度算法資源的優(yōu)化管理

計(jì)劃與調(diào)度算法資源的優(yōu)化管理，主要任務(wù)是針對(duì)不同的算法資源請(qǐng)求，找到最適合的算法資源進(jìn)行處理。它分為兩個(gè)階段：根據(jù)用戶(hù)請(qǐng)求信息，通過(guò)檢索匹配，找到資源服務(wù)池中滿(mǎn)足需求的候選算法服務(wù)集；根據(jù)歷史評(píng)價(jià)信息，對(duì)候選服務(wù)集中的算法資源進(jìn)行優(yōu)化選擇。

1.3 計(jì)劃與調(diào)度算法資源的運(yùn)行與監(jiān)控

計(jì)劃與調(diào)度算法資源的運(yùn)行與監(jiān)控的主要任務(wù)是，把算法資源請(qǐng)求者的數(shù)據(jù)發(fā)送給計(jì)劃與調(diào)度算法資源的優(yōu)化管理階段最終選擇的調(diào)度算法，進(jìn)行處理；處理完畢后，把調(diào)度結(jié)果返回給算法資源請(qǐng)求者，并且對(duì)算法資源請(qǐng)求者和算法資源提供者的評(píng)價(jià)信息進(jìn)行收集，從而對(duì)算法資源的優(yōu)化選擇進(jìn)行支撐。

2 基于本體的算法資源服務(wù)語(yǔ)義描述

2.1 算法資源的服務(wù)本體

以往的資源虛擬化和服務(wù)化方法，是針對(duì)所有的制造資源和制造能力的共性進(jìn)行研究，而調(diào)度算法資源是制造資源中的軟資源，具有自己特性。本文針對(duì)軟資源的特點(diǎn)，結(jié)合OWL-S研究調(diào)度算法資源的服務(wù)化，算法資源標(biāo)準(zhǔn)化的接入采用Web Service技術(shù)。在Web Service技術(shù)中的WSDL對(duì)服務(wù)的屬性描述缺乏進(jìn)一步的支持，但為了滿(mǎn)足對(duì)生產(chǎn)計(jì)劃與調(diào)度算法資源的智能管理及用戶(hù)的個(gè)性化需求，必須對(duì)算法資源服務(wù)的語(yǔ)義進(jìn)行充分描述。因此，首先需要基于OWL-S給出算法資源的服務(wù)本體。

定義1 任一算法資源服務(wù)定義為一個(gè)AR_Service本體，其本體模型為：

AR_Service=

其中，AR_ServiceProfile描述算法資源服務(wù)的領(lǐng)域知識(shí)。服務(wù)提供者和使用者可以通過(guò)AR_ServiceProfile來(lái)描述算法資源服務(wù)的基本、功能、性能與狀態(tài)等方面的信息。服務(wù)發(fā)現(xiàn)模型通過(guò)服務(wù)供需雙方在AR_ServiceProfile上的雙向聲明信息來(lái)實(shí)現(xiàn)服務(wù)智能匹配，幫助服務(wù)使用者獲得滿(mǎn)足需求的AR_Service。

AR_ServiceModel描述算法資源服務(wù)實(shí)現(xiàn)的內(nèi)部流程，即具體實(shí)現(xiàn)細(xì)節(jié)。由于一個(gè)生產(chǎn)計(jì)劃與調(diào)度算法的執(zhí)行過(guò)程具有原子性，因此每個(gè)AR_ServiceModel都是一個(gè)可以被直接調(diào)用的不可再分的原子過(guò)程，其需要綁定AR_ServiceGrounding信息。

AR_ServiceGrounding描述如何獲得算法資源服務(wù)，具體包括服務(wù)提供者的訪(fǎng)問(wèn)地址、通信協(xié)議、輸入與輸出的定義等信息。

2.2 算法資源的領(lǐng)域本體

算法資源的領(lǐng)域本體可以描述成為：

AR_ServiceProfile =

其中，基本屬性BP（BasicProperty）包括算法編碼、算法名稱(chēng)、算法簡(jiǎn)介、算法類(lèi)型、算法提供者等信息。

功能屬性FP（FunctionProperty）包括算法功能簡(jiǎn)述、算法約束條件、算法功能的輸入、算法功能的輸出等信息。

性能屬性PP（PerformanceProperty）包括算法的求解能力、收斂性和求解精度等信息。

狀態(tài)屬性SP（StatusProperty）包括算法的當(dāng)前狀態(tài)、當(dāng)前狀態(tài)開(kāi)始時(shí)間、負(fù)荷狀態(tài)等信息。其中，算法當(dāng)前狀態(tài)的取值范圍為{可用，更新中、已下線(xiàn)}。

評(píng)價(jià)屬性EP（EvaluationPorperty）包括算法的功能評(píng)價(jià)、性能評(píng)價(jià)、服務(wù)QoS（Quality of Service）評(píng)價(jià)、信譽(yù)評(píng)價(jià)等信息。

應(yīng)用屬性AP（ApplicationProperty）包括算法的應(yīng)用方式和付費(fèi)方式。

3 算法資源云服務(wù)的優(yōu)化管理

算法資源云服務(wù)的優(yōu)化管理功能主要是指對(duì)算法云平臺(tái)中的算法資源服務(wù)池中的算法服務(wù)進(jìn)行優(yōu)化管理，其目標(biāo)是為消費(fèi)者發(fā)布的調(diào)度任務(wù)找到最優(yōu)化的算法服務(wù)來(lái)完成它。要實(shí)現(xiàn)這一目標(biāo)，就需要經(jīng)歷兩個(gè)階段的處理工作：基于語(yǔ)義的算法服務(wù)檢索與匹配，從語(yǔ)義層面找到一組與調(diào)度任務(wù)相匹配的算法服務(wù)，即可選算法服務(wù)集；基于評(píng)價(jià)指數(shù)的算法優(yōu)化選擇，以評(píng)價(jià)指數(shù)作為衡量標(biāo)準(zhǔn)，從可選服務(wù)集中選擇最優(yōu)化的算法服務(wù)。

3.1 基于語(yǔ)義的算法服務(wù)檢索與匹配

以往的匹配方法都是面向所有的Web服務(wù)的檢索與匹配，沒(méi)有考慮到車(chē)間調(diào)度算法云服務(wù)的特殊性。由于調(diào)度算法云服務(wù)是一個(gè)很明確的領(lǐng)域，并且不涉及到服務(wù)的組合，因而檢索的計(jì)算量會(huì)降低很多。并且請(qǐng)求者和提供者使用的是統(tǒng)一的本體，可以很大程度上提高匹配的精度。

基于語(yǔ)義的算法服務(wù)檢索與匹配旨在根據(jù)用戶(hù)對(duì)算法服務(wù)的需求描述，利用各類(lèi)服務(wù)匹配算法，從算法云服務(wù)平臺(tái)中篩選出最符合用戶(hù)需求的算法云服務(wù)。算法云服務(wù)請(qǐng)求中，有的需求是必須嚴(yán)格滿(mǎn)足的，稱(chēng)為硬性需求；有些需求是可以盡量滿(mǎn)足的，稱(chēng)為軟性需求。算法云服務(wù)與算法云服務(wù)需求的匹配度可用如下公式表示：

MD（R，P）=（

SymboleC@w*MDS（R，P））*

SymbolPA@（MDH（R，P））（1）

式中：R代表算法云服務(wù)請(qǐng)求；P代表算法云服務(wù)；MD（R，P）代表算法云服務(wù)的匹配度；MDS（R，P）代表算法云服務(wù)對(duì)算法云服務(wù)請(qǐng)求的軟性需求的匹配度，它的值域?yàn)閇0，1]；w為該項(xiàng)需求的權(quán)重；MDH（R，P）表示算法云服務(wù)對(duì)算法云服務(wù)請(qǐng)求硬性需求的匹配度，它的值域?yàn)?，1。

根據(jù)式（1）可以將算法云服務(wù)的匹配分為兩個(gè)階段：硬性需求匹配階段和軟性需求匹配階段。由于硬性需求的匹配函數(shù)的值域?yàn)?，1，所以可以通過(guò)硬性需求匹配淘汰掉不滿(mǎn)足需求的算法云服務(wù)，并且所有滿(mǎn)足硬性需求的算法云服務(wù)的匹配度的值等于軟性需求的匹配度的值。硬性需求的匹配包括狀態(tài)屬性匹配、應(yīng)用屬性匹配、基本屬性匹配和功能屬性匹配；軟性需求匹配包括性能屬性匹配。針對(duì)算法云服務(wù)的不同屬性，需采用多種匹配度的計(jì)算方法。為此，首先要構(gòu)建針對(duì)算法云服務(wù)的各個(gè)屬性的匹配模型：

定義2 一個(gè)算法云服務(wù)的功能屬性可以表示為四元組

F=

其中：Dcrp（Description）表示算法云服務(wù)的功能描述，Cstr（Constraint）表示算法云服務(wù)的約束，Input為算法云服務(wù)執(zhí)行所需要輸入的信息組成的參數(shù)集合；Output表示算法云服務(wù)執(zhí)行后所產(chǎn)生的輸出信息組成的參數(shù)集合。為實(shí)現(xiàn)基于語(yǔ)義的匹配，Dcrp、Cstr、Input和Output的參數(shù)均引用領(lǐng)域本體中的概念。

定義3 算法云服務(wù)功能屬性匹配程度指算法云服務(wù)功能屬性滿(mǎn)足算法云服務(wù)請(qǐng)求功能需求的程度，設(shè)算法云服務(wù)功能需求為：

RF=

算法云服務(wù)功能屬性為：

PF=

w1，w2，w3和w4分別為Dcrp，Cstr，Input和Output 4個(gè)屬性在匹配過(guò)程中所占的權(quán)重，并且w1+w2+w3+w4=1則算法云服務(wù)功能屬性匹配程度FMD（Function Macth Degree）可表示為

FMD（R，P）=

w1*dcrp_md（RDcrp，PDcrp）

+w2*cstr_md（RCstr，PCstr）

+w3*input_md（RInput，PInpuit）

+w4*output_md（ROutput，POutput）（2）

定義4 一個(gè)算法云服務(wù)的性能屬性可以表示為三元組

P=

其中：Ability表示算法云服務(wù)的求解能力，即該算法云服務(wù)處理多大規(guī)模的問(wèn)題時(shí)，性能最穩(wěn)定；Cvgc （Convergence） 表示算法云服務(wù)的收斂性，用算法的運(yùn)行時(shí)間來(lái)衡量；Precs（Precision）表示算法云服務(wù)處理特定問(wèn)題所得調(diào)度結(jié)果與該問(wèn)題的最優(yōu)解之間的偏差大小。

定義5 算法云服務(wù)性能匹配程度指算法云服務(wù)的性能屬性滿(mǎn)足算法云服務(wù)請(qǐng)求性能需求的程度，設(shè)算法云服務(wù)性能需求為：

RP=

算法云服務(wù)性能屬性為：

PP=

δ1，δ2和δ3分別為Ability，Cvgc和Precs三個(gè)屬性在匹配過(guò)程中所占的權(quán)重，并且δ1+δ2+δ3= 1，則綜合匹配程度PMD（performance macth degree）可表示為

PMD（R，P）=

δ1*ability_md（RAbility，PAbility）

+δ2*cvgc_md（RCvgc，PCvgc）

+δ3*precs_md（RPrecs，PPrecs）（3）

在匹配開(kāi)始之前，需要使用服務(wù)解析器對(duì)標(biāo)準(zhǔn)的算法云服務(wù)請(qǐng)求本體進(jìn)行解析，從中解析出用戶(hù)的需求信息。

1）硬性需求匹配階段

（a）狀態(tài)屬性匹配。對(duì)那些當(dāng)前狀態(tài)為更新中、已下線(xiàn)，或者負(fù)荷狀態(tài)為滿(mǎn)負(fù)荷、超負(fù)荷的算法云服務(wù)進(jìn)行過(guò)濾。

（b）應(yīng)用屬性匹配。在進(jìn)行應(yīng)用屬性匹配之前，首先檢查解析出的用戶(hù)需求是否對(duì)這個(gè)屬性有要求，如果沒(méi)有，則跳過(guò)這個(gè)階段；如果有，則對(duì)應(yīng)用方式和付款方式與算法云服務(wù)請(qǐng)求不符的算法云服務(wù)進(jìn)行過(guò)濾。

（c）基本屬性匹配。在進(jìn)行基本屬性匹配之前，首先檢查解析出的用戶(hù)需求是否對(duì)這個(gè)屬性有要求，如果沒(méi)有，則跳過(guò)這個(gè)階段；如果有，則對(duì)算法類(lèi)型和算法編碼等與算法云服務(wù)請(qǐng)求不符的算法云服務(wù)進(jìn)行過(guò)濾。

（d）功能屬性匹配。功能屬性匹配又分為功能描述匹配、約束條件匹配、輸入與輸出參數(shù)匹配和功能屬性綜合匹配4部分的匹配：

①功能描述匹配。

對(duì)解析出的功能需求，通過(guò)中文分詞，提取關(guān)鍵字，然后依據(jù)算法資源的領(lǐng)域本體，與本體中定義的概念進(jìn)行映射，組成功能描述向量。同樣的，把算法云服務(wù)資源池中的算法云服務(wù)的功能描述信息進(jìn)行映射，組成功能向量。然后，將功能需求中的每一個(gè)項(xiàng)與算法云服務(wù)的項(xiàng)逐一進(jìn)行匹配，并取匹配程度最高的項(xiàng)，作為功能項(xiàng)匹配對(duì)。最后，功能描述的匹配度，取需求功能描述向量各個(gè)項(xiàng)的平均值。

②約束條件匹配。

在進(jìn)行求約束條件匹配前，首先檢查解析出的用戶(hù)需求中是否對(duì)這部分有要求，如果沒(méi)有，則所有算法云服務(wù)的這部分的匹配度都為1，否則對(duì)解析出的約束條件需求中的每一條約束信息，利用語(yǔ)義推理工具進(jìn)行語(yǔ)義推理，計(jì)算它和算法云服務(wù)的所有約束信息進(jìn)行匹配，并把匹配程度最大的作為該條的匹配程度，記錄對(duì)應(yīng)的約束條件對(duì)。最后，選取約束條件匹配對(duì)中，匹配度最小的作為該項(xiàng)的最終匹配度。

③輸入、輸出參數(shù)匹配。

首先，對(duì)輸入、輸出參數(shù)的參數(shù)個(gè)數(shù)進(jìn)行匹配。假設(shè)算法云服務(wù)請(qǐng)求R有IR個(gè)輸入?yún)?shù)，OR個(gè)輸出參數(shù)；算法云服務(wù)P有IP個(gè)輸入?yún)?shù)，OP個(gè)輸出參數(shù)。當(dāng)IR < IP或者 OR > OP時(shí)，則算法云服務(wù)P不能滿(mǎn)足R的需求。

然后，對(duì)算法云服務(wù)請(qǐng)求R的第一個(gè)輸出參數(shù)，計(jì)算它和算法云服務(wù)P的所有輸出的匹配程度，并把匹配程度最大的作為該項(xiàng)的匹配度，記錄對(duì)應(yīng)的輸出參數(shù)對(duì)。如果該匹配度大于預(yù)設(shè)的參數(shù)匹配度閾值，則按照相同的方法，計(jì)算其余OR-1個(gè)參數(shù)的匹配程度；否則，算法云服務(wù)P不能滿(mǎn)足R的需求。同理，對(duì)R的輸入?yún)?shù)進(jìn)行匹配。最后，選取輸入、輸出參數(shù)各項(xiàng)中匹配程度最低的作為該項(xiàng)的最終匹配程度。

④功能屬性綜合匹配。根據(jù)各屬性的匹配程度和其所占權(quán)重，計(jì)算算法云服務(wù)與算法云服務(wù)請(qǐng)求最終的匹配程度，根據(jù)預(yù)設(shè)的匹配度閾值，過(guò)濾匹配度過(guò)低的算法云服務(wù)。

2）軟性需求匹配階段

（a）性能屬性匹配。性能屬性匹配又分為求解能力匹配、收斂性匹配和求解精度匹配3個(gè)部分的匹配：

①求解能力匹配。

求解能力指的是該算法云服務(wù)在處理多大規(guī)模的問(wèn)題時(shí)，穩(wěn)定性最好，它是一個(gè)區(qū)間，為了能夠進(jìn)行定量的分析，我們用這個(gè)區(qū)間的中心點(diǎn)進(jìn)行表示。在進(jìn)行求解能力匹配前，首先檢查解析出的用戶(hù)需求中是否對(duì)這個(gè)性能有要求，如果沒(méi)有，則所有算法云服務(wù)的這部分的匹配度都為1，否則按照如下公式進(jìn)行計(jì)算其求解能力匹配度。

ability_md（R，P）=11+logPAbilityRAbility（4）

式（4）中：ability_md（R，P）表示算法云服務(wù)求解能力的匹配度；R表示算法云服務(wù)請(qǐng)求；P表示算法云服務(wù)；RAbility表示算法云服務(wù)的求解能力需求；PAbility表示算法云服務(wù)的求解能力。

②收斂性匹配。

收斂性指的是算法云服務(wù)在進(jìn)行處理特定規(guī)模的問(wèn)題時(shí)，進(jìn)入穩(wěn)定期的速度，由于大多數(shù)的算法都把處理結(jié)果進(jìn)入穩(wěn)定期作為算法的結(jié)束條件，所里這里用算法的運(yùn)行時(shí)間表示算法的收斂性。在進(jìn)行收斂性的匹配前，首先檢查解析出的用戶(hù)需求是否對(duì)這個(gè)性能有要求，如果沒(méi)有，則所有算法云服務(wù)的這部分的匹配度為1。如果有，則看用戶(hù)是否對(duì)算法的求解能力有要求，如果有，則用算法之前根據(jù)指定測(cè)試用例測(cè)得的收斂性中問(wèn)題規(guī)模與求解能力的值最相近的，根據(jù)如下公式計(jì)算其收斂性匹配度；如果沒(méi)有，則用預(yù)先選定的問(wèn)題規(guī)模的收斂性，根據(jù)如下公式計(jì)算其收斂性匹配度。

cvgc_md（R，P）=1-|RCvgc-PCvgc|RCvgc（5）

式中：cvgc_md（R，P）表示算法云服務(wù)的收斂性匹配度；R表示算法云服務(wù)請(qǐng)求；P表示算法云服務(wù)；RCvgc表示算法云服務(wù)請(qǐng)求的收斂性需求；PCvgc表示算法云服務(wù)的收斂性。

③求解精度匹配。

求解精度指的是算法云服務(wù)求得的結(jié)果與最優(yōu)解之間的差異，用該規(guī)模問(wèn)題的最優(yōu)解的生產(chǎn)周期與算法求得的解的生產(chǎn)周期的比進(jìn)行表示。在進(jìn)行求解精度的匹配之前，首先檢查解析出的算法云服務(wù)需求中是否對(duì)這部分性能有要求，如果沒(méi)有，則所有算法云服務(wù)的這部分匹配度都為1。如果有，則看用戶(hù)是否對(duì)算法的求解能力有要求，如果有，則用算法之前根據(jù)指定測(cè)試用例測(cè)得的求解精度中問(wèn)題規(guī)模與求解能力的值最相近的，根據(jù)式（6）計(jì)算其收斂性匹配度；如果沒(méi)有，則用預(yù)先選定的問(wèn)題規(guī)模的求解精度，根據(jù)式（6）計(jì)算其求解精度匹配度。

precs_md（R，P）=1，RPrecs>PPrecs

PPrecsRPrecs，others（6）

式中：precs_md（R，P）表示算法云服務(wù)求解精度匹配度；R表示算法云服務(wù)請(qǐng)求；P表示算法云服務(wù)；RPrecs表示算法云服務(wù)請(qǐng)求的求解精度需求；PPrecs表示算法云服務(wù)的求解精度。

④性能屬性綜合匹配。

根據(jù)各屬性的匹配程度和其所占權(quán)重，計(jì)算算法云服務(wù)與算法云服務(wù)請(qǐng)求最終的性能屬性匹配程度。

由于硬性需求的匹配函數(shù)的值域?yàn)?，1，所以所有滿(mǎn)足硬性需求的算法云服務(wù)的匹配度的值等于軟性需求的匹配度的值。即候選算法云服務(wù)集中的算法云服務(wù)的性能屬性的綜合匹配度等于最終的算法云服務(wù)匹配度。根據(jù)這個(gè)值對(duì)算法云服務(wù)進(jìn)行排序，然后，選取預(yù)設(shè)數(shù)量的算法云服務(wù)進(jìn)入基于評(píng)價(jià)指數(shù)的算法服務(wù)優(yōu)化選擇。

3.2 基于評(píng)價(jià)指數(shù)的算法服務(wù)優(yōu)化選擇

實(shí)現(xiàn)基于評(píng)價(jià)指數(shù)的算法服務(wù)優(yōu)化選擇的關(guān)鍵是算法服務(wù)綜合評(píng)價(jià)指數(shù)的綜合計(jì)算，此處采用的是主觀與客觀相結(jié)合、定性與定量相結(jié)合的綜合評(píng)估模式。為此，首先需要構(gòu)建算法服務(wù)綜合評(píng)價(jià)指數(shù)的評(píng)價(jià)指標(biāo)體系。該評(píng)價(jià)指標(biāo)體系是一個(gè)三層模型，頂層是目標(biāo)層，即綜合評(píng)估的目標(biāo)是獲取評(píng)價(jià)指數(shù)的取值；中間層是準(zhǔn)則層，包括算法功能、算法性能、服務(wù)QoS[15-17]、信譽(yù)4個(gè)評(píng)價(jià)維度；底層是指標(biāo)層，針對(duì)不同的維度，分別對(duì)應(yīng)不同的指標(biāo)。如圖2所示，算法功能準(zhǔn)則一般包含功能完備性、功能充分性等指標(biāo)。算法性能準(zhǔn)則一般包括算法的求解能力、算法的計(jì)算時(shí)間、算法的求解精度等指標(biāo)。服務(wù)QoS準(zhǔn)則一般包括算法服務(wù)的響應(yīng)時(shí)間、算法服務(wù)的可見(jiàn)性、算法服務(wù)的友好性、算法服務(wù)的可靠性、算法服務(wù)的安全性、算法服務(wù)的可用性等指標(biāo)。信譽(yù)準(zhǔn)則一般包括算法本身的信譽(yù)度、算法提供者的信譽(yù)度等指標(biāo)。

針對(duì)上述評(píng)價(jià)指標(biāo)，它們的取值來(lái)自多個(gè)方面：有的評(píng)價(jià)指標(biāo)取值是來(lái)自于云平臺(tái)本身，例如，算法服務(wù)的計(jì)算時(shí)間（平均CPU時(shí)間）、算法服務(wù)的響應(yīng)時(shí)間、算法服務(wù)的可靠性（訪(fǎng)問(wèn)成功次數(shù)與總訪(fǎng)問(wèn)次數(shù)之比）等；有的評(píng)價(jià)指標(biāo)取值來(lái)自于算法服務(wù)的提供者，提供者采用領(lǐng)域內(nèi)公認(rèn)的算法測(cè)試用例給出算法性能類(lèi)指標(biāo)的取值，例如，算法的求解能力、求解精度；此外，其它評(píng)價(jià)指標(biāo)均來(lái)自算法服務(wù)的消費(fèi)者，消費(fèi)者在通過(guò)云平臺(tái)使用算法服務(wù)的過(guò)程中產(chǎn)生的對(duì)算法服務(wù)在功能、服務(wù)QoS以及信譽(yù)方面的感受。

最后，結(jié)合了消費(fèi)者、提供商和算法云平臺(tái)三方面的評(píng)價(jià)信息，并采用的是主觀與客觀相結(jié)合、定性與定量相結(jié)合的綜合評(píng)估模式，使得評(píng)估的結(jié)果的可靠性更強(qiáng)。從可實(shí)現(xiàn)性角度考慮，具體的評(píng)價(jià)方法選擇層次分析法AHP（analytic hierarchy process）[18-19]。基于上述內(nèi)容，云平臺(tái)的運(yùn)營(yíng)者就可以計(jì)算可選服務(wù)集中多個(gè)算法服務(wù)的評(píng)價(jià)指數(shù)，然后依據(jù)它們的取值進(jìn)行排序，最終選取最優(yōu)的算法服務(wù)完成調(diào)度任務(wù)。

4 實(shí)例驗(yàn)證

為了驗(yàn)證本文提出的算法云服務(wù)本體及其匹配模型的可行性和有效性，本文結(jié)合算法云服務(wù)平臺(tái)的原型平臺(tái)，對(duì)以上方法進(jìn)行了實(shí)例驗(yàn)證。首先，將來(lái)自于MES系統(tǒng)的算法云服務(wù)發(fā)布到原型平臺(tái)，然后以平臺(tái)中6個(gè)功能相似的算法云服務(wù)作為考察對(duì)象，應(yīng)用本文提出的基于語(yǔ)義的匹配方法，依次與各個(gè)算法云服務(wù)進(jìn)行匹配，并對(duì)匹配的結(jié)果進(jìn)行排序和篩選。最后，采用本文提出的基于評(píng)價(jià)指數(shù)的優(yōu)化選擇方法，選取最優(yōu)的算法服務(wù)完成調(diào)度任務(wù)。

表1為來(lái)自MES的算法云服務(wù)請(qǐng)求的需求信息。表2為算法云服務(wù)平臺(tái)中的云服務(wù)，這些云服務(wù)在云平臺(tái)中用OWL—S文檔進(jìn)行描述，并且注冊(cè)到UDDI注冊(cè)中心，方便進(jìn)行服務(wù)匹配。

匹配過(guò)程如下：

1）硬性需求匹配：

①進(jìn)行狀態(tài)屬性匹配，五個(gè)候選算法云服務(wù)中，算法云服務(wù)2的當(dāng)前狀態(tài)為更新中，將它從候選服務(wù)集中剔除。

②進(jìn)行應(yīng)用屬性匹配，候選服務(wù)集中的五個(gè)的應(yīng)用屬性都滿(mǎn)足需求，進(jìn)行下一步匹配。

③進(jìn)行基本屬性匹配，由于算法云服務(wù)請(qǐng)求并未對(duì)這部分屬性進(jìn)行限制，跳過(guò)本部分的匹配，進(jìn)行下一步匹配。

④進(jìn)行功能屬性匹配，為了計(jì)算方便，取w1=w2=w3=w4=0.25。我們采用文[20]中的方法對(duì)概念間的匹配度進(jìn)行定量計(jì)算，然后根據(jù)由式（2）建立的功能屬性匹配度計(jì)算模型計(jì)算各個(gè)算法云服務(wù)的功能屬性匹配度。計(jì)算結(jié)果如表3所示。

其中算法云服務(wù)4由于輸入?yún)?shù)的個(gè)數(shù)比算法云服務(wù)請(qǐng)求的輸入?yún)?shù)多，不滿(mǎn)足需求，從候選云服務(wù)集中剔除。假設(shè)預(yù)設(shè)功能匹配度的閾值為0.97，則算法云服務(wù)6的匹配度低于閾值，從候選服務(wù)集中剔除。

2）軟性需求匹配

進(jìn)行性能匹配度匹配，為了方便計(jì)算取δ1=0.4，δ2=δ3=0.3。我們根據(jù)式（3）、式（4）、式（5）和式（6）提出的建立的性能屬性匹配度計(jì)算模型計(jì)算各個(gè)算法云服務(wù)的性能匹配度。計(jì)算結(jié)果如表4所示。由于所有滿(mǎn)足硬性需求的算法云服務(wù)的匹配度的值等于軟性需求的匹配度的值，所以表4中的性能屬性的匹配度就是最終的算法云服務(wù)的匹配度。假設(shè)預(yù)設(shè)選取2個(gè)算法云服務(wù)進(jìn)行基于評(píng)價(jià)指數(shù)的算法服務(wù)優(yōu)化選擇，則對(duì)算法云服務(wù)的匹配度進(jìn)行排序后，算法云服務(wù)5的匹配度最低，從候選服務(wù)集中剔除。

然后根據(jù)層次分析法AHP計(jì)算這2個(gè)算法服務(wù)的評(píng)價(jià)指數(shù)，經(jīng)計(jì)算算法云服務(wù)1的評(píng)價(jià)指數(shù)為0.674，算法云服務(wù)3的評(píng)價(jià)指數(shù)為0.753，所以選擇算法云服務(wù)3對(duì)算法云服務(wù)請(qǐng)求進(jìn)行處理。

5 結(jié) 語(yǔ)

高效地使用高質(zhì)量的作業(yè)調(diào)度算法是制造企業(yè)生產(chǎn)實(shí)現(xiàn)高效率、高柔性和高可靠性的關(guān)鍵，因此，對(duì)作業(yè)調(diào)度算法的服務(wù)化封裝進(jìn)行研究，從而構(gòu)建作業(yè)調(diào)度算法資源云服務(wù)平臺(tái)具有重大的現(xiàn)實(shí)和理論意義。本文結(jié)合云制造理論，基于OWL-S的本體描述語(yǔ)言，對(duì)調(diào)度算法資源的虛擬化和服務(wù)化封裝進(jìn)行了研究，構(gòu)建了調(diào)度算法資源服務(wù)本體，該本體可以有效的對(duì)調(diào)度算法資源進(jìn)行封裝。接著，設(shè)計(jì)了算法云服務(wù)與算法云服務(wù)請(qǐng)求的多階段匹配模型，并給出了量化方法，使得每個(gè)算法云服務(wù)請(qǐng)求都能匹配到適合它的候選算法云服務(wù)集。之后，又給出了基于評(píng)價(jià)的多層次的算法資源優(yōu)化選擇方案，使得用戶(hù)可以根據(jù)其他用戶(hù)對(duì)候選算法云服務(wù)集中的算法進(jìn)行優(yōu)化選擇，從中找到最適合自身需求的算法云服務(wù)。最后，通過(guò)搭建算法云服務(wù)平臺(tái)的原型系統(tǒng)，并采用哈爾濱電機(jī)廠(chǎng)的車(chē)間實(shí)際生產(chǎn)數(shù)據(jù)，對(duì)本文提出的模型進(jìn)行了實(shí)例驗(yàn)證。試驗(yàn)結(jié)果證明，本文提出的模型具有準(zhǔn)確性和可行性，可以有效的解決現(xiàn)今制造執(zhí)行系統(tǒng)的調(diào)度算法資源不能充分共享的問(wèn)題。

參 考 文 獻(xiàn)：

[1] 劉勝輝， 張淑麗， 滕春賢. 考慮不確定因素的單件小批作業(yè)計(jì)劃與調(diào)度動(dòng)態(tài)算法[J].哈爾濱工程大學(xué)學(xué)報(bào)， 2011， 32（4）： 471-475.

[2] 張宏國(guó)， 王彥俊. Pareto多目標(biāo)模糊調(diào)度算法研究[J]. 哈爾濱理工大學(xué)學(xué)報(bào)， 2013， 18（5）： 47-51.

[3] 李伯虎， 張霖， 任磊， 等. 云制造典型特征、關(guān)鍵技術(shù)與應(yīng)用[J]. 計(jì)算機(jī)集成制造系統(tǒng)， 2012， 18（7）： 1345-1356.

[4] 李伯虎， 張霖， 任磊， 等. 云制造典型特征、關(guān)鍵技術(shù)與應(yīng)用[J]. 計(jì)算機(jī)集成制造系統(tǒng)， 2012， 18（7）： 1345-1356.

[5] 張霖， 羅永亮， 陶飛，等. 制造云構(gòu)建關(guān)鍵技術(shù)研究[J]. 計(jì)算機(jī)集成制造系統(tǒng)， 2010， 16（11）：2510-2520.

[6] 曹?chē)[博， 許承東， 胡春生， 云制造環(huán)境中的虛擬制造單元[J]. 計(jì)算機(jī)集成制造系統(tǒng)， 2012，18（7）：1415-1425.

[7] 鄭鎂， 羅磊， 江平寧. 基于語(yǔ)義Web的云設(shè)計(jì)服務(wù)平臺(tái)及關(guān)鍵技術(shù)[J]. 計(jì)算機(jī)集成制造系統(tǒng)， 2012， 18（7）：1426-1434.

[8] 周競(jìng)濤， 楊海成. 基于同態(tài)映射的制造資源虛擬化機(jī)制[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)， 2014， 26（9）：1528-1535.

[9] 張映鋒， 張耿， 楊騰， 等. 云制造加工設(shè)備服務(wù)化封裝與云端化接入方法[J]. 計(jì)算機(jī)集成制造系統(tǒng)， 2014， 20（8）：2029-2037.

[10]尹超， 夏卿， 黎振武. 基于OWL-S的云制造服務(wù)語(yǔ)義匹配方法[J]. 計(jì)算機(jī)集成制造系統(tǒng)， 2012， 18（7）： 1494-1502.

[11]趙文棟， 陶曉臻， 彭來(lái)獻(xiàn)， 等. 一種基于功能語(yǔ)義的Web服務(wù)描述及預(yù)檢索方法[J]. 計(jì)算機(jī)科學(xué)， 2013， 40（11）： 222-227.

[12]馬森， 趙文， 袁崇義， 等. 基于規(guī)則推理的語(yǔ)義檢索若干關(guān)鍵技術(shù)研究[J]. 電子學(xué)報(bào)， 2013， 41（5）：977-981.

[13]吳根斌， 丁振凡. 基于語(yǔ)義Web的搜索引擎研究[J]. 計(jì)算機(jī)與現(xiàn)代化， 2012， （8）： 128-133.

[14]牟帥， 黃映輝， 李冠宇. 基于中文分詞的OWL-S/UDDI語(yǔ)義Web服務(wù)檢索模型[J]. 計(jì)算機(jī)工程與設(shè)計(jì)， 2009， 30（3）： 705-708.

[15]TAO Fei， ZHAO Dong-ming， ZHANG Lin. Resource Service Optimal-selection Based on Intuitionistic Fuzzy Set and Non-functionality QoS in Manufacturing Grid System[J]. Knowledge and Information Systems， 2010，25（1）：185-208.

[16]甘佳， 段桂江. 云制造服務(wù)信任評(píng)估技術(shù)[J]. 計(jì)算機(jī)集成制造系統(tǒng)， 2012， 18（7）：1527-1535.

[17]李永湘， 姚錫凡， 徐川， 等. 基于擴(kuò)展進(jìn)程代數(shù)的云制造服務(wù)組合建模與QoS評(píng)價(jià)[J]. 計(jì)算機(jī)集成制造系統(tǒng)， 2014，20（3）：689-700.

[18]李惠林， 殷國(guó)富， 謝慶生， 等. 面向網(wǎng)絡(luò)化制造的制造資源組合評(píng)價(jià)方法研究[J].計(jì)算機(jī)集成制造系統(tǒng)， 2008，14（5）：955-961.

[19]陳衛(wèi)衛(wèi)， 李濤， 李志剛， 等. 基于模糊層次分析法的云服務(wù)評(píng)估方法[J]. 解放軍理工大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2016，17（1）：25-30.

[20]李慧芳， 董訓(xùn)， 宋長(zhǎng)剛. 制造云服務(wù)智能搜索與匹配方法[J]. 計(jì)算機(jī)集成制造系統(tǒng)，2012，18（7）：1485-1493.