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

2、均為一個(gè)單位時(shí)間).這個(gè)問(wèn)題適合用貪心算法來(lái)解決貪心算法的出發(fā)點(diǎn)是每一次都選擇利潤(rùn)大的任務(wù)來(lái)完成以期得到最多的收益但是對(duì)于本問(wèn)題由于每一個(gè)任務(wù)都有一個(gè)完成的期限因此在任務(wù)安排過(guò)程中除了考慮利潤(rùn)C(jī)i外還要考慮期限di.（一）算法描述1假設(shè)用數(shù)組J存儲(chǔ)任務(wù)用數(shù)組C存儲(chǔ)利潤(rùn)用數(shù)組d存儲(chǔ)期限用數(shù)組P存儲(chǔ)安排好的任務(wù).按照利潤(rùn)從大到小的次序調(diào)整任務(wù)的次序：對(duì)n個(gè)任務(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個(gè)任務(wù)則它們滿足d[P[i]]≥i(1≤i≤k)即利潤(rùn)較高的k個(gè)任務(wù)能夠在它們的期限內(nèi)完成.那么對(duì)于第k1個(gè)任務(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個(gè)任務(wù)已經(jīng)排在可以滿足的最遲時(shí)間)那么因?yàn)镃k≥Ck1只好放棄任務(wù)J[k1]ii)若k小于d[P[k]](表示第k個(gè)任務(wù)還有推后的余地):若d[k1]=k將第k個(gè)任務(wù)后移一位(P[k1]←P[k])將第k1個(gè)任務(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中對(duì)X=x1x2…xn

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

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

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

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