久久精品国产69国产精品亚洲_日韩欧美亚洲一区_免费观看污网站_欧美在线一

隨著現代物流技術的發展,自動化倉儲系統在生產和流通領域得到了越來越廣泛的應用。自動化倉儲系統的管理技術,特別是調度技術日益成為自動化倉儲系統的關鍵技術之一。一般任務調度算法有2種:一種是累積一定任務后的統一調度,稱為靜態調度;另一種是調度安排隨著新任務的進入而改變,稱為動態調度。本文提出的算法主要解決大型倉庫中運輸車輛的靜態任務調度問題。

任務調度的目標是把任務分配到各被調車輛上,安排車輛的執行次序,使其在滿足約束前提下完成時間最短。任務調度問題是經典的NP-Hard問題,為解決這一問題許多學者提出了多種啟發式調度算法,例如:模擬退火算法、蟻群調度算法、BDCP調度法等[1,2]。遺傳算法(genetic algorithm,GA)因其可比其他調度算法獲得更好的解,而被應用得最多的。特別是,如果把其他算法的解作為遺傳算法初始群中的個體,往往能獲得更好的解,缺點是遺傳算法執行時間比其他調度算法長得多[3,4]。

本文是在一種基于遺傳算法的倉儲車輛調度方法的啟發下[5,6],提出了一種基于貪心算法和遺傳算法的倉儲車輛調度算法。不僅克服了遺傳算法在任務調度上的編碼限制,而且貪心算法的加入使得融合算法性能大大提高。此算法還可以應用在多任務多處理器求最短完成時間的靜態調度方面。

倉儲車輛調度屬于多任務多處理器調度的一種,可分為任務分配和任務排序兩部分。此前已有學者采用遺傳算法解決該問題。該調度方法編碼復雜,并且由于其遺傳算法的交叉和變異過程極易產生非可行解的個體,這些個體經修正后隨機性降低,算法的全局搜索能力大大減弱。本文的算法采用遺傳算法優化任務分配,采用貪心算法優化任務排序。貪心算法的加入不僅使得遺傳算法在個體編碼簡化和運行時間縮短,同時排除了不可行解的出現,并增強了全局搜索能力。

貪心算法是一種常用的求解最優化問題的簡單、迅速的方法。貪心算法總是做出在當前看來最好的選擇,它所作的每一個選擇都是在當前狀態下某種意義的最好選擇,即貪心選擇,并希望通過每次所作的貪心選擇最終得到問題最優解[7]。貪心算法是一種快速簡易的求解旅行商問題(traveling salesman problem,TSP)的方法[8,9],其求解的基本思想是優先選擇當前點的最短邊。每次選擇邊的規則為

1)不會引起頂點度數大于等于3;

2)除非選取的邊為最后一條邊,所選取的邊不應形成回路。

本文貪心算法是當每輛車分配到任務后,對任務執行的先后進行排序,獲得單個車輛完成任務的最優解。單車輛的任務排序可視為一種TSP。經任務分配后,單車輛任務量不大,即TSP中途經點較少的情況下,貪心算法十分適用此排序問題。

遺傳算法是一種通過模擬自然進化過程,搜索最優解的方法,具有隱式并行性和很好的全局尋優能力。遺傳算法基本操作過程如圖1所示,其構成要素主要包括計算適應度、選擇算子、交叉算子和變異算子[10]。

圖1 遺傳算法基本操作流程Fig 1 Basic operation flow chart of genetic algorithm  下載原圖

本文采用遺傳算法尋求最優的任務分配方式,個體的基因型僅表示調度方法的任務分配。當判定個體適應度時,根據分配的任務采用貪心算法依次求得每輛車的執行時間。使用遺傳算法的好處在于,無論初始化、交叉、變異得到的基因型都不會存在不可行解,確保了隨機性和全局搜索能力。

本文的算法是以遺傳算法為框架,應用貪心算法簡化其編碼復雜度和計算適應度。最優解的求解過程依賴于遺傳算法。遺傳算法實現流程如圖2所示。計算適應度環節主要使用貪心算法,對每輛車分配的任務進行查表的方式獲得執行時間最短的任務排序,同時獲得并記錄其個體代表的調度方案的執行時間,從而求得個體適應度。

