特許連鎖模具制造網(wǎng)格下的制造單元啟發(fā)式調(diào)度算法*

陳 娟，王宗忠

(1.廣東工貿(mào)職業(yè)技術(shù)學(xué)院，廣州 510510;2.廣東工業(yè)大學(xué)，廣州 510090)

1 特許連鎖模具制造網(wǎng)格下的制造單元

目前我國(guó)模具制造業(yè)尚處于不發(fā)達(dá)階段:大多數(shù)模具制造企業(yè)規(guī)模小，缺乏關(guān)鍵設(shè)備，加工手段原始，生產(chǎn)效率低下;企業(yè)各自為戰(zhàn)，分散化經(jīng)營(yíng)，行業(yè)整體聯(lián)系松散;模具設(shè)計(jì)、工藝與操作流程不規(guī)范，質(zhì)量無法保證;模具生產(chǎn)管理流程不規(guī)范，無法有效控制制造成本和交貨期。反觀國(guó)際模具制造市場(chǎng)的最新發(fā)展趨勢(shì)，一些大型生產(chǎn)廠商一直試圖減少模具供應(yīng)商的數(shù)量以減少管理的復(fù)雜性，并增大采購(gòu)批量獲得折扣來降低成本，此外，延遲付款和分期付款的付款方式業(yè)經(jīng)成為入圍大企業(yè)供應(yīng)商的必須服從的條款。這些弊端造成了我國(guó)模具尤其是大型、精密、復(fù)雜、長(zhǎng)壽命模具供不應(yīng)求的局面，使得國(guó)內(nèi)大多數(shù)模具企業(yè)缺乏國(guó)際市場(chǎng)競(jìng)爭(zhēng)力，不具備承接大公司或大模具訂單的能力。弱化或打破企業(yè)間的壁壘，進(jìn)行行業(yè)資源整合是擺在全行業(yè)面前重要而迫切的課題。針對(duì)這種情況，筆者所在的研究小組提出了用特許連鎖的經(jīng)營(yíng)模式來改造模具行業(yè)的新思路［1-2］。我們認(rèn)為，根據(jù)中國(guó)模具行業(yè)的現(xiàn)狀，特許連鎖是實(shí)現(xiàn)行業(yè)資源整合的較好方式。同時(shí)，我們借鑒了近幾年國(guó)內(nèi)外一些專家學(xué)者提出的開放式網(wǎng)格服務(wù)結(jié)構(gòu)OGSA［3］來構(gòu)造模具制造系統(tǒng)?；谀＞咧圃熘匈Y源配置的重要性和困難性，我們將物理意義上的制造資源與相應(yīng)的基本管理方法相結(jié)合，形成具有提供某類服務(wù)能力的制造網(wǎng)格單元，對(duì)其進(jìn)行標(biāo)準(zhǔn)化封裝，并提供一組接口，所有的網(wǎng)格服務(wù)都通過這些接口實(shí)現(xiàn)。簡(jiǎn)單和基礎(chǔ)的服務(wù)可以形成更復(fù)雜、更高級(jí)、更抽象的服務(wù)，這樣層層迭進(jìn)就可以十分方便的實(shí)現(xiàn)資源配置的快速性和高效性、制造過程的標(biāo)準(zhǔn)化以及制造系統(tǒng)的擴(kuò)展。例如，我們將設(shè)計(jì)、加工、裝配、存儲(chǔ)、運(yùn)輸?shù)戎圃飙h(huán)節(jié)看作服務(wù)過程，將內(nèi)部的資源，如設(shè)備和人力資源，連同其中的計(jì)劃過程、調(diào)度過程以及管理過程一起封裝成制造網(wǎng)格系統(tǒng)的組成元素——網(wǎng)格單元，該單元只通過接口與外界聯(lián)系，完成相應(yīng)的制造服務(wù)(任務(wù))。將上述特許連鎖經(jīng)營(yíng)理念與網(wǎng)格化制造模式相結(jié)合得到模具特許連鎖制造網(wǎng)格的示意圖如圖1所示。

圖1 模具特許連鎖制造網(wǎng)格

