生產運輸調度算法研究

卓雪雪 朱蒼璐 郭杰 錢鵬

【摘? 要】生產調度問題一直備受社會關注，尤其是制造業，因此，經典調度問題被研究學者提出，即實現一臺機器加工一個工件的功能。隨著社會對產品的需求量不斷增加，實現一臺機器同時加工多個工件的批調度問題被相繼提出，其中差異工件尺寸調度問題最為復雜。論文研究的生產運輸調度算法的復雜度超過了以上所有的批調度問題，涉及批調度和產品交付2個階段，這是一個強NP難問題，深入研究具有重大意義。

【Abstract】The problem of production scheduling attracted much social attention， especially in manufacturing industry. Therefore， the classical scheduling problem is proposed by researchers， that is， realizing the function of one machine processing one workpiece. As the society's demand for products continues to increase， the batch scheduling problem to realize the simultaneous processing of multiple workpieces by one machine has been proposed one after another， among which the scheduling problem of different workpiece sizes is the most complex. The complexity of the algorithms of production and transportation scheduling studied in this paper exceeds all the above batch scheduling problems， involving two stages： batch scheduling and product delivery. This is a strong NP hard problem， and in-depth research is of great significance.

【關鍵詞】平行批處理機;不同尺寸的工件;蟻群優化算法

【Keywords】parallel batch processing machine; workpieces of different sizes; ant colony optimization algorithm

【中圖分類號】F273;TP18? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?【文獻標志碼】A? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?【文章編號】1673-1069（2021）11-0124-04

1 引言

國內外研究學者首先提出了經典調度問題，即單機調度問題，如Tang[1]研究了改進的差分進化算法用以獲得更好的解。但是隨著社會的發展，單機調度問題不能滿足社會的需要，隨后平行機批調度問題被提出。Chang等[2]在研究了模擬退火算法處理平行批處理機調度問題。生產制造階段固然重要，然而從企業利益角度出發，產品交付、最小化運輸成本也非常重要。例如，Koh等[3]研究了訂單的加工、包裝以及交付的整個流程，最小化分銷成本。Ghazvini等[4]研究了單機加工單車交付的問題。在本文中，研究了工件尺寸不同的平行機調度問題，同時，研究了加工完成的工件的交付問題。這種2個階段結合的問題很少被研究，因此，本研究的集成調度具有重要意義。

2 研究內容

3 算法研究

3.1 下界算法

本文提出的下界算法主要是為了與啟發式算法進行性能比較。下面詳細介紹該算法過程：

算法1：下界算法（LB）

①將每個工件Jj單位化，即把每個工件分成若干個單位大小的工件，每個單位工件的權重為wj/sj。因此，得到一個新的單位大小的工件集合，稱為JU。

②把工件集JU中的單位工件按照wj/sj的值降序排序，得到一個有序的工件集。

③把有序的工件集JU按照批的容量的s進行分批，得到批的列表BU。

④調用DLV（BU）求出目標值。

下界算法中的第4步提到的DLV（B）算法是本文研究的調度算法的第2個階段，即運輸。該算法具體步驟如下：

算法2：DLV（B）

①計算每個批Bki中工件權值之和，同時存儲于Wki中。

②計算每個批Bki的完工時間，同時存儲于Cki中。

③BD←0，TWD←0。

④l←1到d。

h←BD+1;當（Cki≤VTl）且（h-BD）≤VNl×V時開始循環。

TWD←TDW+Wki×VTl;h←h+1。

循環結束。

⑤輸出目標值TWD。

下面通過一個例子對此算法進行詳細說明，假設有5個工件，p=1表示工件加工時間為1，VT1=1，VT2=2表示有2次發車，VN1=2，VN2=1表示2種車輛數，V=1表示每輛車1次只可以運輸1個批。S=5表示機器的容量為5。工件單位化，這里舉例說明，如果工件Jj的尺寸為2，權值為3，則對其單位化之后，分成2個工件尺寸為1的工件，同時，工件的權值按單位化的比例進行分配，單位化的2個工件的權值各為1.5。例中便對這12個單位化的工件按照wj/sj的值進行降序排。然后根據機器尺寸S=5進行分批。

