有期限的作業(yè)調(diào)度算法

1、有期限的作業(yè)調(diào)度算法有期限的作業(yè)調(diào)度算法一、典型算法貪心算法是以局部最優(yōu)為原則通過一系列選擇來得到問題的一個最優(yōu)解它所做的每一個選擇都是當(dāng)前狀態(tài)下某種意義上的最佳選擇.貪心算法適合于解決這樣的問題:局部的最優(yōu)解能夠?qū)е伦罱K結(jié)果的最優(yōu)解。“有限期作業(yè)安排問題”描述如下:有n個任務(wù)J1J2...Jn每個任務(wù)Ji都有一個完成期限di若任務(wù)Ji在它的期限di內(nèi)完成則可以獲利Ci(1[i[n)問如何安排使得總的收益最大(假設(shè)完成每一個任務(wù)所需時間

2、均為一個單位時間).這個問題適合用貪心算法來解決貪心算法的出發(fā)點(diǎn)是每一次都選擇利潤大的任務(wù)來完成以期得到最多的收益但是對于本問題由于每一個任務(wù)都有一個完成的期限因此在任務(wù)安排過程中除了考慮利潤C(jī)i外還要考慮期限di.（一）算法描述1假設(shè)用數(shù)組J存儲任務(wù)用數(shù)組C存儲利潤用數(shù)組d存儲期限用數(shù)組P存儲安排好的任務(wù).按照利潤從大到小的次序調(diào)整任務(wù)的次序：對n個任務(wù)J1J2...Jn進(jìn)行調(diào)整使其滿足C1≥C2≥…≥Cn.2將排序后的任務(wù)順次插入輸

3、出數(shù)組P.A)任務(wù)J[1]排在P[1]B)若已經(jīng)優(yōu)先安排了k個任務(wù)則它們滿足d[P[i]]≥i(1≤i≤k)即利潤較高的k個任務(wù)能夠在它們的期限內(nèi)完成.那么對于第k1個任務(wù)J[k1]顯然C[k1]≤C[i](1≤i≤k)比較d[k1]和d[P[k]]:a)若d[k1]大于d[P[k]]那么將它排在第k1位(P[k1]←J[k1])b)若d[k1]小于等于d[P[k]]那么J[k]能否插入需比較k和d[P[k]]而定:i)若k等于d[P[

4、k]](其第k個任務(wù)已經(jīng)排在可以滿足的最遲時間)那么因?yàn)镃k≥Ck1只好放棄任務(wù)J[k1]ii)若k小于d[P[k]](表示第k個任務(wù)還有推后的余地):若d[k1]=k將第k個任務(wù)后移一位(P[k1]←P[k])將第k1個任務(wù)排在第k位(P[k]←J[k1]).若d[k1]=d[i])if(d[P[r]]rh)P[h1]=P[h]kP[r1]=iF(j)←F(l)endifrepeatendFJS（三）算法分析在1中對X=x1x2…xn

5、按pi的非增序重新排序若用快速排序法其平均時間復(fù)雜度為o(nlogn)在2中考察每一個xi1≤i≤n需調(diào)用一次Find總共調(diào)用Find的次數(shù)≤n總共調(diào)用Union的次數(shù)1≤b≤n.所以其時間復(fù)雜度近似于o(nlogn).綜合以上分析無論采用什么排序算法整個有限期作業(yè)調(diào)度算法其時間復(fù)雜度不低于o(nlogn)三改進(jìn)算法（一）改進(jìn)策略典型算法利用優(yōu)先策略很好的解決了有限期作業(yè)安排問題。但由于采取順序查找方式定位平均查找長度較大并且需要進(jìn)行移

6、動操作效率較低.改進(jìn)算法的基本思想是:對每一個任務(wù)Ji(1≤i≤n)來說其首選插入位置k為其滿足期限要求的最遲時間(即k=di).如果Pk空閑則將其插入否則說明已有一利潤更大的任務(wù)安排在此應(yīng)向前搜索(因?yàn)橹挥邪才旁谄谙迌?nèi)才能獲利)在搜索過程中找到空閑位就將其插入若搜索結(jié)束仍未找到有空閑位則將任務(wù)Ji舍去.設(shè)已安排任務(wù)集合SP=J1J2…Ji1當(dāng)前任務(wù)為Ji未安排任務(wù)集合SJ=Ji1Ji2…Jn.若任務(wù)Ji能夠插入到集合SP中對于Ji∈S

7、J必有Ci≥Cj且Ji處在其期限的邊界位置所以能夠保證Ji不再被移動若插入失敗對于Ji∈SP必有Cp≥Ci所以任務(wù)Ji必被舍棄.通過縮小搜索空間來進(jìn)一步優(yōu)化算法.設(shè)置左邊界指針h用以紀(jì)錄搜索終止位置其初值為1.當(dāng)某個任務(wù)Ji(1≤i≤n被放棄時則說明在輸出數(shù)組P的前di個節(jié)點(diǎn)都已經(jīng)被安排則以后沒有必要再次搜索所以下次搜索的終點(diǎn)為di1(即h←di1).設(shè)置右邊界指針t用以標(biāo)識當(dāng)前任務(wù)Ji的最優(yōu)搜索起始位置初始值為n.對于任務(wù)Ji來說其最

8、大安排期限不可能大于n所以若存在din則令其插入預(yù)選位置k為t同時修改t.（二）算法描述1假設(shè)用數(shù)組J存儲任務(wù)用數(shù)組C存儲利潤用數(shù)組d存儲期限用數(shù)組P存儲安排好的任務(wù)。按照利潤從大到小的次序調(diào)整任務(wù)的次序:對n個任務(wù)J1J2...Jn進(jìn)行調(diào)整使其滿足C1≥C2≥...≥Cn.2將排序后的任務(wù)順次插入輸出數(shù)組P.A)對t和h設(shè)初值:h=1t=nB)令任務(wù)J[i]的首選插入位置k為d[i]C)插入過程:i)若k小于h則放棄J[i](因?yàn)榍癶