崔亞 宋劍萍 韓曉東

摘要：本文圍繞汽車總裝線的裝配問(wèn)題，構(gòu)建了以極小化生產(chǎn)成本為目標(biāo)，以顏色等各個(gè)屬性上的裝配要求為約束條件的優(yōu)化模型，并設(shè)計(jì)了基于貪心算法和遺傳算法的新型混合算法，在matlab軟件下編程求解，得到最優(yōu)裝配順序。

Abstract： Focusing on the assembly problem of automobile final assembly line， an optimization model was built to minimize the production cost as the goal， and the assembly requirements on various attributes such as color as the constraint conditions. A new hybrid algorithm based on greedy algorithm and genetic algorithm was designed， which was solved by programming in MATLAB software to obtain the optimal assembly sequence.

關(guān)鍵詞：優(yōu)化模型;貪心算法;遺傳算法;裝配順序

Key words： optimization model;greedy algorithm;genetic algorithm;assembly sequence

中圖分類號(hào)：U471.23? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? ? ? ? ? ?文章編號(hào)：1674-957X（2021）17-0158-03

1? 問(wèn)題重述

汽車裝配是汽車生產(chǎn)的一個(gè)重要環(huán)節(jié)，現(xiàn)有某汽車公司的裝配流程圖以及該企業(yè)一周的生產(chǎn)計(jì)劃和每種型號(hào)汽車的品牌、配置、動(dòng)力、驅(qū)動(dòng)、顏色5種屬性，現(xiàn)需根據(jù)裝配要求使成本盡可能低的情況下，設(shè)計(jì)一個(gè)簡(jiǎn)單有效的算法將待裝配車輛在總裝線上重新進(jìn)行排序。

2? 符號(hào)說(shuō)明（表1）

3? 問(wèn)題分析

針對(duì)該問(wèn)題，本文構(gòu)建以極小化生產(chǎn)成本為目標(biāo)，以顏色等各個(gè)屬性上的裝配要求為約束條件的數(shù)學(xué)優(yōu)化模型。通過(guò)分析發(fā)現(xiàn)，貪心算法針對(duì)大規(guī)模問(wèn)題很難獲得最優(yōu)解，故在求解上分為兩步：首先使用貪心算法求解得到一個(gè)比較好的初值;然后運(yùn)用遺傳算法進(jìn)一步改進(jìn)，得到最終的最優(yōu)裝配順序。

4? 模型建立

本文運(yùn)用線性約束和含有示性函數(shù)的約束條件來(lái)刻畫生產(chǎn)中的限制條件，以生產(chǎn)成本最低為目標(biāo)函數(shù)，構(gòu)建了一個(gè)數(shù)學(xué)優(yōu)化模型。將所有的示性函數(shù)轉(zhuǎn)化為混合整數(shù)規(guī)劃，形成一個(gè)大規(guī)模的混合整數(shù)的線性規(guī)劃問(wèn)題。

4.1 決策變量

設(shè)每天生產(chǎn)n輛車，其中一輛車有5種屬性，就用一個(gè)n×5的矩陣把A所有車的信息表示出來(lái)。第一個(gè)屬性取值為{1，2}，分別對(duì)應(yīng)品牌A1，A2;第二個(gè)屬性取值可以為{1，2，3，4，5，6}，分別對(duì)應(yīng)配置B1，B2，B3，B4，B5，B6;第三個(gè)屬性表示動(dòng)力，取值為{1，2}，分別對(duì)應(yīng)汽油和柴油;第四個(gè)屬性表示驅(qū)動(dòng)，取值為{-1，1}，分別對(duì)應(yīng)兩驅(qū)和四驅(qū);第五個(gè)屬性表示顏色，取值為{0，1，2，3，4，5，6，7，20}。則n×5的矩陣A表示如下：A=（ ）n×5。

此矩陣可用matlab軟件生成。因?yàn)楦鶕?jù)所給數(shù)據(jù)，已知每種車每天需要多少輛，例如9月17日，汽油、兩驅(qū)，黃色的車要4輛。只需要把該屬性的車對(duì)應(yīng)的向量復(fù)制4次即可。程序?yàn)椋?，由此可生成矩陣A。

決策變量有兩部分，第一部分是1×n維向量a，a中的元素是1到n的序號(hào)，代表生產(chǎn)順序。例如a=（3，4，9，10，

6，5，…）代表先生產(chǎn)A中的第三行代表的車，然后生產(chǎn)第4行的，依次類推。第二部分是1×n維向量b，b中元素都為1或2，其中1代表在c1線上進(jìn)行噴涂，2代表在c2線上進(jìn)行噴涂。

根據(jù)以上所述可得決策變量為：

4.2 建立目標(biāo)函數(shù)[1][2]

4.2.1 第一部分目標(biāo)：降低車輛切換次數(shù)的成本

根據(jù)相鄰兩輛車之間的差異越大，成本越高，為了減少同一品牌下不同配置車輛之間切換次數(shù)的成本，故建立如下的目標(biāo)函數(shù)，記為：

4.2.2 第二部分目標(biāo)：降低噴涂線上更換顏料顏色的成本

