崔亞 宋劍萍 韓曉東

摘要：本文圍繞汽車總裝線的裝配問題，構建了以極小化生產成本為目標，以顏色等各個屬性上的裝配要求為約束條件的優(yōu)化模型，并設計了基于貪心算法和遺傳算法的新型混合算法，在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.

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

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

中圖分類號：U471.23? ? ? ? ? ? ? ? 文獻標識碼：A? ? ? ? ? ? ?文章編號：1674-957X（2021）17-0158-03

1? 問題重述

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

2? 符號說明（表1）

3? 問題分析

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

4? 模型建立

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

4.1 決策變量

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

此矩陣可用matlab軟件生成。因為根據(jù)所給數(shù)據(jù)，已知每種車每天需要多少輛，例如9月17日，汽油、兩驅，黃色的車要4輛。只需要把該屬性的車對應的向量復制4次即可。程序為：，由此可生成矩陣A。

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

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

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

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

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

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

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

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

因為有2條流水線，所以要識別出來每條流水線的車輛，就是把C1噴涂的那些車輛找出來，并把它們的序號記錄下來。C1和a，b的關系是C1是b為1的那些a組成的向量。同理可得向量C2。例如a=（5，4，3，2，1），b=（1，1，1，2，2）;那么C1=（5，4，3）。程序為：

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

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

4.3 約束條件

由于工藝流程的制約和質量控制的需要以及降低成本的考慮，總裝和噴涂作業(yè)對經過生產線車輛型號有多種要求：

4.3.1 裝配要求

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

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

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

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

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

4.3.2 顏色要求

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

①黃與灰間隔。

②紅與灰間隔。

③藍與白間隔。

④金與紅間隔。

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

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

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

5? 模型求解

5.1 模型算法

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

5.2 模型求解實例

下面以求解9月20日的裝配順序為例，來介紹該模型的求解過程：

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

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

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

6.1 模型的優(yōu)點

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

6.2 模型的缺點

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

參考文獻：

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

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

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

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