3.2 啟發式算法

文中的啟發式算法用來與元啟發式算法作性能對比。下面詳細介紹該算法的步驟：

算法3：啟發式算法（H）

①根據工件的比值wj/sj對工件降序排序。

②根據最佳適應分配原則（BFF）對工件進行分批。

③調用DLV（B）獲得解，并輸出目標值。

把上文例子中的5個工件用啟發式算法進行分批，分批結果是批B1是滿批，而B2和B3不滿，造成空間浪費，影響了算法的性能。

3.3 兩種基于ACO的算法

本文主要介紹ACO算法與MMAS算法以及啟發式算法H，三者進行性能對比，在元啟發式算法中，信息素對構建解很重要。

3.3.1 信息素

文中，當前批Bki和候選工件Jj之間的信息素，記作τj，ki，定義為式（1）。

（1）

為有效探索蟻群的搜索空間，信息素更新尤為重要，信息素更新公式定義為式（2）：

τg，j（t+1）=（1-ρ）·τg，j（t）+mg，j（t）·Δτg，j（t）? ? ? ?（2）

3.3.2 啟發式信息

根據本文研究的問題，為尋找更優解我們優先加工權值大的工件，但是也要考慮尺寸，如果工件的尺寸過于大，那么這個工件是不適合優先加工的，因為此工件的wj/sj的權值不一定是最大的。當然，如果2個工件的wj/sj的權值相同，我們要優先對尺寸小的分批。本文設計了3個獨立的啟發式信息，定義如下。

η1=wj/sj ? ? ? ? （3）

η2=1/sj ? ? ? ? （4）

（5）

3.3.3 候選列表

如果不構建候選列表，螞蟻就需要不停地搜索下一個即將被調度的工件，這樣會浪費很多時間，因此，這里我們為螞蟻構建一個候選列表，節約時間，其構造如下：

（6）

3.3.4 解的構建

元啟發式算法中解的構建至關重要。第一，每只螞蟻為自己創建一個空批，隨后選工件入批，這些工件來自候選列表，而且第1個被選中的工件是隨機的且沒有被螞蟻調度的，每選擇一個工件入批就要及時更新候選列表。第二，螞蟻開始選擇即將入批的第2個工件，入批的第2個工件至最后1個工件都是根據狀態轉移概率的大小進行選擇的。直到候選列表中所有的工件被選完。在螞蟻選擇工件入批的過程中，會判斷當前批是否已滿，如果當前批已滿，則構建新批，只有把全部工件都完成調度方可得到完整的解決方案。重復以上步驟，直到每只螞蟻都完成了最大迭代次數的解的構建。算法如下所述。

算法4：CL算法

①初始化TB←[1，2，…，n]。

②當TB≠[0，0，…，0]。

每只螞蟻構建一個空批Bki。每只螞蟻隨機選擇一個沒有被調度的工件Jj放到批Bki中，然后更新向量TBj←0，根據式（2）生成當前批的候選列表Lki。當Lki≠？準開始循環。

螞蟻根據概率Pj，ki從候選列表Lki中選擇Jj加入當前批;

（7）

更新向量TBj←0;Lki←Lki＼{Jj}。

③計算出目標值，得出解決方案。

3.3.5 局部優化

此局部優化算法是基于每只螞蟻的每個解決方案進行工件交換以及對交換工件后的批進行排序，優化解的質量，從而保證權值較大的工件優先發車，第一時間運輸到客戶手中。首先，檢查優先發車的批與后面發車的批中是否存在權值相同，但是尺寸不同的工件。假設存在這樣的工件，在保證不超出批的容量情況下，把尺寸小的工件交換到優先發車的批中，此時一定要注意，大尺寸的工件被置換到后面發車的批中不能超過此批的容量，否則不予置換。第一步的作用是可以為優先發車的批空出更多的剩余空間。其次，在第一步的基礎上把后發車的批中的合適工件移動到優先發車的批中，且不超出每個批的剩余空間。最后，根據批權值從小到大排序置換工件的批，最終確保權值大的批優先送到客戶手中。具體算法描述如下：

