周建濤，陸海燕，葉新銘

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

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

1 背景知識

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

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

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

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

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

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

在資源調(diào)度等多屬性決策問題中[2-5]，決策矩陣的規(guī)范化多采用標(biāo)準(zhǔn)0-1規(guī)范化處理和一般規(guī)范化處理方法。而在Web工作量描述中，聚類算法在計算歐式距離前對原始數(shù)據(jù)進(jìn)行規(guī)范化處理時，常使用ZSCORE規(guī)范化處理技術(shù)[6]。文章將這種方法也引入到資源調(diào)度問題中進(jìn)行多屬性決策前的矩陣預(yù)處理，并對該方法進(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)系。由于它具有簡便的變換式和良好的特性，使之成為目前多屬性決策及綜合評價中用得最多的規(guī)范化方法。

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

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

對于效益型的決策屬性的處理式是:

(3)

對于成本型的決策屬性的處理式是:

(4)

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

ZSCORE是利用了各個屬性測量值的平均值和標(biāo)準(zhǔn)差的一種變換，可用來避免因?qū)傩缘南鄬θ≈岛头秶蟛幌嗤鴮?dǎo)致結(jié)果自然增長的問題，變換結(jié)果使得參數(shù)與單位無關(guān)。對于一個給定參數(shù)的ZSCORE計算如下：

(5)

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

對于效益型的決策屬性的處理式是：

(6)

對于成本型的決策屬性的處理式是：

(7)

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

3 實驗與分析

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

3.1 實驗簡介

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

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

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

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

③ 輸出：矩陣Z及程序運行時間。

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

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

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

③ 輸出：矩陣C及程序運行時間。

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

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

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

③ 輸出：矩陣U及程序運行時間。

3.2 舉例

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

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

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

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

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

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

3.3 分析與比較

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

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

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

方法，一般規(guī)范化方法及Zscore方法作用于同一決策矩陣X后的結(jié)果矩陣及所用的計算時間，以下將會從數(shù)據(jù)和時間兩方面對這三種規(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之間。對成本型QoS來說，值越小處理后結(jié)果越大，對效益型QoS來說，值越大處理結(jié)果越大。結(jié)果最小可到0，最大可到1，其余結(jié)果在0-1開區(qū)間分布；

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

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

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

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

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

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

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

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

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

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

4 結(jié) 語

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

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

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

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

參考文獻(xiàn)：

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

[2] 劉麗蘭，余濤，施戰(zhàn)備．制造網(wǎng)格中基于服務(wù)質(zhì)量的資源調(diào)度研究[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.