在統(tǒng)一承接了客戶的模具訂單后，作為網(wǎng)格中心的連鎖總部(大型模具企業(yè))將訂單以企業(yè)制造項(xiàng)目(在模具企業(yè)，一套模具為一個(gè)項(xiàng)目)的方式來進(jìn)行管理，從事以下幾方面的工作:①承擔(dān)主要的訂單設(shè)計(jì)任務(wù)(這是因?yàn)榇蠖鄶?shù)模具企業(yè)不具有設(shè)計(jì)能力)，如果某些加盟企業(yè)具有小訂單的設(shè)計(jì)能力，可考慮將設(shè)計(jì)任務(wù)分配給它們;②制定項(xiàng)目物流規(guī)劃方案，確定項(xiàng)目所需的物料數(shù)量、種類，采購(gòu)這些物料的時(shí)機(jī)，這些物料在各個(gè)存儲(chǔ)單元之間的合理分布，選擇何種運(yùn)送路線等等;③制定實(shí)際制造任務(wù)分配方案，即按各個(gè)加盟企業(yè)的實(shí)力將項(xiàng)目(如果企業(yè)能夠承擔(dān)整個(gè)項(xiàng)目)或工件任務(wù)分配給它們;④對(duì)加盟企業(yè)項(xiàng)目或任務(wù)執(zhí)行過程進(jìn)行監(jiān)控，包括質(zhì)量控制，成本控制和進(jìn)度控制。對(duì)加盟企業(yè)而言，要考慮的是如何將連鎖總部分配的項(xiàng)目(如果是項(xiàng)目則先要對(duì)項(xiàng)目進(jìn)行分解)或任務(wù)，與提供該項(xiàng)服務(wù)的某個(gè)具體網(wǎng)格單元(設(shè)計(jì)、制造、倉儲(chǔ)、運(yùn)輸?shù)?匹配，匹配所依據(jù)的信息主要是每個(gè)網(wǎng)格單元的能力和動(dòng)態(tài)負(fù)荷。對(duì)網(wǎng)格單元而言，在承接了某項(xiàng)具體的網(wǎng)格需求后，其所要決策的是單元內(nèi)部具體設(shè)備和人員的實(shí)時(shí)調(diào)配問題，即確定某項(xiàng)任務(wù)由哪個(gè)人/哪臺(tái)設(shè)備何時(shí)開始、何時(shí)完成。具體到制造單元，它負(fù)責(zé)將上層加盟企業(yè)分發(fā)下來的生產(chǎn)訂單(零部件生產(chǎn)計(jì)劃)進(jìn)行分解，并根據(jù)底層設(shè)備控制層的生產(chǎn)信息編制詳細(xì)作業(yè)計(jì)劃，將各作業(yè)在各加工資源上排序，并在生產(chǎn)執(zhí)行過程中通過生產(chǎn)跟蹤反饋的信息及時(shí)對(duì)計(jì)劃進(jìn)行調(diào)整。

2 模具網(wǎng)格制造單元生產(chǎn)調(diào)度

要根據(jù)模具生產(chǎn)的特點(diǎn)來界定模具網(wǎng)格制造單元生產(chǎn)調(diào)度問題的性質(zhì)。首先，模具的每個(gè)零件包含多道工序，每道工序由不同種類的機(jī)器加工而成，因而模具制造單元生產(chǎn)調(diào)度屬于多機(jī)問題。第二，模具生產(chǎn)是面向訂單的，訂單的獲得具有很大的隨機(jī)性，這意味著從上層加盟企業(yè)層分配到模具制造單元的生產(chǎn)訂單(工件)是陸續(xù)不斷的、不定時(shí)的，因而模具制造單元生產(chǎn)調(diào)度屬于動(dòng)態(tài)調(diào)度。第三，模具生產(chǎn)是單件生產(chǎn)，一般每種模具只生產(chǎn)一套，因此到達(dá)模具制造單元的工件其工藝路線一般不同，因而模具制造單元生產(chǎn)調(diào)度屬于Job-Shop問題。另外，在對(duì)模具企業(yè)進(jìn)行調(diào)研的過程中，我們發(fā)現(xiàn)，模具零件的工藝路線一般是由參加過該套模具設(shè)計(jì)的設(shè)計(jì)人員擔(dān)任工藝計(jì)劃員預(yù)先確定的，模具零件就依照這條工藝路線來加工，只在極個(gè)別的情況下，才會(huì)發(fā)生工藝路線的改變。故在本文中，擬按確定工藝路線來討論模具制造單元生產(chǎn)調(diào)度問題。第四，在模具的加工過程中，突發(fā)事件多，且工件加工時(shí)間等參數(shù)不確定，故模具制造單元生產(chǎn)調(diào)度屬于隨機(jī)性問題。最后，模具生產(chǎn)的目標(biāo)是要在保證模具質(zhì)量和交貨期的基礎(chǔ)上，最大限度地降低生產(chǎn)成本，提高企業(yè)收益。故模具制造單元生產(chǎn)調(diào)度通常屬于多目標(biāo)決策問題。

總而言之，模具制造單元生產(chǎn)調(diào)度屬于多機(jī)、多任務(wù)、有復(fù)雜約束、不同任務(wù)具有不同工藝路線、任務(wù)不斷不定時(shí)輸入輸出的Jop-shop類隨機(jī)調(diào)度，是生產(chǎn)調(diào)度問題中較復(fù)雜的一類，屬于NP完全問題。它的基本任務(wù)是圍繞模具零件的加工制造，解決并行加工的多個(gè)零件如何共享有限資源以最大限度地滿足加工成本、交貨期的問題。它不但要對(duì)零件的各道工序任務(wù)在各個(gè)資源上的加工順序和時(shí)間進(jìn)行安排，而且要監(jiān)控制造單元生產(chǎn)中出現(xiàn)的意外情況(包括上層加盟企業(yè)下達(dá)的生產(chǎn)訂單信息的改變和下層設(shè)備控制層反饋的異常信息)對(duì)原先做好的工序任務(wù)安排進(jìn)行實(shí)時(shí)的再調(diào)整，是一個(gè)持續(xù)更新、動(dòng)態(tài)變化的過程。

