Research on a Mixed-model Assembly Line Sequencing Problem

ZHANG Shi-zhe

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

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.

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

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

中圖分類號(hào)：TH162? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文章編號(hào)：1006-4311（2019）32-0269-04

0? 引言

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

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

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

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

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

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

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

1.2 建立數(shù)學(xué)模型

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

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

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

D為計(jì)劃期內(nèi)所需生產(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個(gè)產(chǎn)品的完工時(shí)間;

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

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

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

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

objective

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

2? 改進(jìn)遺傳算法

2.1 編碼

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

按照同樣方法進(jìn)行重復(fù)，即可形成種群。

2.2 適應(yīng)度計(jì)算

首先，對(duì)每一個(gè)染色體計(jì)算其所對(duì)應(yīng)的提前/超期成本。由于本文所解決排序問題目標(biāo)為最小化問題，因此，需將每個(gè)染色體所對(duì)應(yīng)的提前/超期成本進(jìn)行一定的處理轉(zhuǎn)化為適應(yīng)度值，本文所采用的提前/超期成本與適應(yīng)度的轉(zhuǎn)化公式為：

式中fi為每個(gè)個(gè)體的適應(yīng)度值，mi為每個(gè)個(gè)體的提前/超期成本。

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

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

式中Pi為個(gè)體i被選中的概率，fi為個(gè)體i的適應(yīng)度值，I為當(dāng)前種群。

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

2.4 交叉

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

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

隨機(jī)選取染色體1中的兩個(gè)交叉點(diǎn)，并將交叉點(diǎn)間的基因刪除，假設(shè)選取交叉點(diǎn)為3和6，如圖3所示。

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

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

按照同樣交叉方式對(duì)染色體2進(jìn)行處理將得到子染色體2。

2.5 變異

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

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

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

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

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

2.6 局部尋優(yōu)

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

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

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

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

3? 算例分析

3.1 算例

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

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

將第一個(gè)產(chǎn)品進(jìn)入裝配線裝配的時(shí)間設(shè)置為0時(shí)刻，各產(chǎn)品的所對(duì)應(yīng)的交貨期時(shí)間窗如表3所示。

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

3.2 結(jié)果分析

將案例數(shù)據(jù)數(shù)據(jù)帶入算法進(jìn)行優(yōu)化，算法相關(guān)參數(shù)設(shè)置如下：種群數(shù)量100、交叉概率0.9、變異概率0.01、穩(wěn)態(tài)選擇數(shù)量20、迭代次數(shù)100、對(duì)每代中最優(yōu)的20個(gè)個(gè)體進(jìn)行局部尋優(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)計(jì)算，總提前/超期成本為2251.02元。

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

將本文算法與標(biāo)準(zhǔn)遺傳算法以及將本文算法中選擇策略替換為適應(yīng)值比例選擇策略的算法進(jìn)行比較，三種算法的目標(biāo)值收斂曲線如圖11所示。

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

4? 結(jié)論

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

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

作者簡(jiǎn)介：張世哲（1995-），男，山西長(zhǎng)治人，碩士研究生，研究方向?yàn)檫\(yùn)營(yíng)管理。