一種混合裝配線產(chǎn)品排序問題的研究

Research on a Mixed-model Assembly Line Sequencing Problem

ZHANG Shi-zhe

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

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? 引言

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

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

1? 產(chǎn)品排序問題的數(shù)學模型

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

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

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

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

1.2 建立數(shù)學模型

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

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

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

D為計劃期內所需生產(chǎn)產(chǎn)品總量;

N={1，…，n，…，D}生產(chǎn)產(chǎn)品集合;

np產(chǎn)品類型數(shù)量;

L={1，…，l，…，np}產(chǎn)品類型集合;

Ni為第i種產(chǎn)品的總生產(chǎn)量;

Tij為第i類型的第j個產(chǎn)品的完工時間;

ADi為第i類型產(chǎn)品的單位提前成本;

DEi為第i類型產(chǎn)品的單位延期成本;

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

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

objective

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

2? 改進遺傳算法

2.1 編碼

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

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

2.2 適應度計算

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

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

2.3 穩(wěn)態(tài)選擇

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

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

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

2.4 交叉

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

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

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

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

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

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

2.5 變異

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

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

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

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

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

2.6 局部尋優(yōu)

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

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

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

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

3? 算例分析

3.1 算例

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

在裝配過程中，各產(chǎn)品依次經(jīng)過12個工作站進行裝配，每種產(chǎn)品在各工作站的裝配時間如表2所示。

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

每種產(chǎn)品的提前超期成本如表4所示。

3.2 結果分析

將案例數(shù)據(jù)數(shù)據(jù)帶入算法進行優(yōu)化，算法相關參數(shù)設置如下：種群數(shù)量100、交叉概率0.9、變異概率0.01、穩(wěn)態(tài)選擇數(shù)量20、迭代次數(shù)100、對每代中最優(yōu)的20個個體進行局部尋優(yōu)，尋優(yōu)代數(shù)為100。

將數(shù)據(jù)帶入算法，經(jīng)過優(yōu)化后，得到最優(yōu)產(chǎn)品生產(chǎn)序列，所有產(chǎn)品均未產(chǎn)生超期成本，每種產(chǎn)品的提前/超期成本、生產(chǎn)順序如表5所示。

經(jīng)計算，總提前/超期成本為2251.02元。

3.3 穩(wěn)態(tài)選擇策略與其他遺傳算法的比較

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

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

4? 結論

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

參考文獻：

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

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

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

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

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

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

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

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

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