一種混合裝配線產品排序問題的研究

Research on a Mixed-model Assembly Line Sequencing Problem

ZHANG Shi-zhe

摘要：針對帶交貨期時間窗的混合裝配線產品排序問題進行研究。根據帶交貨期時間窗的混合裝配線產品排序問題的特點建立混合裝配線產品排序以提前/超期成本最小為目標的數學模型，并設計一種改進遺傳算法進行求解。最后以一個案例為例，證明算法的有效性。

Abstract： In this paper， the mixed-model assembly line sequencing problem with delivery time window is studied. According to the characteristics of mixed-model assembly line sequencing problem with delivery time window， a mathematic model was established aiming at minimizing the cost of earliness/tardiness for the mixed-model assembly line sequencing problem. An improved genetic algorithm was proposed according to the model. Finally， the robustness of proposed algorithm was demonstrated by the benchmark instance.

關鍵詞：排序問題;混合裝配線;提前/拖期;遺傳算法

Key words： sequencing problem;mixed-model assembly line;earliness/tardiness;genetic algorithm

中圖分類號：TH162? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻標識碼：A? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文章編號：1006-4311（2019）32-0269-04

0? 引言

隨著社會的發展，混合裝配線被越來越多的應用于實際生產中。而產品排序問題就成為了混合裝配線優化過程中必須面對的問題。在某些高價值產品的生產過程中，經常會遇到以最小化產品提前/超期成本為目標的生產排序問題，這類產品往往具有價值較高、每件產品擁有其獨立的交貨期時間窗、不適合長期儲存、延期交付將產生大量的延期交付成本等特點。工程機械就是這類產品的典型代表。

本文將針對混合裝配線排序問題進行研究，建立數學模型，并設計一種改進遺傳算法，以最小化產品排序的總提前/超期成本，從而提升企業效益。

1? 產品排序問題的數學模型

1.1 帶交貨期時間窗的混合裝配線產品排序問題

產品排序問題是一個典型的NP-hard問題。首先，對于混合裝配線中產品的裝配而言，多種相似產品在一條裝配線上進行裝配，每種產品由裝配線起始工作站進入裝配線開始裝配，依次經過每個工作站，直至裝配完畢，而每個工作站每種產品的裝配時間并不相同。

其次，對于產品的交付而言，每種產品具有獨立的交貨期。若產品在最早交貨時間之前完工，將產生庫存成本、維護成本等提前交付成本。同樣，若產品在最晚交貨時間之后完工，將產生違約成本等超期成本。

帶時間窗交貨期的混合裝配線排序問題就是通過合理安排產品進入裝配線進行裝配的順序，使各產品的裝配完成時間盡可能落在其交貨期時間窗之內，以最小化總提前/超期成本的問題。不合理的生產排序將會導致較高的成本，嚴重影響企業效益。因此，通過合理安排各產品的裝配順序以使產品總提前/超期成本最小，對企業而言至關重要。

1.2 建立數學模型

首先，本文在建立相應的數學模型之前，作出如下假設：①每個產品不能同時在幾個工作站進行裝配，在某一時刻只能在一個工作站進行裝配。②每個產品的裝配一旦開始不能停止，中途不能插入其他產品進行裝配。③產品依次通過各個工作站完成裝配。④每種產品在各工作站的裝配時間固定，與裝配順序無關。

為描述混合裝配線排序問題，定義以下參數及變量：

[d，d]為第i類型第j個產品的交貨期時間窗，d為第i類型第j個產品的最早交貨時間，d為第i類型第j個產品的最晚交貨時間;

D為計劃期內所需生產產品總量;

N={1，…，n，…，D}生產產品集合;

np產品類型數量;

L={1，…，l，…，np}產品類型集合;

Ni為第i種產品的總生產量;

Tij為第i類型的第j個產品的完工時間;

ADi為第i類型產品的單位提前成本;

DEi為第i類型產品的單位延期成本;

Zij=01，若Zij=1，則第i個裝配的產品為j類型產品;

最終得到混合裝配線排序問題的數學模型為：

objective