圖2 遺傳算法實現流程Fig 2 Realization flow chart of genetic algorithm  下載原圖

遺傳算法在編碼設計中常采用二進制編碼、格雷碼和浮點編碼等。本文采用整數編碼,所需調度任務數為Nt,可調度車輛數為Nv。個體的染色體可編碼為:長度Nt位,每位Nv種基因型。將所有任務編號為0,1,2,…,(Nt-1),車輛編號為0,1,2,…,(Nv-1)。例如:有8項運輸任務和4輛可調度車,每個個體編碼為一個8位字串x∈{0,1,2,3},其中每位有4種編碼選擇。個體型與對應分配方式如表1。

表1 8任務4車輛編碼示例Tab 1 Coding example of 8 tasks of 4 vehicles  下載原圖

表1 8任務4車輛編碼示例Tab 1 Coding example of 8 tasks of 4 vehicles

每個個體代表一個調度方案,此編碼的個體型只能反映調度中的分配方案,具體調度方案需要經過貪心算法得到。

選擇算子采用確定式采樣(deterministic sampling)選擇。設群體大小為M,個體i的適應度為Fi。群體中每個個體在下一代群體中的期望生存數目Ni

交叉算子采用單點交叉(one-point crossover)。經確定式采樣選擇好的個體,以交叉概率Pc參與交叉操作。在參與交叉操作的個體編碼中隨機設置一個交叉點,然后在該點相互交換2個配對的個體部分的染色體。

變異算子采用均勻變異(uniform mutation)。個體編碼串中每一個基因座都為變異點,每個變異點以較小的變異概率Pm從符合的基因范圍內取一隨機數來替代原有基因值。

選擇算子會讓適應度更高的個體更多地保留,交叉、變異等操作產生出新的優良個體。但由于這些操作的隨機性,它們也可能破壞原有適應度較好的個體。如圖2所示,新一代群體中會保留上一代群體中適應度最高的個體,該操作保證了遺傳算法的收斂性并加快了進化的效率。

貪心算法主要應用在根據已有任務分配下,計算車輛最短所需的執行時間。個體的執行時間是評判該個體優劣的主要依據,所需的執行時間越長,說明該方案越差,個體的適應度也越低。倉庫中的運輸車輛如同多臺可并行執行任務的處理器,為了實現資源優化利用,調度者希望盡可能多地利用車輛,最好每輛運輸車都分配有任務,達到車輛資源的充分利用。因此,本算法在求最后適應度值時,增加了罰函數,對于出現不均分配的個體予以適應度上的懲罰。

計算適應度環節流程如圖3,可細分為:

1)對個體編碼串進行解碼,即按照編碼串對調度車輛進行任務分配;

2)貪心算法求得每輛運輸車完成所分配任務預計執行最短的時間;

3)取個體中最長的執行時間,作為整個調度方案的執行時間;

4)根據調度方案的執行時間T和罰參數P,求解適應度函數如下

其中,Pi為調度方案i中有Pi輛調度車未被分配任務。

圖3 計算適應度流程Fig 3 Flow chart of calculating fitness  下載原圖

個體基因先通過解碼得到任務分配情況,再由貪心算法通過查表對任務進行排序求每輛車執行時間。設3輛可調度車編號為A,B,C,6項需執行任務編號為ⅰ,ⅱ,ⅲ,ⅳ,ⅴ,ⅵ。表2中每個單元格數值表示,完成橫向任務后再去處理縱向任務所需要花的時間值;橫向為車編號代表,由車輛初始位置執行縱向任務所需要花的時間值。時間值設置為1~100 min。

表2 執行時間表Tab 2 Executing time table  下載原圖

表2 執行時間表Tab 2 Executing time table

例如:個體222110對其使用貪心算法,查表求解最短執行時間,其步驟如下:

1)由解碼得A車處理任務ⅵ,B車處理任務ⅳ和ⅴ,C車處理任務ⅰ,ⅱ和ⅲ。

