訂單可拆分的非等同并行多機生產排程問題研究

（華南理工大學 工商管理學院，廣州 510641）

0 引言

在面向訂單生產的制造車間中，為了提高效率，一個訂單的需求往往被拆分為多個子作業進行，子作業間沒有嚴格的優先次序限制，因而稱為訂單（作業）可拆分。非等同并行多機指的是多臺機器間加工成本和效率存在差異。訂單可拆分的非等同并行多機生產排程問題需要解決的是在給定訂單信息（訂貨量、延期懲罰等）和機器信息（加工成本、效率等）的情況下，考慮機器的最低開機量，為每個訂單安排合適的拆分和加工方案。

國內并行多機調度問題的研究開始較早，尹新等[1]使用禁忌搜索方法解決了延期任務數最少的并行多機調度問題。為了提升計算效率，劉民等[2]最早提出了使用遺傳算法求解多機調度問題的方案，并在編碼與變異方法方面做了研究。隨著并行多機調度問題的深入研究以及計算機能力的增強，新的算法逐漸被開發出來。高家全等[3]針對最小化完工時間的一類非等同并行多機調度問題提出了一種混合遺傳算法。江貴松等[4]針對非等同并行多機調度問題提出了一種改進的蟻群算法。為了更貼合現實生產過程，王建軍等[5]考慮了在并行多機生產環境下，隨機機器故障的調度問題。而胡大勇等[6]考慮了等同并行機調度中調整時間與順序相關的情形，通過建立數學規劃模型，利用遺傳算法求解該問題。

在我們已知范圍內，國內關于可拆分調度的研究較少，孫鶴旭等[7]研究了工序可拆分的生產調度問題，并提出了多種群精英遺傳算法，結果表明該算法優于一些常規算法。荊家剛[8]在研究了單件小批量生產企業的生產模式后，提出了將工序進行拆分重新優化排序的思路。與上述工序拆分的研究不同，溫宇昂[9]研究了石英的生產過程，考慮作業的拆分，建立了數學模型，并通過分支定界法和遺傳算法兩種方法進行求解，指出問題規模較大時遺傳算法優于分支定界法。

國外學者在并行多機調度問題上也進行了大量研究。Balin[10]指出盡管在工業生產中該類調度問題普遍存在，但僅有少數學者對其進行研究。在不考慮安裝時間、準備時間和到期時間的情況下，Balin提出了一種遺傳算法，用以解決最小化完工時間的非等同并行多機調度問題。與Balin不同，Hop和Nagarur[11]考慮了具有序列依賴的安裝時間，建立了最小化完工時間的數學模型。在非等同并行多機調度問題上，近年來，越來越多的學者應用不同的新方法研究該類問題。在面對非等同并行批處理機的調度問題時，Maria等[12]提出了一種改進的粒子群算法。除此之外，Maria等[13]針對相同問題還提出了一種人工蜂群算法。兩種算法中，粒子群算法優勢在于計算速度而人工蜂群算法的優勢在于處理大規模問題。Faruk等[14]根據焊接過程研究了一種特殊情況下的并行多機調度問題，并提出了模糊語言方法來解決該類問題。

在可拆分方面，Rasaratnam等[15]研究了作業可拆分的不相關并行多機調度問題，在考慮動態作業釋放和動態機器可用性的基礎上，建立了一個求解最小化加權延遲的混合整數線性規劃模型。Sang-Oh和Yeong-Dae[16]提出了一種針對作業可拆分的等同并行多機調度的分支定界法，并通過算例實驗說明了該方法的有效性。

本文研究的是訂單可拆分的非等同并行多機生產排程問題，與現有研究不同，一方面，現有文獻結合可拆分作業進行分析的較少，另一方面本文從成本角度考慮，更加偏重于訂單拆分方案的制定和成本的節約，以期能給企業實際生產提供一定參考。本文余下章節安排如下：第一章對所研究的問題進行數學刻畫；第二章針對研究問題建立相應數學模型；第三章設計遺傳算法用于求解，并對算法各操作進行詳細說明；第四章結合某電纜制造企業的生產情況進行數值仿真實驗，并對實驗結果進行分析；最后總結全文工作。

1 問題描述

本文研究的問題描述如下：給定n個可拆分加工的訂單，m臺產能和生產成本不同的機器，在滿足最低開機量的條件下，給出生產排程方案使得總成本最低。該問題的數學描述可以用集合（N，P，M，C，L）表示：