設(shè)向量C1為在c1線上噴涂的車輛，C2為在c2線上噴涂的車輛，N1表示的是向量C1的元素個(gè)數(shù)，N2表示的是向量C2的元素個(gè)數(shù)。

因?yàn)橛?條流水線，所以要識(shí)別出來(lái)每條流水線的車輛，就是把C1噴涂的那些車輛找出來(lái)，并把它們的序號(hào)記錄下來(lái)。C1和a，b的關(guān)系是C1是b為1的那些a組成的向量。同理可得向量C2。例如a=（5，4，3，2，1），b=（1，1，1，2，2）;那么C1=（5，4，3）。程序?yàn)椋?/p>

為了使噴涂線上不同顏色的汽車之間切換次數(shù)盡可能少，分別建立以C1、C2兩條線上顏色調(diào)換成本最小的目標(biāo)函數(shù)如下：

其含義為：用向量的差或者向量部分分量的差來(lái)表示這種成本。

4.3 約束條件

由于工藝流程的制約和質(zhì)量控制的需要以及降低成本的考慮，總裝和噴涂作業(yè)對(duì)經(jīng)過(guò)生產(chǎn)線車輛型號(hào)有多種要求：

4.3.1 裝配要求

最多連續(xù)不超過(guò)2輛這個(gè)約束可以寫成相鄰2個(gè)且只有兩個(gè)系數(shù)是1的線形約束，即在顏色之前的約束都可以用線性規(guī)劃表示。綜上所述，該項(xiàng)則需要細(xì)分為四個(gè)約束：

①四驅(qū)汽車連續(xù)裝配數(shù)量不得超過(guò)2輛[3]。

②兩批四驅(qū)汽車之間間隔的兩驅(qū)汽車的數(shù)量至少是10輛。

③柴油汽車連續(xù)裝配數(shù)量不得超過(guò)2輛。

④兩批柴油汽車之間間隔的汽油汽車的數(shù)量至少10輛。

4.3.2 顏色要求

設(shè)顏色分別用數(shù)字0、1、2、3、4、5、6、7、20表示，如表2。

①黃與灰間隔。

②紅與灰間隔。

③藍(lán)與白間隔。

④金與紅間隔。

⑤根據(jù)黑色汽車連續(xù)排列的數(shù)量在50-70輛之間，兩批黑色汽車在總裝線上需間隔至少20輛，可得：

4.3.3 通過(guò)引入輔助變量，我們將示性函數(shù)轉(zhuǎn)化為混合整數(shù)約束

通過(guò)如上的轉(zhuǎn)化技巧，可將所有的示性函數(shù)轉(zhuǎn)化為混合整數(shù)規(guī)劃約束。這樣，就形成了一個(gè)大規(guī)模的混合整數(shù)的線性規(guī)劃問(wèn)題。

5? 模型求解

5.1 模型算法

采用貪心算法結(jié)合遺傳算法進(jìn)行求解。首先使用貪心算法求解得到一個(gè)比較好的初值;然后運(yùn)用遺傳算法進(jìn)一步改進(jìn)，得到最終的的最優(yōu)裝配順序。

5.2 模型求解實(shí)例

下面以求解9月20日的裝配順序?yàn)槔瑏?lái)介紹該模型的求解過(guò)程：

①考慮到1）每天白班和晚班都是按照先A1后A2的品牌順序，裝配當(dāng)天兩種品牌各一半數(shù)量的汽車;2）噴涂線上汽車顏色的要求;3）總裝線上汽車顏色的要求，使用貪心算法得到一個(gè)汽車的裝配順序，即為初值向量。

②檢驗(yàn)的最優(yōu)性，利用matlab編寫程序把生產(chǎn)汽車的數(shù)據(jù)生成矩陣，針對(duì)依然不滿足的相鄰班次銜接處的要求以及顏色的要求采用遺傳算法進(jìn)行調(diào)整，最終得到9月20日的最優(yōu)裝配順序。

6? 模型優(yōu)缺點(diǎn)

6.1 模型的優(yōu)點(diǎn)

新混合算法，一方面克服了貪心算法針對(duì)大規(guī)模問(wèn)題難以獲得全局最優(yōu)解的不足，另一方面克服了遺傳算法計(jì)算速度慢的不足，具有較好的實(shí)用價(jià)值。

6.2 模型的缺點(diǎn)

該混合算法相較貪心算法與遺傳算法有了大幅的提升，但這兩種算法都是人工智能算法，針對(duì)大規(guī)模問(wèn)題找到最優(yōu)解的速度很慢。

參考文獻(xiàn)：

[1]孫文瑜，徐成賢，朱德通.最優(yōu)化方法[M].第二版.高等教育出版社，2010.

[2]張可村，李換琴.工程優(yōu)化方法及其應(yīng)用[M].西安交通大學(xué)出版社，2007.

[3]刁在筠，劉桂真，戎曉霞，王光輝.運(yùn)籌學(xué)[M].第四版.高等教育出版社，2016.

[4]Frank R. Giordano，William P.Fox，Steven B.Horton 著，葉其孝，姜啟源 等 譯. 數(shù)學(xué)建模（原書第5版），A First Course in Mathematical Modeling（Fifth Edition）[M]. 機(jī)械工業(yè)出版社，2014.