公式（1）表示所有產品總提前/超期成本最小，其中max（d-Tij，0）表示第i類型的第j個產品的提前完工時間，ADimax（d-Tij，0）表示第i類型的第j個產品的提前成本，max（Tij-d，0）表示第i類型的第j個產品的延遲交付時間，DEimax（Tij-d，0）表示第i類型的第j個產品的超期成本。公式（2）表示每種產品產量必須與計劃期內該品種產品需求量一致。公式（3）生產序列每個位置有且只能有1個產品。公式（4）表示變量Z的取值范圍。

2? 改進遺傳算法

2.1 編碼

產品排序問題由于只需要優化產品的裝配順序，因此，在利用遺傳算法求解時，采用數字串編碼的方式進行編碼。每條染色體表示一個可行產品裝配順序，染色體上每一個基因表示一個產品，染色體的長度即為該生產周期內所需生產產品的總量。染色體生成的步驟為：①確定所需生產產品類型數量以及各類型產品數量。②在當前可生產產品類型中隨機選擇一種產品放入染色體對應位置。③所選類型產品生產數量減1，更新所需生產產品類型以及各類型產品所需生產量。④若更新后所需生產產品類型數量不為0，則返回步驟2，若更新后計劃期內所需生產產品類型數量為0，則結束。

按照同樣方法進行重復，即可形成種群。

2.2 適應度計算

首先，對每一個染色體計算其所對應的提前/超期成本。由于本文所解決排序問題目標為最小化問題，因此，需將每個染色體所對應的提前/超期成本進行一定的處理轉化為適應度值，本文所采用的提前/超期成本與適應度的轉化公式為：

式中fi為每個個體的適應度值，mi為每個個體的提前/超期成本。

2.3 穩態選擇

本文選擇穩態選擇策略作為排序問題的選擇方式，即選擇少量個體進行之后的交叉、變異操作。每個個體被選中的概率計算公式為：

式中Pi為個體i被選中的概率，fi為個體i的適應度值，I為當前種群。

之后，根據每個個體被選中的概率選擇少量個體組成交配池進行之后的交叉、變異操作。

2.4 交叉

染色體的交叉采用次序交叉的方式進行處理，以下舉例說明：

假設，某條裝配線生產7種類型產品，每種產品均只生產一個，經編碼、選擇后產生交配池，從當前交配池中，隨機選取兩條染色體，假設兩條染色體如圖1、圖2所示。

隨機選取染色體1中的兩個交叉點，并將交叉點間的基因刪除，假設選取交叉點為3和6，如圖3所示。

將染色體2中染色體1保留部分依次刪除，如圖4所示。

將染色體2中剩余部分依次插入染色體1中所刪去部分得到子染色體1，如圖5所示。

按照同樣交叉方式對染色體2進行處理將得到子染色體2。

2.5 變異

在進行完交叉操作后，需進行變異操作，本文對染色體的變異設定一個變異方向。首先，從交叉產生的子代群體中，隨機選取一個染色體。之后，隨機選擇該染色體的一個基因，根據所選取基因的提前/超期成本進行調整，若該基因產生了提前入庫成本，則將該基因向染色體尾部方向調整，若該基因產生了超期成本，則將該基因向染色體頭部方向調整。以下舉例說明，仍然采用上文中案例進行說明。

首先從交叉后生成的子代中，隨機選擇一條染色體，假設上文案例中所生成的子代中隨機選擇一條染色體如圖6所示。

隨機選擇一個基因，假設選擇基因4。若該基因存在超期成本，則將該基因隨機插入其左側染色體部分，如圖7所示。

若該基因存在提前入庫成本，則將該基因隨機插入其右側染色體部分，如圖8所示。

在完成變異操作后，將生成的子代個體代替原種群中最差的等量個體遺傳至下一代中。

2.6 局部尋優

為使算法更快速收斂到最小值附近，本文在遺傳算法完成遺傳操作后，對種群中個體進行局部尋優。本文在對種群個體進行局部尋優時，僅對種群中少量較優個體進行局部尋優。