算法5：LO算法

3.3.6 HACO算法

HACO是一種迭代搜索算法，假設蟻群有20只螞蟻，迭代100次，在第一代循環時就會生成20個解，其中每個解都會進行局部優化，得到新的批序列后進行運輸，最后得到運輸結果值。在這20個運輸結果值中挑選一個最好的作為當代最優解，即第1代全局最優解。然后用第1代中的最優解對信息素進行更新，開始第2代循環，按照以上過程循環100代，最后從得到的100個全局最優解中選擇一個最好的作為最終的解。算法過程如下：

算法6：HACO算法

①參數初始化。②t←0。③如果t

3.3.7 MMAS算法

MMAS算法是在ACO算法的基礎上，從3個方面進行改進。第一，為了使螞蟻能夠更好地探索，從而構建更好的解，把信息素初始化為最大值;第二，除了最優解之外，不允許其他任何解更新信息素;第三，信息素過高或者過低有可能發生搜索停滯，造成構建的解陷入局部最優，而不是全局最優，因此，為信息素設定一個范圍。

由于2個蟻群算法求解過程的很多步驟是一樣的，所以這里只描述二者不同的步驟：

③如果目標值在D代沒有改進，則把信息素的值改為τmax。

4 仿真實驗與結果分析

4.1 實驗設置

本文列舉2組實例N1M1P1、N1M1P2進行實驗驗證，其中，N1M1P1隨機生成10個算例，N1M1P2同樣隨機生成10個算例，假設工件數為N1=100，機器數為M1=2，工件加工時間分為2種，第一種P1=3，第二種P2=5。

4.2 實驗結果及分析

對啟發式算法H、蟻群算法HACO、最大最小螞蟻算法三者進行性能對比，圖1得到的是加工時間P=3的實驗對比結果，圖2得到的是加工時間P=5的實驗對比結果，從2個圖中得出以下結論：第一，工件加工時間從3延長到5，3個算法的性能幾乎沒有變化，因此，時間對算法的性能影響較小;第二，3個算法中，啟發式算法H的性能最差，ACO算法的性能遠遠優于啟發式算法，盡管運行時間大于啟發式算法，但是在可接受的合理范圍內，與蟻群算法相比MMAS算法性能較好，相應的運行時間有所增加;第三，2個實例證明2個蟻群算法可以構建出更好的解，這是啟發式算法無法做到的，圖中也證明了MMAS算法性能優于HACO算法的性能，HACO算法的性能遠遠優于啟發式算法H的性能。

5 結語與展望

本文主要研究的是2個階段的批調度算法，不同于以往研究學者，或者只研究批調度階段，或者只研究產品運輸階段，而是根據現實社會的需要把2個階段結合起來，為企業節約成本，促進利益最大化。在此提出了3個算法，即啟發式算法H、蟻群算法HACO、最大最小螞蟻算法MMAS，并通過實例證明MMAS算法構建的解的性能最好，優于蟻群算法HACO，啟發式算法相比前兩者性能明顯不足。

當然相較于社會的快速發展，本文的研究是不夠的，我們可以考慮工件加工時間不同，機器加工時間不同，車容量不同，且涵蓋發車延遲的問題研究。

【參考文獻】

【1】Lixin Tang，Yue Zhao，Jiyin Liu.An improved differential evolution algorithm for practical dynamic scheduling in steelmaking-continuous casting production [J]. IEEE Trans-actions on Evolutionary Computation，2014（5）：209-225.

【2】P.Y. Chang，P. Damodaran，S. Melouk.Minimizing makespan on parallel batch processing machines[J].International Journal of Production Research，2004，42（19）：4211-4220.

【3】Shie-Gheun Koh，Pyung-Hoi Koo，Jae-Won Ha，et al.Scheduling parallel batch processing machines with arbitrary job sizes and incompatible job families[J].International Journal of Production Research，2004，42（19）：4091-4107.

【4】Fariborz Jolai Ghazvini，Lionel Dupont.Minimizing mean flow times criteria on a single batch processing machine with non-identical jobs sizes[J].International Journal of Production Economics，1998，55（3）：273-280.