【多目標加工作業調度問題算法分析案例7700字】

多目標加工作業調度問題算法分析案例目錄TOC\o"1-3"\h\u2533多目標加工作業調度問題算法分析案例 1241551.1引言 1289321.2問題介紹 2118661.3基于中小規模問題的NSABC算法 3261361.3.1支配關系 3165261.3.2擁擠度計算 3310491.3.3精英策略 4202761.3.4算法框架 59701.4基于大規模問題的DS-LPT啟發式算法 6243101.5數值仿真實驗 8201871.1.1智能優化算法 8303071.1.2啟發式算法 11265801.6加工作業調度系統的設計與實現 13128871.6.1數據輸入 13126711.6.2運行結果 141.1引言在航空發動機的制造過程中，企業的優化目標往往不是單一的。這些優化目標包括降低能耗、減少在制庫存或者提高客戶的滿意度等，而這些目標之間往往是相互沖突的。例如，企業希望在最短的時間內按時生產出最多的商品，而時間和產量這兩個目標之間就是相互制衡的，縮短生產時間勢必會導致產量降低，反之亦然。在這個多目標問題中，無法使得每個子目標一起達到最優值，一個子目標的優化勢必會導致另一目標的惡化，因而只能調和所有的給定目標，使用折中方式優化每個子目標。相對于單目標問題最優解唯一的特點，多目標問題則需要求得問題的所有帕累托最優點。這個概念最早出現在經濟領域[58]，因意大利的著名經濟學家維弗雷多·帕累托而得名。帕累托最優指無論怎樣改變當前解，均無法找到所有目標全部優于當前解的狀態。多目標問題可以通過下述式子定義。(1.1)(1.2)(1.3)(1.4)多目標問題也可以簡單的將每個目標函數賦予權重進而轉化為單目標問題。(1.5)盡管如此，在賦予每個目標函數權重的過程中難免會出現各種問題。首先，待優化的多個目標之間往往沒有關聯，每個目標函數的標量范圍很可能差距過大。為了平衡各個目標間的關系，就需要將較小標量范圍的目標函數賦予較大的權值。當該目標函數出現較小偏差時，就會對整體目標函數產生較大影響。其次，權值的大小往往沒有實際意義，只能通過不斷實驗來找到一組合適的權值，整個過程耗時耗力。本章將針對雙目標的加工作業問題，目標函數分別為極小化兩個代理的最大完工時間和以及每個任務的平均完工時間，設計多目標智能優化算法與啟發式算法求解該問題。對于中小規模的問題，本文設計了一種基于非支配排序的NSABC算法求解該問題，并與求解多目標問題常用的NSDE算法進行了數值對比實驗。對于大規模問題，本文設計了一種高效的DS-LPT啟發式算法，盡可能的平衡兩個目標函數。并分別針對每個目標函數設計一個有效下界，驗證啟發式算法的收斂性。1.2問題介紹在多目標加工作業問題中，共有n個任務需在m臺設備上進行作業。這n個任務分屬于不同的代理商A和B，并有自己固定的加工順序。同時每個任務j需在其對應的釋放時間rj之后才可以開始作業。在任務作業的過程中，所有設備的作業過程均不可中斷。任務j在任意一臺設備上完成該道工序后，若下一道工序對應設備仍被其他任務占用，該任務將在緩沖區等待，直到被占用的設備達到可用狀態時才可進行作業。假設待處理任務的緩沖區是無限的，即不對緩沖區的容量進行考慮。本章將兩個代理商對應的最大完工時間和以及所有任務的平均完工時間作為優化目標，并給出該雙目標問題的帕累托解集。本章整數規劃模型中變量定義與約束部分與4.2.2節中的模型相同。在本章的多目標問題中代理商A和代理商B的優先級相同。由于本章問題為多目標加工作業問題，因此相對于單目標優化問題來說，本章的優化目標將會有所不同，具體的目標函數如下。(1.6)(1.7)1.3基于中小規模問題的NSABC算法1.3.1支配關系對于多目標優化問題來說，在算法的運行過程中，若種群中隨機兩個個體Xi和Xj滿足任意一個目標函數均有的條件，或者至少存在一個目標函數，使得，并且同時滿足其他目標函數，則稱該個體Xi支配個體Xj。以此類推，當前種群中所有的非支配解就構成了非支配解集，即此時的帕累托解集。在當前種群中，如果找不到其他個體Xj可以支配個體Xi，那么個體Xi就是當前種群的非支配解。在完成種群更新過程后，最終所有的非支配解集合就構成了該多目標問題的帕累托解集。在迭代過程中，需要將種群中的所有個體賦予支配等級Rank用于隨后的精英選擇過程。以當前種群中處在帕累托前沿面的個體為基準，將其Rank值設定為1，即種群中不存在其他個體可以支配該個體。設定完畢后，將當前種群中Rank值為1的個體移除，重新進行確定新的支配關系，并找出該狀態下的帕累托解集。同時將更新后解集中的所有前沿面個體Rank值設定為2，循環往復，直到得出種群中所有個體的Rank等級。圖1.1為種群個體Rank等級的示意圖。該圖中，兩個目標均為極小化問題。圖1.1種群個體Rank等級示意圖Fig.1.1SchematicdiagramofindividualRankofpopulation1.3.2擁擠度計算在確定了所有個體的Rank值之后，為了進一步確保精英選擇過程中保留較為優秀的父代個體，使用擁擠度來衡量同一等級間個體的質量好壞。多目標問題的帕累托解集不僅需要確保解的數量，同時也要衡量解集中解的離散程度。擁擠度可以很好的反映每個解之間的距離關系，擁擠度越小，則說明解集中的解越密集，反之則說明該解集中的解較為廣泛。擁擠度需要對種群中所有個體的每個目標函數進行升序排序。對于每個目標函數，邊界解（即每個目標函數的最大值與最小值）的擁擠度為無窮大。其它解的擁擠度則與其相鄰解有關，為其最近兩個鄰解進行歸一化處理后的函數絕對差值。每個目標函數在計算擁擠度時都會進行歸一化處理。圖1.2為計算擁擠度的實例。在圖1.2中，黑色框線的邊界點即為個體i的兩個相鄰解。擁擠度計算的具體步驟如下。初始每個個體的擁擠度di為0。將種群中所有個體基于每個目標函數進行升序排序，并記錄于。令邊界對應個體di的擁擠度記為無窮大。對其他個體進行擁擠度計算，。圖1.2種群個體擁擠度示意圖Fig.1.2Schematicdiagramofindividualcrowdingdegreeofpopulation1.3.3精英策略在經過支配排序與擁擠度的計算之后，種群中的任意兩個個體Xi和Xj都可根據上述屬性進行優劣比較。若Xi處于非支配層，即Xi的Rank值大于Xj，則個體Xi相對于個體Xi較優。如果二者Rank值相同，則比較他們的擁擠度數值，擁擠度較大的個體較優，即id>jd。精英選擇策略可以將種群中的優秀個體保留下來，作為新一代的父代個體，進而提高子代解的質量，同時也確保了當前種群中的最優解不會丟失。精英選擇過程首先將父代種群Pd與子代種群Qd合并成新的種群Rd，此時Rd種群的大小為2n。合并完成后對Rd中個體進行Rank等級以及擁擠度計算。計算完畢后按Rank等級從小到大的順序以此將個體添加到新父代種群Pd+1中。當某個Rank等級添加完畢后超出Pd+1規模時，按該Rank等級擁擠度大小重新添加，直到填滿新父代種群Pd+1。精英選擇過程如圖1.3所示。圖1.3精英選擇過程示意圖Fig.1.3Schematicdiagramofeliteselectionprocess1.3.4算法框架在多目標問題中，由于各目標之間往往相互約束，因此需要將單目標的人工蜂群算法的鄰域結構進行調整。本章根據多目標問題的特點，對已有鄰域搜索方式進行改進以適用多目標問題。在保留交換、前插、保留等基本結構不變的前提下，根據目標函數的性質，引入LPT以及SPT啟發式思想，豐富鄰域結構。LPT策略在解序列長度內隨機生成兩個不同的數和，并令大于。將到之間編碼按對應工序的處理時間進行降序排序，即LPT規則，生成一個新的解序列。SPT策略在解序列長度內隨機生成兩個不同的數和，并令大于。將到之間編碼按對應工序的處理時間進行升序排序，即SPT規則，生成一個新的解序列。在單目標問題中，人工蜂群算法通過輪盤賭的方式選擇搜索蜜源。而在多目標問題中，由于各目標函數之間無法進行線性歸一化，因此需要更改選擇方式。在NSABC算法中，跟隨蜂通過二進制擇優的方法，隨機選擇某個個體進行搜索，搜索過程與單目標問題類似。在偵察蜂搜索過程中，單目標問題對當前最好解進行10次偵察蜂搜索。而在多目標問題中，則對當前帕累托解集中所有個體進行10次偵察蜂搜索。完整的NSABC算法流程由如下偽代碼給出。NSABC算法偽代碼1開始2;3初始化蜜源列表Ps，進行快速非支配排序；4；5Whileτ<geneartiondo6Forn=1topopnum7對Ps中個體進行搜索過程8將當前蜜源列表記為Qs9Endfor10合并兩個蜜源列表Ps和Qs記為Rs11對新蜜源列表Rs進行快速非支配排序，相同等級個體記為Fi12對相同Rank等級個體進擁擠度計算，并按數值大小進行升序排序13Fori=1toRANKdo14IfPs+1+Fi<=popsize15將Fi的個體全部并入新的蜜源列表Ps+1中；16Else17計算Fi中個體的擁擠度并按照非降序排序，并將新的父代Ps+1中的個體數補全至popsize18Endif19Endfor20s=s+121Endwhile22返回帕累托解集F23End1.4基于大規模問題的DS-LPT啟發式算法(1)DS-LPT啟發式算法流程在多目標的加工作業問題中，在優化每個代理商的最大完工時間和這一目標函數時，將勢必會導致另一目標函數的惡化。因此本節將結合上述兩個不同目標對應的啟發式算法思想，設計了一種DS-LPT啟發式算法。在DS-LPT啟發式算法中使用任務的總剩余處理時間來確定當前設備進行作業的任務。若當前任務為最后一道工序，則搶占該設備，優先進行加工。該啟發式算法思想可以被描述為：任務i在調度過程中的任意時間點到達，若其工序對應的設備可用則立即開始作業。若該設備被占用，則該設備完成當前工序后，若可處理任務數大于1，根據所有任務的已完成工序情況及處理時間來決定排序。若存在某個任務當前設備為最后一道工序則優先選擇。若不存在該任務，則選擇當前剩余總處理時間最大的任務進行排序。在滿足上述情況下，若仍存在多個處理時間相同的任務，則根據給定任務編號從小到大依次排序。下面給出一個設備數為3，任務數為4的DS-LPT啟發式算法實例。該例子中任務的處理時間，釋放時間與工序則分別由如下矩陣給出。在該例中，J1和J2仍為代理商A所屬任務，J3和J4則對應B代理商所屬任務。圖1.4為該例子對應的最終調度甘特圖。該甘特圖對應的A、B代理的完工時間和為55，所有任務的平均完工時間則為21.75。圖1.4DS-LPT啟發式算法甘特圖Fig.1.4GanttchartofDS-LPTheuristicalgorithmDS-LPT啟發式算法框架DS-LPT啟發式算法的具體過程由如下偽代碼給出。DS-LPT啟發式算法偽代碼1開始2Forj=1todo3If當前只有一個任務j可被處理4將該任務j的當前工序安排到所對應的設備m上，更新任務j當前工序對應設備上的完工時間Cm,j，當前設備m處理過的任務數加15Endif6If當前設備m有多個任務可被處理7首先考慮是否存在最后一道工序的任務。若存在該類任務，則選擇處理時間最長的任務j。若無該類任務則記錄當前設備待處理任務的剩余處理時間，選擇剩余處理時間最長的任務j。若此時仍存在多個處理時間相同任務，則選擇任務編碼最小的任務j。更新任務j當前工序對應設備上的完工時間Cm,j，當前設備m處理過的任務數加18Endif9Endfor10返回以及11結束1.5數值仿真實驗本章實驗算法均由C++語言編寫，CodeBlocks編譯。實驗所用環境的操作系統為WindowsServer2016標準版。服務器CPU型號為Inter(r)Xeon(r)Gold6278CCPU@2.60Ghz2。系統的運行內存為8GB。在本節的數值實驗中，A代理的任務數仍為總任務數的30%至50%。1.1.1智能優化算法本節將通過NSABC算法與NSDE算法的數值仿真實驗來驗證算法求解多目標加工作業問題的能力。數值實驗中設備數m={3,5,8}，任務數n={30,50,80,100}。處理時間與釋放時間仍為U(1,10)與U(0,3n)的離散均勻分布。在單目標問題的實驗分析過程中，可以直接將目標函數值進行比較。而在多目標問題中，由于各目標之間相互獨立，因此無法進行簡單的數值比較。本節將使用一些針對多目標問題的評價指標來衡量算法性能。在數值實驗中，NP為最終帕累托解集中解的個數，該指標可以直觀的反應解的廣泛性。為了驗證最終解的質量，則使用C-metric指標比較兩種算法間的支配關系。該指標的計算方法如下。(1.8)其中A，B為待比較算法，|A|表示該算法中最終解集解的個數。a，b分別代表該算法得到的帕累托解集中的某個解。表示對于A算法中的某個解a，在B算法中存在a可支配的解。該指標的取值范圍為[0，1]，同時。0表示A算法中的所有解均無法支配B算法得到的解。該指標數值越大，則表明A算法得到的解可支配B算法的比值越大。D-metric指標衡量了算法所獲得最終解集的均勻性，該指標的計算方法如下。(1.9)其中為算法獲得該問題的帕累托解集，為除去當前解之外的其余帕累托解對應集合，表示解集中任意解v到其余解的歐氏距離。超體積指標HV為算法獲得的帕累托解集和參照點所圍目標空間區域的超立方體體積。該指標同時衡量了解集的收斂性與多樣性。該指標的數值越大，則說明算法的綜合性能越好。HV的計算方法如下。(1.10)該式中，表示勒貝格測度，用以計算超立方體體積。為帕累托解集中解的個數，vi表示參照點與解集中第i個解所圍成的超立方體體積。在本章對應的二維優化問題中，首先將帕累托解集中的所有解根據第一維目標函數值進行降序排序，則該超立方體體積即排序后相鄰解在平面直角坐標系中根據兩個目標函數值所圍城的平面面積。針對多目標問題，正交實驗的主效應值則為該參數組合下獲得的帕累托解個數占最終解集的百分比。根據正交實驗獲得的人工蜂群算法參數為：鄰域列表長度為15；鄰域搜索次數為25。不同設備數與任務數的組合均生成十組數據。每組數據則進行5次的獨立重復實驗來減少隨機誤差。實驗結果如表1.1所示，實驗數據為對應問題規模的十組數據均值。數據表中，為了防止HV指標一列數據差異過大，使用了對數歸一化的方法。由于多目標優化問題相對于單目標問題更加復雜，因此智能優化算法在求解時有很強的隨機性，進而導致NP指標在不同規模上的波動性較大。但從總體上看，兩種算法在求解不同規模的問題時均在合理范圍內上下浮動，因此問題規模對該指標影響不大。從均值上看，NSABC算法每次可以生成2.52個解，NSDE算法該指標則為2.55。盡管NSABC算法解的個數較小，但是差距也微乎其微。在衡量帕累托解集質量的指標C-metric上可以看出，NSABC算法取得了壓倒性的優勢。C(NSABC,NSDE)在所有規模上均大于C(NSDE,NSABC)。同時當問題規模擴大時，C(NSDE,NSABC)有逐漸減小的趨勢，這說明NSDE算法隨著問題規模的擴大，解決多目標加工作業問題的能力相對于NSABC算法有所下降。從該指標均值來看，C(NSABC,NSDE)為0.917，而NSDE算法對應的數值僅為0.225。這表明NSABC算法所獲得最終解的質量更高。這是因為NSABC算法的鄰域搜索過程融合了加工作業問題的性質，相對于NSDE算法，搜索效率更高，得到較好解的幾率也就更大。從均勻性指標D-metric來看，NSABC算法在10個問題規模中的數值較小，占到了所有規模總數的83.3%。同時從指標均值看，NSABC算法為9.613，也小于NSDE算法的10.401。這說明NSABC算法在帕累托解集質量較好的前提下，最終解集內的解分布較為均勻。而從綜合性評價指標HV來看，NSABC算法也在10個問題規模上占優，同時均值也要優于NSDE算法。結合上述指標來說，NSABC算法無論是從綜合評價上來看，還是解的質量與解集均勻性來看，均優于NSDE算法。僅在最終解個數NP這一指標上略低于NSDE算法。盡管如此，該指標數值差距也不足2%。因此可以說明，在解決多目標加工作業問題上，NSABC算法相對于NSDE算法的求解性能更優。表1.1多目標加工作業智能優化算法結果Table1.1Resultofintelligentalgorithmsformulti-objectivejobshop問題規模NPC-metricD-metricHVNSDENSABCNSDENSABCNSDENSABCNSDENSABC3*3070.947.154.421.851.673*5000.918.167.426.297.303*8030.897.9310.306.437.763*10080.8913.8212.917.328.565*3090.868.326.541.526.065*502.039.338.771.746.295*8030.889.858.027.797.945*10070.9613.4210.867.557.128*3020.967.566.726.106.198*503.058.619.606.496.918*8080.9010.9310.026.917.348*10070.9616.4814.587.638.17Ave2.552.520.2250.91710.4019.6136.7067.2401.1.2啟發式算法本節數值實驗將驗證所提出的DS-LPT算法在求解大規模多目標加工作業問題時的性能。數值實驗中，設備數m={3,5,8}，任務數n={100,200,500,800,1000,1500}。任務的處理時間，釋放時間與工序的生成方式與4.1.2節中DA-LPT啟發式算法的數值實驗保持一致。與單目標問題的啟發式算法數值實驗不同之處在于，在本節的數值實驗中將會分別與每個目標函數對應的下界進行對比。本章多目標問題的兩個目標下界首先均松弛掉工序約束及設備運行時不可中斷約束。在松弛掉該約束的基礎上針對每個代理完工時間和目標函數使用LPT規則，所有任務的平均完工時間則使用SPT規則進行調度排序。DS-LPT啟發式算法得到的目標函數值記為Obj，每個目標函數的下界值為LB，同樣使用GAP指標來評價啟發式算法的性能。表1.2多目標均勻分布處理時間實驗結果Table1.2Multi-objectiveexperimentresultinuniformdistribution問題規模m=3m=5m=8f1f2f1f2f1f2n=10031.36%20.08%41.41%34.64%57.94%53.48%n=20031.54%19.67%38.30%30.28%44.36%34.51%n=50031.79%17.75%31.60%21.64%40.19%30.69%n=80030.36%17.98%32.84%21.33%37.34%27.77%n=100029.79%18.02%32.04%23.55%31.41%28.15%n=150029.91%17.16%31.12%22.47%34.10%26.61%表1.3多目標正態分布處理時間實驗結果Table1.3Multi-objectiveexperimentresultinnormaldistribution問題規模m=3m=5m=8f1f2f1f2f1f2n=10034.33%23.66%42.65%32.31%62.75%54.04%n=20032.62%22.75%37.04%26.72%44.62%31.85%n=50033.55%20.17%36.29%27.72%41.79%29.65%n=80032.76%18.69%34.82%26.52%36.90%30.06%n=100031.85%19.85%33.02%21.02%31.82%30.04%n=150031.29%17.96%32.91%23.23%31.19%27.46%表1.2和1.3分別為均勻分布處理時間及正態分布生成處理時間下的實驗結果。其中f1對應為每個代理完工時間和目標函數的實驗結果。f2則對應所有任務平均完工時間的實驗結果。實驗結果表明，無論處理時間服從均勻分布或是正態分布，盡管實驗結果隨著問題規模的改變略有波動，但每個目標函數對應的GAP值隨任務數增大而減小的趨勢還是十分明顯的。這說明本章提出的DS-LPT啟發式算法適用于求解大規模的多目標加工作業問題。以均勻分布處理時間，設備數為3的情況為例，每個代理完工時間和的目標函數GAP值從100任務數的31.36%下降至1500任務數時的29.91%。而相對應所有任務的平均完工時間目標函數則從100任務數的20.08%下降至1500任務數時的17.16%。而當正處理時間服從正態分布時，設備數為5的情況為例，每個代理完工時間和一列的GAP值從100任務數的42.64%下降到1500任務數時的32.91%。所有任務的平均完工時間的一列則從100任務數的32.31%下降到1500任務數時的23.23%。為了更直觀的展現實驗數據所呈現的規律，圖1.5為均勻分布處理時間情況下兩個目標函數對應的實驗結果折線圖。圖1.6則為正態分布處理時間情況下不同目標函數的GAP值變化情況。從圖1.5和1.6可以看出，盡管偶爾出現數據波動的情況，但GAP值總體的下降趨勢仍十分明顯。處理時間服從不同分布時的實驗規律也大致相同。同時可以看出，盡管數據總體呈現下降趨勢，但相比與