3 基于優(yōu)先規(guī)則的啟發(fā)式調(diào)度算法

與其它算法相比，啟發(fā)式算法具有以下優(yōu)點(diǎn)［4］:①收斂速度快，能在較短的時(shí)間內(nèi)得到讓人滿意的解;②算法編程簡(jiǎn)單，易于實(shí)現(xiàn)且容易修改;③不需要建立問題的數(shù)學(xué)模型;④是針對(duì)求解的某類具體問題設(shè)計(jì)的，依賴于問題的具體特征，利用了專門的知識(shí)和經(jīng)驗(yàn)，只要設(shè)計(jì)得當(dāng)就可能得到特定問題的較優(yōu)解?；诖?，本文針對(duì)模具制造單元生產(chǎn)調(diào)度問題設(shè)計(jì)了一種基于優(yōu)先規(guī)則的可進(jìn)行并行作業(yè)調(diào)度的啟發(fā)式算法［5］，現(xiàn)用類C語言來描述該啟發(fā)式算法:

4 算法驗(yàn)證與分析

設(shè)某模具制造單元的機(jī)器情況如表1:

表1 模具制造單元機(jī)器設(shè)備

現(xiàn)有6個(gè)工件同一周期排產(chǎn)，它們的工藝路線、工序加工時(shí)間、工序加工成本、交貨期如表2(注:表中C(5，10)(7，8)表示某道工序要用CNC機(jī)床加工，用C1加工的時(shí)間是5、成本是10，用C2加工的時(shí)間是7，成本是8):

表2 工藝計(jì)劃

根據(jù)上述算法獲得生產(chǎn)計(jì)劃的甘特圖如圖2所示。

圖2 甘特圖

J1、J2、J3、J4、J5、J6 的完工時(shí)間分別是 16、25、28、37、19、23，即只有J4有少量誤工。工件加工的總成本為(10+4+6)+(4+6+3+6)+(5+6+9+6)+(8+5+5+6+6)+(6+5+5)+(2+6+7+7+4)=137，加工成本應(yīng)當(dāng)在119和154之間變動(dòng)。

工件的加工情況和機(jī)器的利用情況如表3、表4所示。

表3 工件加工情況

表4 機(jī)器利用率

經(jīng)過多次變換單元內(nèi)各類機(jī)器的數(shù)目和工件加工路線，仍然用該算法來進(jìn)行作業(yè)排序，仿真結(jié)果都證明該種啟發(fā)式算法基本能夠滿足誤工工件數(shù)量少、兼顧加工成本盡可能小的原則，并且該種算法具有一定的收斂速度。在此不一一列出。

5 結(jié)束語與創(chuàng)新點(diǎn)

實(shí)際上，單純從算法的角度來看，對(duì)本文所探討的制造單元生產(chǎn)調(diào)度問題的給定實(shí)例，該種啟發(fā)式調(diào)度算法只包含對(duì)工件和機(jī)器的有限搜索、排序及不等式判斷，其時(shí)間復(fù)雜度應(yīng)是實(shí)例大小的多項(xiàng)式，可以快速對(duì)問題求解。同時(shí)，由于該算法在每個(gè)均分時(shí)段的起始時(shí)刻搜索在某類機(jī)器上等待排產(chǎn)的工件的工序任務(wù)及其個(gè)數(shù)、某類機(jī)器的可用機(jī)床個(gè)數(shù)，因此該算法可實(shí)現(xiàn)對(duì)實(shí)際生產(chǎn)過程中上層加盟企業(yè)和下層設(shè)備異常情況的及時(shí)反應(yīng)并對(duì)生產(chǎn)計(jì)劃作出及時(shí)調(diào)整，能夠滿足特許連鎖網(wǎng)格制造單元的生產(chǎn)調(diào)度需求。

本文創(chuàng)新點(diǎn):①本文的調(diào)度算法是針對(duì)特許連鎖經(jīng)營(yíng)模式下的模具網(wǎng)格制造單元制定的;②該調(diào)度算法是一種新的行之有效的基于規(guī)則的啟發(fā)式算法。

［1］陳慶新，田文生，陳新，等.特許連鎖模式下的模具制造網(wǎng)格系統(tǒng)架構(gòu)［J］.計(jì)算機(jī)集成制造系統(tǒng)，2003，9(7):595-600.

［2］陳娟，陳慶新，陳新.特許連鎖經(jīng)營(yíng)模式下的模具制造系統(tǒng)建模［J］.制造業(yè)自動(dòng)化，2004(增刊):58-66.

［3］Foster I，Kesselman C，Nick J et al.The Physiology of the Grid:An Open Grid Services Architecture for Distributed Systems Open Grid Service Infrastructure.Global Grid Forum，2002.

［4］刑文訓(xùn)，謝金星.現(xiàn)代優(yōu)化計(jì)算方法［M］.北京:清華大學(xué)出版社，1999.

［5］毛寧，劉霞，林潔瑜.關(guān)于M類機(jī)器的非流水復(fù)雜作業(yè)排序問題的一種啟發(fā)式算法［J］.工程數(shù)學(xué)學(xué)報(bào)，1996，6(13):65-73.