在對個體進行局部尋優時，借鑒鄰域搜索以及2-OPT算法的思想進行處理。本節仍以上文中案例為例進行說明，假設經過上文的遺傳變異后，形成新種群，從新種群中選擇少量最優個體進行局部尋優，假設某進行局部尋優操作染色體如圖9所示。

利用2-OPT算法的思想構建一個所選染色體的鄰域染色體，即對當前染色體隨機選取兩個基因，并將兩個基因之間的基因進行倒序排列，假設選取位置為2和6，之后對兩個基因之間的染色體部分進行倒序，所得到的新染色體即為一個鄰域染色體。如圖10所示。

在得到一個新的鄰域染色體后，判斷新染色體是否優于原染色體，若優于原染色體，則用該染色體代替掉原染色體，并對該新染色體進行鄰域搜索，直至達到結束條件退出局部尋優，若不優于原染色體，則繼續對原染色體進行搜索，直至達到結束條件退出局部尋優。

3? 算例分析

3.1 算例

某工程機械制造公司共需生產10種產品共120臺機械，10種產品均在一條混合裝配線上進行生產，每種產品的生產數量如表1所示。

在裝配過程中，各產品依次經過12個工作站進行裝配，每種產品在各工作站的裝配時間如表2所示。

將第一個產品進入裝配線裝配的時間設置為0時刻，各產品的所對應的交貨期時間窗如表3所示。

每種產品的提前超期成本如表4所示。

3.2 結果分析

將案例數據數據帶入算法進行優化，算法相關參數設置如下：種群數量100、交叉概率0.9、變異概率0.01、穩態選擇數量20、迭代次數100、對每代中最優的20個個體進行局部尋優，尋優代數為100。

將數據帶入算法，經過優化后，得到最優產品生產序列，所有產品均未產生超期成本，每種產品的提前/超期成本、生產順序如表5所示。

經計算，總提前/超期成本為2251.02元。

3.3 穩態選擇策略與其他遺傳算法的比較

將本文算法與標準遺傳算法以及將本文算法中選擇策略替換為適應值比例選擇策略的算法進行比較，三種算法的目標值收斂曲線如圖11所示。

由圖中信息可發現，本文算法在收斂速度上明顯優于標準遺傳算法，略優于本文算法選擇策略采用適應值比例選擇策略算法。在結果上，本文算法明顯優于另外兩種算法。

4? 結論

本文針對以最小化產品總提前/超期成本最小為目標的混合裝配線排序問題進行研究，建立了相應的數學模型，并設計了一種基于穩態選擇策略的改進遺傳算法，通過與傳統遺傳算法以及其他幾種遺傳算法選擇策略進行對比，證明了穩態選擇策略的優越性。為企業解決實際產品排序問題提供了方法。

參考文獻：

[1]李逍波，林爭輝.一種高效穩態型遺傳算法結構[J].上海交通大學學報，1998（01）：7-9.

[2]鄭姣，楊侃，郝永懷，周冉，劉國帥.基于穩態繁殖的遺傳算法在水庫優化調度中的應用[J].水電能源科學，2011，29（08）：38-41.

[3]范麗，張育林.基于穩態遺傳算法的間歇式覆蓋天基雷達星座優化設計[J].國防科技大學學報，2006（02）：17-21.

[4]張貴軍，吳惕華，葉蓉.CTSP問題穩態小生境算法的研究及仿真實現[J].系統仿真學報，2004（08）：1692-1696.

[5]宋華明，馬士華.考慮流水線平衡的混合裝配線排序[J].中國機械工程，2006（11）：1138-1141，1147.

[6]劉巍巍，楊浩，劉慧芳.基于SGRASP-LP算法的混流裝配線排序問題[J].組合機床與自動化加工技術，2019（09）：148-151，156.

[7]秦東各，王長坤.一種基于2-opt算法的混合型蟻群算法[J].工業控制計算機，2018，31（01）：98-100.

[8]劉芬，張訓全，陶泓序.基于生產負荷平衡的混流裝配線計劃排序問題[J].價值工程，2015，34（15）：231-232.

作者簡介：張世哲（1995-），男，山西長治人，碩士研究生，研究方向為運營管理。