生產(chǎn)運(yùn)輸調(diào)度算法研究

卓雪雪 朱蒼璐 郭杰 錢鵬

【摘? 要】生產(chǎn)調(diào)度問題一直備受社會(huì)關(guān)注，尤其是制造業(yè)，因此，經(jīng)典調(diào)度問題被研究學(xué)者提出，即實(shí)現(xiàn)一臺(tái)機(jī)器加工一個(gè)工件的功能。隨著社會(huì)對(duì)產(chǎn)品的需求量不斷增加，實(shí)現(xiàn)一臺(tái)機(jī)器同時(shí)加工多個(gè)工件的批調(diào)度問題被相繼提出，其中差異工件尺寸調(diào)度問題最為復(fù)雜。論文研究的生產(chǎn)運(yùn)輸調(diào)度算法的復(fù)雜度超過了以上所有的批調(diào)度問題，涉及批調(diào)度和產(chǎn)品交付2個(gè)階段，這是一個(gè)強(qiáng)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.

【關(guān)鍵詞】平行批處理機(jī);不同尺寸的工件;蟻群優(yōu)化算法

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

【中圖分類號(hào)】F273;TP18? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?【文獻(xiàn)標(biāo)志碼】A? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?【文章編號(hào)】1673-1069（2021）11-0124-04

1 引言

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

2 研究內(nèi)容

3 算法研究

3.1 下界算法

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

算法1：下界算法（LB）

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

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

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

④調(diào)用DLV（BU）求出目標(biāo)值。

下界算法中的第4步提到的DLV（B）算法是本文研究的調(diào)度算法的第2個(gè)階段，即運(yùn)輸。該算法具體步驟如下：

算法2：DLV（B）

①計(jì)算每個(gè)批Bki中工件權(quán)值之和，同時(shí)存儲(chǔ)于Wki中。

②計(jì)算每個(gè)批Bki的完工時(shí)間，同時(shí)存儲(chǔ)于Cki中。

③BD←0，TWD←0。

④l←1到d。

h←BD+1;當(dāng)（Cki≤VTl）且（h-BD）≤VNl×V時(shí)開始循環(huán)。

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

循環(huán)結(jié)束。

⑤輸出目標(biāo)值TWD。

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

3.2 啟發(fā)式算法

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

算法3：啟發(fā)式算法（H）

①根據(jù)工件的比值wj/sj對(duì)工件降序排序。

②根據(jù)最佳適應(yīng)分配原則（BFF）對(duì)工件進(jìn)行分批。

③調(diào)用DLV（B）獲得解，并輸出目標(biāo)值。

把上文例子中的5個(gè)工件用啟發(fā)式算法進(jìn)行分批，分批結(jié)果是批B1是滿批，而B2和B3不滿，造成空間浪費(fèi)，影響了算法的性能。

3.3 兩種基于ACO的算法

本文主要介紹ACO算法與MMAS算法以及啟發(fā)式算法H，三者進(jìn)行性能對(duì)比，在元啟發(fā)式算法中，信息素對(duì)構(gòu)建解很重要。

3.3.1 信息素

文中，當(dāng)前批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 啟發(fā)式信息

根據(jù)本文研究的問題，為尋找更優(yōu)解我們優(yōu)先加工權(quán)值大的工件，但是也要考慮尺寸，如果工件的尺寸過于大，那么這個(gè)工件是不適合優(yōu)先加工的，因?yàn)榇斯ぜ膚j/sj的權(quán)值不一定是最大的。當(dāng)然，如果2個(gè)工件的wj/sj的權(quán)值相同，我們要優(yōu)先對(duì)尺寸小的分批。本文設(shè)計(jì)了3個(gè)獨(dú)立的啟發(fā)式信息，定義如下。

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

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

（5）

3.3.3 候選列表

如果不構(gòu)建候選列表，螞蟻就需要不停地搜索下一個(gè)即將被調(diào)度的工件，這樣會(huì)浪費(fèi)很多時(shí)間，因此，這里我們?yōu)槲浵仒?gòu)建一個(gè)候選列表，節(jié)約時(shí)間，其構(gòu)造如下：

（6）

3.3.4 解的構(gòu)建

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

算法4：CL算法

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

②當(dāng)TB≠[0，0，…，0]。

每只螞蟻構(gòu)建一個(gè)空批Bki。每只螞蟻隨機(jī)選擇一個(gè)沒有被調(diào)度的工件Jj放到批Bki中，然后更新向量TBj←0，根據(jù)式（2）生成當(dāng)前批的候選列表Lki。當(dāng)Lki≠？準(zhǔn)開始循環(huán)。

螞蟻根據(jù)概率Pj，ki從候選列表Lki中選擇Jj加入當(dāng)前批;

（7）

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

③計(jì)算出目標(biāo)值，得出解決方案。

3.3.5 局部優(yōu)化

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

算法5：LO算法

3.3.6 HACO算法

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

算法6：HACO算法

①參數(shù)初始化。②t←0。③如果t

3.3.7 MMAS算法

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

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

③如果目標(biāo)值在D代沒有改進(jìn)，則把信息素的值改為τmax。

4 仿真實(shí)驗(yàn)與結(jié)果分析

4.1 實(shí)驗(yàn)設(shè)置

本文列舉2組實(shí)例N1M1P1、N1M1P2進(jìn)行實(shí)驗(yàn)驗(yàn)證，其中，N1M1P1隨機(jī)生成10個(gè)算例，N1M1P2同樣隨機(jī)生成10個(gè)算例，假設(shè)工件數(shù)為N1=100，機(jī)器數(shù)為M1=2，工件加工時(shí)間分為2種，第一種P1=3，第二種P2=5。

4.2 實(shí)驗(yàn)結(jié)果及分析

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

5 結(jié)語與展望

本文主要研究的是2個(gè)階段的批調(diào)度算法，不同于以往研究學(xué)者，或者只研究批調(diào)度階段，或者只研究產(chǎn)品運(yùn)輸階段，而是根據(jù)現(xiàn)實(shí)社會(huì)的需要把2個(gè)階段結(jié)合起來，為企業(yè)節(jié)約成本，促進(jìn)利益最大化。在此提出了3個(gè)算法，即啟發(fā)式算法H、蟻群算法HACO、最大最小螞蟻算法MMAS，并通過實(shí)例證明MMAS算法構(gòu)建的解的性能最好，優(yōu)于蟻群算法HACO，啟發(fā)式算法相比前兩者性能明顯不足。

當(dāng)然相較于社會(huì)的快速發(fā)展，本文的研究是不夠的，我們可以考慮工件加工時(shí)間不同，機(jī)器加工時(shí)間不同，車容量不同，且涵蓋發(fā)車延遲的問題研究。

【參考文獻(xiàn)】

【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.