面向資源調(diào)度的矩陣規(guī)范化方法研究*

周建濤，陸海燕，葉新銘

(內(nèi)蒙古大學(xué)計(jì)算機(jī)學(xué)院，內(nèi)蒙古 呼和浩特 010021)

計(jì)算機(jī)支持的協(xié)同工作是基于大規(guī)模分布式系統(tǒng)的重要應(yīng)用，其中資源調(diào)度是非?；A(chǔ)的問(wèn)題，在資源調(diào)度中又存在大量的多屬性決策問(wèn)題。例如，在動(dòng)態(tài)、分布、異構(gòu)、自治的網(wǎng)格環(huán)境下，用工作流技術(shù)構(gòu)建復(fù)雜網(wǎng)格應(yīng)用，當(dāng)執(zhí)行某個(gè)具體任務(wù)時(shí)，網(wǎng)格中可選擇的滿(mǎn)足任務(wù)需求的執(zhí)行資源也許并非一個(gè)，可能有成百上千個(gè)。而在考量各備選資源時(shí)，除了完成任務(wù)的功能性需求(如：時(shí)間)，還可能考慮用戶(hù)定制的非功能性需求，如完成任務(wù)所需成本、資源的信譽(yù)度及服務(wù)質(zhì)量等。然而，各因素在其中發(fā)揮的作用不一樣，相當(dāng)于有不同的權(quán)值分配。在復(fù)雜系統(tǒng)中研究資源調(diào)度就是一類(lèi)多屬性決策問(wèn)題，其研究是現(xiàn)代決策科學(xué)的重要內(nèi)容，一直是國(guó)內(nèi)外研究界和工業(yè)界感興趣的課題，具有一定的重要性和現(xiàn)實(shí)意義。

1 背景知識(shí)

本節(jié)首先介紹需要用到的背景知識(shí)。

在一個(gè)多屬性決策(Multi-Attribute Decision Making， MADM)問(wèn)題中，屬性是反映對(duì)象之間的一種關(guān)系的指示量，其量化技術(shù)的合理性直接影響到?jīng)Q策的效果[1]，因此屬性的規(guī)范化技術(shù)是多屬性決策問(wèn)題的基礎(chǔ)。屬性之間一般都沒(méi)有統(tǒng)一的度量標(biāo)準(zhǔn)，并且還存在一定的矛盾性，即對(duì)各屬性的期望值是不同的甚至是相反的。具體來(lái)說(shuō)，一方面各屬性的單位不同、量綱不同、數(shù)量級(jí)不同；另一方面，屬性還可分為效益型和成本型等不同類(lèi)型。因此，對(duì)于一個(gè)已知決策矩陣的多屬性決策問(wèn)題，在求解各屬性權(quán)值及各備選資源綜合實(shí)力排序之前，都需要消除屬性的量綱、數(shù)量級(jí)和屬性類(lèi)型對(duì)決策結(jié)果的影響，也就是說(shuō)，需要對(duì)各屬性值進(jìn)行規(guī)范化處理。其實(shí)質(zhì)是利用數(shù)學(xué)變換把量綱、性質(zhì)各異的屬性值轉(zhuǎn)化為可以綜合處理的“量化值”。一般是把各屬性值統(tǒng)一變換到區(qū)間[0,1]上。規(guī)范化的目的在于獲得可比的尺度。

下面，再將如上提到的決策距陣和屬性類(lèi)型分別進(jìn)一步介紹。

