基于“哈密頓模型”的線性規(guī)劃在汽配件生產(chǎn)排程問題中的應用

李澤萱 閔慧旭 駱秋榮 林道榮 唐日成 張海飛

摘要：該文基于有向哈密頓圖回路模型，對于汽車零配件的排程進行合理規(guī)劃，該過程通過MATLAB程序實現(xiàn)了線性規(guī)劃問題數(shù)學模型的求解方法，并進一步通過實例模型求解方法的分析比較，證明所采用的程序方法有效快捷。文中的程序簡單明了且具有通用性，只需輸入規(guī)劃模型中對應的相關矩陣，立即得到最優(yōu)解和最優(yōu)值。

關鍵詞：哈密頓有向圖模型;周期等量;線性規(guī)劃;最優(yōu)解;最優(yōu)值

中圖分類號：TP391 文獻標識碼：A

文章編號：1009-3044（2020）10-0248-04

1背景

在汽車零件的生產(chǎn)過程中，需要對不同類型的零件進行噴漆上色，而在噴漆的過程中，由于僅有有限個噴漆裝置，而對于不同顏色的噴漆，需要進行換色，在換色過程中便不免會產(chǎn)生消耗，如果因為在不同圈中相同編號滑橇上擺放的零件種類發(fā)生變化時需要人工進行更換對應支架，為了減少人工負擔，盡可能換色的次數(shù)減少。因此需要對零件進行排程，針對已知的指導生產(chǎn)量制定出生產(chǎn)線未來八圈的詳細噴涂排序計劃，不僅要為了降低生產(chǎn)成本減少換色的次數(shù)，并盡可能地滿足指導生產(chǎn)量的需求（可以允許超過計劃生產(chǎn)量的產(chǎn)出，但不會帶來額外的直接收益）。

2問題分析

某汽車零配件制造商的生產(chǎn)流程如下圖1：生產(chǎn)流程圖所示，其中注塑環(huán)節(jié)完成的汽車零件經(jīng)過火焰烘烤和人工處理后進入注塑件緩存區(qū)準備進行噴涂。噴涂過程如圖2：工程示意圖所示，在傳送帶上完成，傳送帶軌道.上裝有滑橇，滑橇上裝有可拆卸支架，每個零件需要放在特定的支架上進行順序噴涂。噴涂過程的一個生產(chǎn)周期稱作“一圈”（即將傳送帶軌道.上所有滑橇上的零件噴涂完畢），一圈共有303個滑橇，全部噴涂完畢的時間大概在5.5個小時，一個滑橇噴涂工序節(jié)拍大概在1分鐘。一個滑橇有兩面，可同時噴涂，一面可以放3個支架，一個滑橇共可放6個支架，支架類型與零件種類為一一對應關系，每種零件只能放置在對應的特定支架上。一個滑橇上只放置同種零件，滑橇不強制要求擺滿支架和零件，但為避免產(chǎn)能浪費，無特殊原因不會放空支架。支架的數(shù)量是有限制的，所以在一圈的生產(chǎn)計劃中同種零件的上架數(shù)也有對應上限。

3模型建立

3.1數(shù)據(jù)處理

根據(jù)表1：生產(chǎn)需求量表所示，表l中提供的數(shù)據(jù)是按照顏色進行分類，即同種顏色的不同產(chǎn)品按照需求量降序的形式在表1里排列出來，為了達到換色次數(shù)要盡可能少的目的，所以將需求量最大的（例如產(chǎn)品為前保D顏色為曜巖黑的零件需求量為992個，將其除以6向上取整約為166個滑橇，則在一維數(shù)組前166個空間放人166個曜巖黑滑橇）放在形如一維數(shù)組（長度8*303）的最前面，在對同種顏色的配件進行處理，當同一種顏色的配件全部處理完后再處理下一個顏色，同時為了保證符合題干中給出的約束條件，即先滿足每個滑橇中的6個支架均為相同顏色的同種零件，安排少于6個零件時，再安排下一個顏色。每一種零件的總需求量除以6后向上取整，得出來的同種顏色的相同零件排滿的滑橇數(shù)，然后依次擺放在上一次數(shù)組個數(shù)的后面，以此類推來將表1里面的所有顏色的零件都擺放在一維數(shù)組里面。如果碰見約束條件而不得已將同種顏色不同產(chǎn)品的零件與上一次的數(shù)據(jù)隔開，則允許向后推移或者放在最后一圈進行調整排放。每完成一個周期后，重新調整需求量并找出所有顏色中能符合約束條件的產(chǎn)品滑橇最大數(shù)。

