一種改進的有限期作業排序算法研究

摘要:提出了作業最晚運行次序的概念，改進算法的時間復雜度完全取決于排序算法的時間復雜度，并且改進算法可以直接得到最大效益作業子集的一種可行運行次序。

關鍵詞:有限期作業;貪心方法;作業最晚運行次序;排序

中圖分類號:TP301.6 文獻標識碼:A 文章編號:1672-3198(2010)02-0252-02

1 改進算法

1.1 算法思想

改進的有限期作業排序的貪心方法:取得最大效益的作業子集一定是運行作業數目最多的子集，在不考慮獲得最大效益的前提下，首先將n個作業按有限期從小到大排序，然后求出在一批作業中CPU最多能運行的作業數目m(m<=n)，利用m給已排好序的作業設置最晚運行次序(lateRunOrder<=m)。接著類似傳統算法將n個作業按效益值從大到小排序，定義一個能存儲m個Job對象的數組，先把效益值最大的作業放入數組中，然后按作業互不沖突的原則依次嘗試把作業放入數組中，只要數組中添滿了m個作業，其余未處理的作業都將被忽略，此時數組中存放的m個作業就是CPU處理該批作業能獲得的最大效益值。由于最晚運行次序是連續的，并且小于等于m，因此改進的算法節省了內存空間。

為了使算法能處理任意數量的作業，算法中使用了C++標準庫容器vector。算法抽象出兩個類:Job和JobHolder。在Job類中包含作業號(initJobNumber)、

作業效益值(profit)、作業截止期限(deadline)和作業最晚運行次序(lateRunOrder)。假設CPU時刻都在處理作業，一個挨一個地處理作業，則作業最晚運行次序指為了能夠獲得該作業的效益值CPU在一批給定的作業中最晚運行該作業的次序。例如某個作業的最晚運行次序等于n，則表示CPU最晚運行該作業的次序為n，但CPU可以安排該作業在n以前運行。JobHolder繼承于Job類，新增加一個bool類型的holder成員，JobHolder類對象用于存儲Job類對象，當有一個Job對象放入JobHolder類對象中時，holder被賦值為true。Job類和JobHolder類如下:

class Job{

public:

long initJobNumber;

long profit;

long deadline;

long lateRunOrder;

public:

Job():initJobNumber(0)，profit(0)，deadline(0)，lateRunOrder(0){}

Job(long _initJobNumber，long _profit，long _deadline，long _lateRunOrder=0)

:initJobNumber(_initJobNumber)，profit(_profit)，deadline(_deadline)，

lateRunOrder(_lateRunOrder){}

};

class JobHolder:public Job{

public:

bool holder;

public:

JobHolder():Job()，holder(1)

{}

void operator=(const Job job)

{initJobNumber=job.initJobNumber;

profit=job.profit;

deadline=job.deadline;

lateRunOrder=job.lateRunOrder;

}

};

1.2 求解n個作業中CPU最多能運行作業數目m

n個作業由于每個作業的期限值d是固定的，因此一個作業集中最多能運行的作業數目m是固定的。在不考慮獲得最大效益的前提下，首先將n個作業按deadline從小到大排序，假設CPU從t=0開始處理按作業期限值有序的作業集，從有序作業中取出第一個作業，如果它的期限值大于t，t加1，表明CPU已處理該作業，并且過了一個時間單位;如果該作業的期限值等于t，則t不加1，因為該作業已過期。然后按照此原則依次比較剩余的作業，比較完成后t的值就是在這批作業中CPU最多能處理的作業數目m。具體算法如下:

void sortByDeadline(vector* pData，int count)

{ int i，j;

int k;

Job* t;

for(i=0;i

k=i;

for(j=i+1;jdeadline>(*pData)[j]->deadline)k=j;

if(k!=i){t=(*pData)[i];(*pData)[i]=(*pData)[k];(*pData)[k]=t;}

}

}

long runMostJobNumber(vector* pVecPJob)

{ int t=0;

int i;

for(i=0;i<(*pVecPJob).size();i++)

if( t<(*pVecPJob)[i]->deadline )t++;

return t;

}

1.3 設置作業的最晚運行次序

作業最晚運行次序依賴于具體一個作業集合，同一個作業在不同作業集合中時其最晚運行次序值可能是不同的。如果一個作業在一個作業集中運行的次序大于它的最晚運行次序，那么無法獲得該作業的效益值，因為CPU運行到改該作業時作業已過期。根據m給每個作業設置CPU運行該作業的最晚次序(lateRunOrder)。作業集仍按deadline從小到大有序，將排列中最后一個作業的最晚運行次序設為m。然后從排列倒數第二個作業開始依次給剩下的作業設置最晚運行次序，作業的最晚運行次序按以下原則設置:對于任一對相鄰的兩個作業，如果前一個作業的期限值小于它后面作業的期限值，那么前一個作業的最晚運行次序等于它后面一個作業最晚運行次序減1，否則兩個作業的最晚運行次序相同。具體算法如下:

void setJobLateRunOrder(vector* pVecPJob，int mostJobNumber)

{ int i;

int lateRunOrder=mostJobNumber;

int s=(*pVecPJob).size();

((*pVecPJob)[s-1])->lateRunOrder=lateRunOrder;

for(i=s-2;i>=0;i--){

if(((*pVecPJob)[i])->deadline<((*pVecPJob)[i+1])->deadline ){

lateRunOrder--;

((*pVecPJob)[i])->lateRunOrder=lateRunOrder;

}

else ((*pVecPJob)[i])->lateRunOrder=lateRunOrder;

}

}

1.4 求解作業集的最大效益

定義一個能存儲m個Job對象的數組，數組初始化為空，即未保存任何作業對象。首先將作業集按效益值從大到小排序，然后按下述規則用m個Job對象把數組填滿:取有序排列中的第一個作業，試著將作業放入數組中，首先嘗試作業在數組中存放位置和該作業的lateRunOrder相同。如果第lateRunOrder數組元素沒有放入作業，則將作業放放在此第lateRunOrder數組元素中;如果第lateRunOrder數組元素中早有作業放入，則從數組的第lateRunOder-1個數組元素直到第1個數組元素反向查找作業在數組中的放入位置，如果能找到，就將作業放在首次發現的未放入作業的數組元素中，如果找不到就將該作業舍棄，然后開始查找下一個作業在數組中的存放位置，也就是首先試著將作業放入第lateRunOder-1個數組元素，如果該數組元素中沒有作業，那么作業就放入這個數組元素中，否則將作業放入它左邊的第1個空著的數組元素中。按著上述規則試著依次將作業放入數組中，只要數組中填滿m個Job對象，就停止比較其它作業能否放在數組中，剩余的作業全部被忽略，此時數組中存放的作業子集j就是CPU運行作業集能獲得最大效益的作業子集，并且數組中作業的存放次序就是CPU運行該子集的一種可行順序。之所以按上述規則將作業放入數組中，是因為作業運行地最晚次序是lateRunOrder，但作業可以在最晚運行次序之前運行。具體算法如下:

void sortByProfit(vector* pData，int count)

{ int i，j;

int k;

ob* t;

for(i=0;i

k=i;

for(j=i+1;jprofit<(*pData)[j]->profit)k=j;

if(k!=i){t=(*pData)[i];(*pData)[i]=(*pData)[k];(*pData)[k]=t;}

}

}

void findMaxProfitJobs(vector* pVecPJob，JobHolder* pJobHolders，long mostJobNumber)

{ int i;

int j;

int s=(*pVecPJob).size();

int flag=0;

for(i=0;i

for(j=(*pVecPJob)[i]->lateRunOrder-1;j>=0;j--)

if(pJobHolders[j].holder==1){

pJobHolders[j]=*(*pVecPJob)[i];

pJobHolders[j].holder=true;

flag++;

break;

}

}

2 算法證明

假設(0，1，……，i，n)表示一批作業，m表示該作業集最多能運行的作業數目。首先證明獲得最大效益的子集一定是包含m個作業的子集，用c表示選出作業子集的數目，當c>m時，c個作業不可能全部運行完，無法獲得效益;當c

3 時間和空間復雜度分析

改進的算法需要四步驟:(1)按作業的有限期排序;(2)求出作業集中最多可以運行作業的總數m，設置作業最晚運行次序;(3)按作業的效益值排序;(4)利用m求出最優解。因此改進的算法時間復雜度完全取決于排序算法的時間復雜度，以排序算法為例， T(n)=n2+n+n+n2+nm=2n2+2n+mn，因此算法時間復雜度O(n2)。如果使用快速排序法，算法平均時間復雜度O(nlog2n)。

由于在求最優解之前已求出最優解包含作業的總數m(m<=n)，因此算法的空間復雜度為m。

4 結語

提出了一個全新的概念-作業最晚運行次序，作業最晚運行次序依賴于具體一個作業集，同一個作業在不同作業集中時其最晚運行次序值可能是不同的。本算法對傳統算法最大的改進是獲得最大效益子集一定是運行作業最多的子集，在作業集中找出最多能運行作業的數目m，并設置每個作業的最晚運行次序(lateRunOrder)，利用作業最晚運行次序很容易判斷一個作業加入一個子集時該子集中的作業是否都能運行，并且可直接得出最優解子集的一種可行運行次序。

參考文獻

[1]夏建勛.帶有限期作業排序快速算法的另一種實現方法[J].孝感學院學報，2004，(03):86-89.

[2]余祥宣，崔國華，鄒海明.計算機算法基礎(第二版)[M].武漢:華中科技大學出版社，2000:71-72.