屬性類(lèi)型一般有效益型、成本型、固定型、偏離型、區(qū)間型、偏離區(qū)間型等。實(shí)際中用得最多的屬性是效益型屬性和成本型屬性。以往的資源調(diào)度也常采用效益型和成本型兩種屬性類(lèi)型。效益型屬性是指屬性指越大越好的屬性；成本型屬性是指屬性值越小越好的屬性。它們都以最終處理后的數(shù)據(jù)大小來(lái)判斷數(shù)據(jù)優(yōu)劣，即數(shù)據(jù)值越大，數(shù)據(jù)質(zhì)量越優(yōu)，反之亦然。既然在同一個(gè)多屬性決策問(wèn)題中，對(duì)各屬性的期望值不同甚至相反，而最后都要以最終結(jié)果值的大小反映值的優(yōu)劣，則不可能用一個(gè)處理公式進(jìn)行統(tǒng)一處理，而應(yīng)該將各屬性按類(lèi)型進(jìn)行劃分，再施以不同的處理公式。在文章后續(xù)章節(jié)的介紹中，將用由0，1元素組成的Pflag向量來(lái)表示各屬性的類(lèi)型，屬性為成本型，對(duì)應(yīng)在Pflag中的元素為1；屬性為效益型，對(duì)應(yīng)在Pflag中的元素為0。Pflag向量長(zhǎng)度等于屬性的個(gè)數(shù)m。

2 決策矩陣的規(guī)范化方法

由于決策矩陣中各列分量的數(shù)值大小不一，因此，考慮數(shù)據(jù)處理的公平性和獨(dú)立性，需要在決策矩陣參與運(yùn)算之前將其進(jìn)行規(guī)范化處理。本節(jié)首先介紹三種規(guī)范化處理方法。

在資源調(diào)度等多屬性決策問(wèn)題中[2-5]，決策矩陣的規(guī)范化多采用標(biāo)準(zhǔn)0-1規(guī)范化處理和一般規(guī)范化處理方法。而在Web工作量描述中，聚類(lèi)算法在計(jì)算歐式距離前對(duì)原始數(shù)據(jù)進(jìn)行規(guī)范化處理時(shí)，常使用ZSCORE規(guī)范化處理技術(shù)[6]。文章將這種方法也引入到資源調(diào)度問(wèn)題中進(jìn)行多屬性決策前的矩陣預(yù)處理，并對(duì)該方法進(jìn)行了改進(jìn)。

2.1 標(biāo)準(zhǔn)0-1規(guī)范化處理方法

該方法的基本思想是將最好的屬性值規(guī)范化為1，將最壞的屬性值規(guī)范化為0，其余屬性值采用線形插值的方法得到規(guī)范化值。

1)效益型的決策屬性：將最大屬性值規(guī)范化為1，最小屬性值規(guī)范化為0，利用插值法得:

,i=1,…,n

(1)

2)成本型的決策屬性：將最小屬性值規(guī)范化為1，最大屬性值規(guī)范化為0，利用插值法得:

,i=1,…,n

(2)

Zij是規(guī)范化后的屬性值，其中

,。

在標(biāo)準(zhǔn)0-1規(guī)范化處理方法中，規(guī)范化后的屬性值都轉(zhuǎn)換到[0，1]閉區(qū)間，最優(yōu)的數(shù)值轉(zhuǎn)換為1，最劣的數(shù)值轉(zhuǎn)換為0，但變換前后的數(shù)值不成比例關(guān)系。由于它具有簡(jiǎn)便的變換式和良好的特性，使之成為目前多屬性決策及綜合評(píng)價(jià)中用得最多的規(guī)范化方法。

2.2 一般規(guī)范化處理方法

該方法的基本思想是將最好的屬性值規(guī)范化為1。與標(biāo)準(zhǔn)0-1規(guī)范化方法不同的是，對(duì)于效益型和成本型屬性，變換前后的屬性值成比例關(guān)系。

對(duì)于效益型的決策屬性的處理式是:

(3)

對(duì)于成本型的決策屬性的處理式是:

(4)

2.3 Z SCORE規(guī)范化處理方法

ZSCORE是利用了各個(gè)屬性測(cè)量值的平均值和標(biāo)準(zhǔn)差的一種變換，可用來(lái)避免因?qū)傩缘南鄬?duì)取值和范圍大不相同而導(dǎo)致結(jié)果自然增長(zhǎng)的問(wèn)題，變換結(jié)果使得參數(shù)與單位無(wú)關(guān)。對(duì)于一個(gè)給定參數(shù)的ZSCORE計(jì)算如下：

(5)

