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

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

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

中圖分類(lèi)號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2020）10-0248-04

1背景

在汽車(chē)零件的生產(chǎn)過(guò)程中，需要對(duì)不同類(lèi)型的零件進(jìn)行噴漆上色，而在噴漆的過(guò)程中，由于僅有有限個(gè)噴漆裝置，而對(duì)于不同顏色的噴漆，需要進(jìn)行換色，在換色過(guò)程中便不免會(huì)產(chǎn)生消耗，如果因?yàn)樵诓煌χ邢嗤幪?hào)滑橇上擺放的零件種類(lèi)發(fā)生變化時(shí)需要人工進(jìn)行更換對(duì)應(yīng)支架，為了減少人工負(fù)擔(dān)，盡可能換色的次數(shù)減少。因此需要對(duì)零件進(jìn)行排程，針對(duì)已知的指導(dǎo)生產(chǎn)量制定出生產(chǎn)線(xiàn)未來(lái)八圈的詳細(xì)噴涂排序計(jì)劃，不僅要為了降低生產(chǎn)成本減少換色的次數(shù)，并盡可能地滿(mǎn)足指導(dǎo)生產(chǎn)量的需求（可以允許超過(guò)計(jì)劃生產(chǎn)量的產(chǎn)出，但不會(huì)帶來(lái)額外的直接收益）。

2問(wèn)題分析

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

3模型建立

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

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

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

3.2模型假設(shè)

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

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

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

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

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

3.3定義與符號(hào)說(shuō)明

3.4模型搭建

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

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

3.5模型求解

偽代碼：

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

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

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

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

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

4結(jié)束語(yǔ)

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