2)以C車為例,查C車初始位置執行ⅰ,ⅱ,ⅲ的時間值選取最小,先執行。如表2選取ⅱ先執行,查詢ⅱ完成后ⅰ,ⅲ的時間值選最小ⅰ。最后查得ⅰ完成后執行ⅲ所需時間,得此調度方案下C車的最佳任務排序為ⅱ→ⅰ→ⅲ,時間值為2+10+43=55 min。同理求得A車任務排序ⅵ,時間值89min;B車任務排序ⅴ→ⅳ,時間值66 min。

3)個體222110對應的調度方案執行時間取最長的A車,時間值89 min。

4)按式(2)求出該個體適應度為2.110。此處保留三位小數。

由上可見:貪心算法由一個僅表示任務分配的遺傳算法個體編碼串,經過解碼、貪心算法求解、適應度函數,形成了一個完整的調度方案。用最快速、簡便的方法在極短的時間里給出了最優或是次優的任務排序解。獲得每個任務由哪輛車完成,每輛車先后執行哪些任務,預計需要多少時間等信息。

實驗程序設3輛可調度車編號為A,B,C,6項需執行任務編號為ⅰ,ⅱ,ⅲ,ⅳ,ⅴ,ⅵ。各任務執行時間值如表2。種群大小M設置為M=NtNv×2=36。進化代數Ge=100代,交叉概率Pc=0.7,變異概率Pm=0.01。初代個體編碼串與時間值表(表2)均為隨機數產生。圖4顯示了此算法在進化中,種群的平均時間值和最優個體時間值的變化過程。由圖可見,遺傳算法在前40代,種群的平均時間值明顯下降,意味著整個種群在向更優進化。由于該算法使用了最優保存策略,故最優個體時間值折線不像平均時間值那樣呈現波動進化。除非當進化中產生更優個體才會替換原有的,時間值從而進一步降低,否則,一直保持下去。該例最后一代種群的最優個體,即算法的最終解為:

個體基因:012011;

A車:ⅰ→ⅲ,時間值51 min;

B車:ⅴ→ⅱ→ⅵ,時間值52 min;

C車:ⅳ,時間值16 min;

調度時間值:52 min。

圖4 不同進化代數的時間值變化Fig 4 Time value change of different numbers of evolution generation  下載原圖

算法中進化代數Ge與種群大小M都是隨著調度量的需求而變化的。經實驗發現,尤其種群數量M極大影響著算法的搜索能力。若M設置過小,遺傳算法容易早熟,全局搜索能力明顯變差。相較而言代數Ge的變化,只是影響已有種群中發生交叉、變異等操作發生的概率。因此,當M不大或Pc,Pm設置較小時,Ge變化的作用并不明顯。若把種群數量縮小一半至18進化情況見圖5。平均時間值折線顯示種群較早就停止進化,有明顯的早熟現象。且最終解的時間值為57 min,并非最優調度方案。可見種群數量M的縮小使得搜索能力大大減弱。

圖5 種群數量縮小一半的時間值變化Fig 5 Time value change of half population quantity  下載原圖

若保持M=36,將進化代數減少一半至50,進化情況見圖6。由平均時間值折線可見,進化情況與圖4相似,并未產生早熟現象。通過50代的進化也獲得了最優調度方案。為確保進化完整和適應更大調度量,進化代數應設置得足夠大。

本文提出的基于貪心算法和遺傳算法的倉儲車輛調度算法,經編程實現與實驗證明:本方法簡化了遺傳算法對車輛調度應用中復雜的編碼方法。避免了由于約束條件而將個體調整為可行解時而產生的非隨機性,不僅避免遺傳算法易出現的早熟的困境,也提高全局搜索能力。本算法的交叉、變異等操作使用起來更加靈活,限制更少,使用者可根據使用范圍,選擇更適用的操作種類。本算法還可通過改動任務、時間表、罰函數等,以適用于其他更高要求的多任務多處理器的調度。

圖6 遺傳代數減少一半的時間值變化Fig 6 Time value change of half inheritance generations