屬性類(lèi)型有成本型和效益型，不同的屬性有不同的量綱和單位，為了避免對(duì)后續(xù)決策計(jì)算帶來(lái)不良影響，在決策之前需要消去各屬性的量綱，即非量綱化，僅用數(shù)值的大小反映屬性值的優(yōu)劣。這樣，僅用(5)式對(duì)所有屬性進(jìn)行統(tǒng)一處理，就沒(méi)辦法滿(mǎn)足屬性多種類(lèi)型的需求，因此把(5)式根據(jù)成本型和效益型的屬性特征分別進(jìn)行改寫(xiě)。

對(duì)于效益型的決策屬性的處理式是：

(6)

對(duì)于成本型的決策屬性的處理式是：

(7)

這樣，無(wú)論是成本型屬性，還是效益型屬性，只需看計(jì)算后的結(jié)果即可做出決策判斷，結(jié)果越大說(shuō)明屬性值越優(yōu)。

3 實(shí)驗(yàn)與分析

本節(jié)將上節(jié)介紹的三種規(guī)范化方法作用于多屬性決策領(lǐng)域中的同一個(gè)資源調(diào)度實(shí)例的決策矩陣，最后通過(guò)實(shí)驗(yàn)數(shù)據(jù)進(jìn)行各方法間的分析比較。

3.1 實(shí)驗(yàn)簡(jiǎn)介

實(shí)驗(yàn)在Windows XP的操作系統(tǒng)環(huán)境下，使用Matlab 7.0數(shù)學(xué)軟件工具進(jìn)行設(shè)計(jì)和開(kāi)發(fā)。實(shí)驗(yàn)開(kāi)發(fā)所涉及的主要函數(shù)如下：

(1)標(biāo)準(zhǔn)0-1規(guī)范化處理函數(shù)Standlize(X,Pflag)

① 輸入：決策矩陣X，各屬性的標(biāo)志數(shù)組Pflag；

② 操作：以列為單位，對(duì)決策矩陣X的每一列向量求出最大值和最小值，分別保存至列最大值和最小值數(shù)組，然后按照公式(1,2)，對(duì)每列元素進(jìn)行計(jì)算；

③ 輸出：矩陣Z及程序運(yùn)行時(shí)間。

(2)一般規(guī)范化處理函數(shù)Standlize1(X,Pflag)

① 輸入：決策矩陣X，各屬性的標(biāo)志數(shù)組Pflag；

② 操作：以列為單位，求X矩陣每一列向量的最大和最小值，分別保存至列最大值和最小值數(shù)組，然后按照公式(3,4)，對(duì)每列元素進(jìn)行計(jì)算；

③ 輸出：矩陣C及程序運(yùn)行時(shí)間。

(3)ZSCORE規(guī)范化處理函數(shù)Zscore(X,Pflag)

① 輸入：決策矩陣X，各屬性的標(biāo)志數(shù)組Pflag；

② 操作：以列為單位，求X矩陣每列的平均值和標(biāo)準(zhǔn)方差，分別保存至列平均值和標(biāo)準(zhǔn)方差數(shù)組，然后按照公式(6,7)，對(duì)每列元素進(jìn)行計(jì)算；

③ 輸出：矩陣U及程序運(yùn)行時(shí)間。

3.2 舉例

設(shè)在某資源調(diào)度問(wèn)題中，有4個(gè)備選資源，即R=(R1,R2,R3,R4)，以時(shí)間、質(zhì)量、成本和服務(wù)4個(gè)屬性，即P=(Rt,Rq,Rc,Rs)來(lái)綜合考量各備選資源的整體實(shí)力。計(jì)算過(guò)程如下。

(1) 首先輸入決策矩陣X及屬性的標(biāo)志數(shù)組Pflag=[1 0 1 0]。X矩陣的橫向量為(Rt,Rq,Rc,Rs)，縱向量為(R1,R2,R3,R4) ，具體數(shù)值如圖1中所示。

(2) 經(jīng)過(guò)標(biāo)準(zhǔn)0-1規(guī)范化處理Standlize(X,Pflag)之后，得到矩陣Z，具體數(shù)值如圖1中所示。處理時(shí)間為0 s。