根據(jù)顏色分類后按照需求量得降序建立表2：

3.2模型假設

根據(jù)題干的信息可以計算出一圈可放置303*6=1818個支架，而根據(jù)表1種數(shù)據(jù)，使用哈密頓有向圖模型的方式進行排布方案，即在不考慮切換顏色消耗滑橇作為換色的情況下，將每種顏色的零件除以6向下取整可得2210，即安排滿零件支架的滑橇數(shù)量，然后將2210除以303向下取整得7圈，將2210mod 303=89，即第8圈還需要占用89個滑橇，將每種顏色的零件數(shù)mod 6可得每種顏色的零件剩余數(shù)量，接著將同種顏色的同種零件安排在相同的滑塊內，接著安排同種顏色的下一種零件，當同一顏色的不同零件安排完了，再切換下一種顏色的零件，如此反復直至全部安排完成，如此可得：

1）假設題干中里面前七個生產(chǎn)周期幾乎一致，在第八圈有相應的位置和數(shù)量的修改。

2）假設在八個生產(chǎn)周期里面，為了減少人工干預和換色次數(shù)而采取八圈均勻分配，即八圈均勻分配后，得到2種情況：

情況一：產(chǎn)品可噴漆量正好分配完;

情況二：產(chǎn)品可噴漆量大于需求量，可以完成需求且生產(chǎn)力有富余。

3.3定義與符號說明

3.4模型搭建

根據(jù)數(shù)據(jù)對每種產(chǎn)品分別求出單圈最大完全利用滑橇數(shù)（沒有空支架）和所需滑橇數(shù)，并進行比較，需求量大者優(yōu)先原則，最后處理需求量少的產(chǎn)品。若產(chǎn)品所需滑橇數(shù)量小于限制數(shù)量，則此圈此產(chǎn)品可使用所需求的滑橇數(shù)。若所需滑橇數(shù)量大于限制數(shù)量，則在此圈使用此產(chǎn)品的所有滑橇（沒有空支架）。當此圈結束后，下一圈安排相同顏色的量大的異種產(chǎn)品進入噴漆，以此類推即可滿足換色次數(shù)最少。

將每圈的顏色能夠最大利用的滑橇數(shù)看作節(jié)點f由支架上限作為限制），尋找其他的顏色中零件種類不重復的節(jié)點，依次尋找使之構成哈密頓通路。若存在多個換色次數(shù)相同且換色次數(shù)最少的哈密頓通路，則他們在換色成本的消耗是相同的。

3.5模型求解

偽代碼：

求單圈每種顏色能夠使用的滑橇數(shù)：Use_num（color）：

要使N最小（實際上最小值為k-1），必得Ji=1，i=1，2，...k。說明顏色相同的零件連續(xù)加工。

注意：各個圈任務相同，必須按給哈密頓回路排序，這樣第一個圈放置k個過渡板。

綜合第一步和第二步，要使更換支架的時間最少，8個圈的加工為周期等量加工。

前七圈的滑塊數(shù)如表3所示（見251頁）（前七圈按照周期性，每圈都一樣），第八圈進行微部調整。

4結束語

通過哈密頓通路和回路分別求出8圈的排序和第1個圈的排序，由于考慮到支架的時間，要每圈任務相同，這樣有的任務要多完成?？赡苡械娜蝿胀瓿刹涣耍@樣最后一圈要調整?？赡茉斐梢徊糠值睦速M或者最后一圈有一定多的人工干預來調整。通過哈密頓圖模型排列顏色的順序，再人工排每個顏色的零件順序（根據(jù)約束條件），可以更快求出最優(yōu)解。