1）集合N={N1，N2，…，Nn}表示n個可拆分但加工過程不可中斷的訂單；

2）集合P={P1，P2，…，Pn}表示n個訂單對應的單位時間延期懲罰成本；

3）集合M={M1，M2，…，Mm}表示m臺生產效率和加工成本不同的機器；

4）集合C={c1，c2，…，cm}表示m臺機器對應的單位時間產能；

5）L為常數，表示加工機器的最低開機生產量。

調度優化的目標是為每個訂單確定合適的拆分方案及其各子作業開始加工的時間，從而使生產總成本最低。總成本由加工成本和延期懲罰成本兩部分構成。

為了簡化研究問題，給出以下一些基本假設：

1）調度開始（0時刻），所有機器都處于可用狀態，所有任務都處于可加工狀態；

2）同一機器只能加工某個訂單的一個任務；

3）一個訂單拆分的子作業數不得超過加工機器數；

4）子作業加工過程不可中斷，加工機器是非搶占式的；

5）同一訂單拆分的子作業在不同機器上調度順序是相同的；

6）任務可以按任何比例拆分，只需滿足最低開機量即可。

2 數學模型

針對所研究的問題，不失一般性，定義如下數學符號：

n：=訂單總數；m：=機器總數；i：=訂單編號；j：=機器編號；di：=訂單i的交貨期；fi：=訂單i的實際完工時間；oi：=訂單i的訂貨量；tij：=訂單i在第j臺機器上加工的時間；αj：=機器j的單位時間加工成本；βi：=訂單i的單位時間延期懲罰成本；cj：=機器j的單位時間產能；L：=最低開機生產量；xij：=訂單i在機器j上子作業的百分比；sij：=訂單i在機器加上子作業開始加工的時間。

其中，xij和sij為決策變量。

根據問題的描述，可構建數學模型：

目標函數：

表示總成本等于總加工成本與總延期懲罰成本之和；

約束1：Ti=max{fi-di,0}，判斷延期與否以及計算延期的時長；

約束2：sij≥0，訂單的所有子作業在調度時刻后才可以開始執行；

約束3：

只有機器j被分配了訂單子作業比例xij時，開始時間sij才有實際意義；

約束4：0≤xij≤1，xij∈R，約束訂單拆分子作業的比例；

約束6：sij+tij＜sqj或sqj+tqj≤sij，1≤q≤n，q∈N且q≠i，同一時刻，一臺機器僅能加工一個訂單的子作業；

約束7：oi·xij≥L，當xij≠0，訂單拆分后的每個子作業都必須不少于開機最低生產量；

約束8：

機器加工時間等于子作業的量比上單位時間產能。

3 算法設計

3.1 染色體編碼

針對所研究的問題，本文提出以下編碼方式：

其中，第一列的元素n表示訂單編號，第二列矩陣中的元素Xnm表示訂單n分配到m機器加工的比例，每一行為一個基因，表示訂單i的分配方案。由于訂單完工時間會受到加工順序的影響，因此染色體中不僅包含了訂單拆分比例的信息，還包含了訂單加工順序的信息，染色體中行順序即表示訂單加工的順序。

3.2 適應度函數

在本文研究的問題中，目標函數是：

3.3 選擇操作

采用常用的輪盤賭選擇法選出“優秀”的個體。具體選擇方法如下：

對于某個個體i，適應度函數為Zi，種群規模為NP，個體的選擇概率為得到每個個體的選擇概率之后，計算累積概率：共進行NP次選擇，每次選擇一個個體，在得到累積概率之后，即得到了每個個體的選擇概率空間，對個體i而言，其選擇概率空間為(APi-1,APi]，當選擇概率落在該區間時，選擇個體i加入繁殖種群中。

3.4 交叉操作

采用定位交叉方法，交叉率為Pc。將繁殖種群中所有染色體進行隨機兩兩配對，配對后的染色體對以概率Pc進行交叉操作。交叉時，隨機選擇多個基因，將兩個染色體中相同編號的基因進行交換，得到兩個新的染色體（如圖1所示），所有染色體對交叉完后得到新的種群。

圖1 交叉操作

3.5 變異操作

采用單點變異，變異率為Pm。變異時，隨機選擇染色體中的一個基因，重新生成一個基因替換選中的基因（如圖2所示）。

圖2 變異操作

3.6 領域搜索