(3) 相同的輸入決策矩陣X及屬性標(biāo)志數(shù)組Pflag，經(jīng)過(guò)一般規(guī)范化處理Standlize1(X,Pflag)之后，得到矩陣C，具體數(shù)值如圖2中所示。處理時(shí)間為0 s。

(4) 相同的輸入決策矩陣X及屬性標(biāo)志數(shù)組Pflag，經(jīng)過(guò)Z-score規(guī)范化處理后，得到矩陣U，具體數(shù)值如圖3中所示。處理時(shí)間為0.07 s。

圖1 標(biāo)準(zhǔn)0-1規(guī)范化方法處理結(jié)果

3.3 分析與比較

通過(guò)上節(jié)的計(jì)算，分別得出標(biāo)準(zhǔn)0-1規(guī)范化說(shuō)明：以上的處理時(shí)間輸出格式采用系統(tǒng)默認(rèn)格式，僅保留6位小數(shù)，不過(guò)已足夠用于對(duì)這三種方法的分析和比較。

圖2 一般規(guī)范化方法處理結(jié)果

圖3 Z-score方法處理結(jié)果

方法，一般規(guī)范化方法及Zscore方法作用于同一決策矩陣X后的結(jié)果矩陣及所用的計(jì)算時(shí)間，以下將會(huì)從數(shù)據(jù)和時(shí)間兩方面對(duì)這三種規(guī)范化方法進(jìn)行分析比較。

3.3.1 規(guī)范化結(jié)果比較 表1和表2是使用三種方法成本型和效益型屬性進(jìn)行規(guī)范化后結(jié)果數(shù)據(jù)的比較。

表1 成本型屬性規(guī)范化結(jié)果比較

表2 效益型屬性規(guī)范化結(jié)果比較

標(biāo)準(zhǔn)0-1規(guī)范化處理后，X矩陣的每列值都處于0-1之間。對(duì)成本型QoS來(lái)說(shuō)，值越小處理后結(jié)果越大，對(duì)效益型QoS來(lái)說(shuō)，值越大處理結(jié)果越大。結(jié)果最小可到0，最大可到1，其余結(jié)果在0-1開(kāi)區(qū)間分布；

一般規(guī)范化處理后，X矩陣的每列值都也都處于0-1之間，但是不會(huì)出現(xiàn)0元素；

經(jīng)Zscore比例技術(shù)處理后，雖然結(jié)果分成本和效益兩類(lèi)也遵從上述的規(guī)律，但是每列的處理值中數(shù)值有正有負(fù)，而且每類(lèi)數(shù)據(jù)的最大和最小值相差結(jié)果大于1，數(shù)據(jù)不規(guī)律，對(duì)日后減法等操作帶來(lái)處理復(fù)雜度。

3.3.2 規(guī)范化處理時(shí)間比較 標(biāo)準(zhǔn)0-1規(guī)范化、一般規(guī)范化、Zscore規(guī)范化處理時(shí)間分別為0.000、0.000、0.070 s。

標(biāo)準(zhǔn)0-1規(guī)范化處理技術(shù)涉及到求每列數(shù)據(jù)的最小、大值，都可以用Matlab的內(nèi)部函數(shù)實(shí)現(xiàn)，接著作減法和除法運(yùn)算，從圖4中可以看出這些操作用時(shí)少，低于10-3數(shù)量級(jí)，因此整個(gè)算法的耗時(shí)為0 s；

圖4 standlize(X,Pflag)耗時(shí)分析

一般規(guī)范化處理技術(shù)涉及到求每列數(shù)據(jù)的最小、最大值，但較標(biāo)準(zhǔn)0-1規(guī)范化來(lái)說(shuō)，少了減法操作，從圖5中可以看到，這種算法處理的時(shí)間也很少，低于10-3數(shù)量級(jí)，算法的總耗時(shí)也為0 s；

圖5 standlize1(X,Pflag)耗時(shí)分析

Zscore比例技術(shù)涉及到求每列數(shù)據(jù)的平均值和標(biāo)準(zhǔn)差，雖然也由Matlab的內(nèi)部函數(shù)實(shí)現(xiàn)，但這兩個(gè)運(yùn)算的復(fù)雜度遠(yuǎn)遠(yuǎn)超過(guò)求最小、最大值的運(yùn)算方法，如圖6，它們的運(yùn)算時(shí)間都大于10-2數(shù)量級(jí)，因此消耗了算法的大部分時(shí)間。在本例中，Zscore處理時(shí)間為0.07 s；

圖6 Z-score(X,Pflag)耗時(shí)分析

綜上所述，不論從處理后的數(shù)據(jù)質(zhì)量還是從時(shí)間，標(biāo)準(zhǔn)0-1規(guī)范化和一般規(guī)范化的方法較Zscore來(lái)說(shuō)性能更優(yōu)，更適用于資源調(diào)度的計(jì)算工作。而標(biāo)準(zhǔn)0-1規(guī)范化和一般規(guī)范化處理的時(shí)間相差不大，數(shù)據(jù)元素也都在0和1之間，但標(biāo)準(zhǔn)0-1規(guī)范化后的矩陣每列必有一個(gè)0，這可以減輕后續(xù)計(jì)算的運(yùn)算量。所以標(biāo)準(zhǔn)0-1規(guī)范化處理方法為這三種資源調(diào)度決策矩陣的規(guī)范化方法中的最優(yōu)方法。

4 結(jié) 語(yǔ)

復(fù)雜分布式環(huán)境中的資源調(diào)度問(wèn)題大都涉及到多屬性決策問(wèn)題，而多屬性決策的基礎(chǔ)問(wèn)題是各屬性的量化問(wèn)題，即決策矩陣規(guī)范化問(wèn)題。對(duì)于此類(lèi)問(wèn)題，本文做了如下工作：

(1)集中討論和比較了三種規(guī)范化處理方法，分別是標(biāo)準(zhǔn)0-1規(guī)范化方法，一般規(guī)范化方法，以及z score規(guī)范化方法。

(2)對(duì)Zscore運(yùn)算式進(jìn)行了改進(jìn)，使之能適用于多屬性決策運(yùn)算。

(3)最后，以實(shí)驗(yàn)數(shù)據(jù)來(lái)對(duì)比分析這三種規(guī)范化方法在資源調(diào)度中的處理效果。實(shí)驗(yàn)結(jié)果表明，標(biāo)準(zhǔn)0-1規(guī)范化處理方法是在可歸屬為多屬性決策問(wèn)題的資源調(diào)度問(wèn)題中，用于矩陣規(guī)范化處理較理想的方法。

參考文獻(xiàn)：

[1] 張堯庭．指標(biāo)量化、序化的理論和方法[M]．北京：科學(xué)出版社，1999: 22-53.

[2] 劉麗蘭，余濤，施戰(zhàn)備．制造網(wǎng)格中基于服務(wù)質(zhì)量的資源調(diào)度研究[J]．計(jì)算機(jī)集成制造系統(tǒng)，2005，11(4): 475-480.

LIU Lilan, Yutao, SHI Zhanbei. Quality of service management system in manufacturing grid[J]. Computer Integrated Manufacturing Systems, 2005,11(4):475-480.

[3] TANG Lei ,YANG Zhiyi, YU Zhiwen,et al. A quality-driven algorithm for resource scheduling based on market model on grid [C]. The 2nd International Workshop on Advanced Distributed and Parallel Network Applications (ADPNA 2007), in conjunction with the 36th International Conference on Parallel Processing (ICPP 2007) USA: IEEE Computer Society Press, 2007: 9-14.

[4] WANG Yingming, PARKAN Celik. Multiple attribute decision making based on fuzzy preference information on alternatives: Ranking and weighting[J]. Fuzzy Sets and Systems, 2005, 153(3): 331-346.

[5] XU Zeshui. On multi-period multi-attribute decision making[J]. Knowledge-Based Systems, 2008, 21(2): 164-171.

[6] MENASCé Daniel A, ALMEIDA V A F. Capacity planning for Web performance: metrics, models, and methods [M]. New Jersey:Prentice Hall PTR Prentice Hall,Upper Saddle River, 1998: 250-262.