在遺傳操作進行完之后，采用領域搜索的方法增加解的多樣性。具體為對子代種群中的個體進行局部搜索，隨機對換兩個基因的位置，然后將搜索得到的該個體鄰域內其他多個個體中最優的個體加入子種群。

3.7 停止準則

本文設計的算法在運行一定代數之后停止。

4 算例分析

電纜的制造是一個綜合了流水式生產與離散式生產的制造加工過程[5]，其一般的生產流程包括三個大的工序段，即線芯、纜芯及成纜的加工制造（如圖3所示）。某企業采用非等同并行多機生產的模式制造電纜，為了測試本文遺傳算法的性能，結合該企業的生產情況，分別用不同算例進行實驗（算例見附件）。

本文實驗全部基于內存3.86GB、處理器為Intel i5 2.50GHz的個人電腦進行。

圖3 電纜生產流程

算例符號說明：

1）N10M3：10個訂單、3臺機器的生產模式；

2）N20M4：20個訂單、4臺機器的生產模式；

3）N40M6：40個訂單、6臺機器的生產模式。

4.1 遺傳參數的分析

4.1.1 交叉率和變異率

為了選擇合適的交叉率和變異率進行實驗，首先進行了以下試驗：以N10M3（10個訂單、3臺機器）算例為對象，交叉率Pc取值從0.5到1，固定步長0.05，變異率Pm取值從0到0.3，固定步長0.05，選擇適應度函數最大時的交叉率與變異率作為實驗參數，試驗結果如圖4所示。

圖4 交叉率、變異率與適應度關系

根據試驗結果，本文選取交叉率Pc=0.95、變異率Pm=0.15作為后續實驗的參數。

4.1.2 種群規模

在確定了交叉率與變異率之后，分別以種群規模為50、100、300，進行試驗，根據試驗結果，發現當種群規模由50增加至100，目標函數有顯著下降，而當種群規模由100增加至300時，目標函數變化不顯著，因此種群規模確定為100。

4.1.3 迭代代數

圖5 種群規模與目標函數關系

通過多次試驗，根據目標函數從1代到1000代的變化，發現大多數實驗中目標函數在800代之前已趨于穩定，因此迭代代數調整為800代。

4.2 穩定性

為了測試算法的穩定性，根據確定的參數，對每個算例分別進行10次獨立實驗，取每次實驗中產生的所有染色體的目標函數最優值（bestfit）與平均值（meanfit）計算偏差，計算公式為：

圖6 偏差波動分析

如圖6所示，從上到下依次是N10M3，N20M4，N40M6算例的偏差波動分析圖，實驗結果表明，對每個算例而言，多次實驗的偏差值均穩定在一定區間內。通過三個算例之間的對比發現，適應度偏差值的波動隨著問題規模的擴大而趨向于更加平穩，說明該算法計算的目標函數是相對穩定的。

統計每次實驗的運行時間如表1所示，對每個算例單獨來說，計算時間的極差較小，而且從三個算例計算時間的極差/平均值和方差對比可以得出，隨著問題規模增大，計算時間的變化相對趨于平穩。

表1 實驗運行時間統計

綜上所述，從整體來看，該算法計算結果和計算時間穩定性良好，并且能夠適應不同規模的問題求解。

4.3 排產方案

對三個算例分別進行10次實驗，選取結果最優的實驗，給出排產方案。

4.3.1 N10M3（10個訂單、3臺機器）

最優的目標函數值為Z=22689.8，該值在迭代至700代后產生，排產方案如圖7、圖8所示。

圖7 N10M3排產甘特圖

圖8 N10M3目標函數隨代數變化

4.3.2 N20M4（20個訂單、4臺機器）

最優的目標函數值為Z=43411.1，該值在迭代至250代后產生，排產方案如圖9、圖10所示。

圖9 N20M4排產甘特圖

圖10 N20M4目標函數隨代數變化

4.3.3 N40M6（40個訂單、6臺機器）

最優的目標函數值為Z=86295.21，該值在迭代至750代后產生，排產方案如圖11、圖12所示。

5 結論

圖11 N40M6排產甘特圖

圖12 N40M6目標函數隨代數變化

本文研究了訂單可拆分的非等同并行多機生產排程問題，構造了求解總成本最小的數學優化模型，采用遺傳算法求解，通過多次試驗找到算法合適的參數，再根據合適的參數進行多次獨立實驗，最終得出較優的排產方案，包括訂單拆分方案和各子作業開始時間。求解結果表明該遺傳算法能夠有效解決不同規模的該類問題，并且具有良好的穩定性。