摘要：

有效的調度方法與優化技術的研究和應用，已成為先進制造技術實踐的基礎和關鍵。本文就車間調度問題的研究狀況，探討了SMT產品制造企業車間調度建模的研究方法，在面向對象的Petri網基礎上,引入依賴消息,提出了一種擴充的面向對象Petri網(EOPN)模型,并建立了一臺貼片機系統的完整的EOPN模型。

關鍵詞：

SMT；車間調度；Petri網

0. 前言
隨著電子產品向微型化、便攜式、網絡化和多媒體方向迅速發展，SMT(Surface Mount Technology 表面貼裝技術)在電子工業中正得到越來越廣泛的應用。如何提高SMT系統的生產效率，如何對SMT產品制造企業的車間調度進行優化，這一技術問題就提到了人們的視野中。對于SMT產品制造企業來講，要想在激烈的競爭中取勝，最重要的是使SMT生產線發揮最大的效率，提高合格產品的產量。然而，要達到這一目標，必然會受到諸多因素的影響。所以必須對SMT 產品制造過程的車間調度進行優化，才可以實現高效生產。當代產品開發和交付周期大大縮短，多品種、小批量、用戶定制化的生產逐漸流行起來。這種生產方式使得生產的計劃、組織和控制變得更加復雜，并要求對制造過程中產生的各類信息進行及時的反饋和處理。因此,通過利用計算機技術實現車間調度計劃優化，快速調整資源配制,統籌安排生產進度，以較低的成本按期交付用戶滿意的產品，對于提高企業自身的競爭力,具有重要意義。

車間調度會經常遇到生產計劃停滯、變更的情況，如在生產過程中發現設計或工藝文件的缺陷或不夠完善，或在檢驗加工件時發現超差,就需要等待技術人員處理；如在加工中遇到進度緊張、資源沖突或外協、外購的零部件、材料等無法在預定期限內交付使用,就需要調度人員及時協調。因此，車間調度與控制技術是實現生產高效率、高柔性和高質量的關鍵。車間生產過程的調度問題，是制造系統運籌技術、管理技術與優化技術發展的核心。

1. 車間調度問題的描述
1.1 車間調度問題的描述及其發展過程
從數學規劃的角度看，車間調度問題可表達為在等式或不等式約束下，對一個或多個目標函數的優化?，F代典型的車間調度問題是:將作業均衡地安排到各處理機上，并合理地安排作業的加工次序和開始時間，使約束條件被滿足，同時優化一些性能指標。調度問題的研究始于20世紀50年代，Johnson提出了解決n/2/F/Cmax和部分特殊的n/3/F/Cmax問題的優化算法，代表調度理論研究的開始；60-70年代建立了調度理論的主體(經典調度理論)并重視調度復雜性的研究。隨著70年代后期調度理論研究的深人及各種交叉學科的發展，又涌現出了許多新的車間調度理論與方法。

1.2車間調度問題的分類與特點
對于車間調度問題，有的學者進行了分類整理。按照不同的分類標準，可分為以下6種類型①開環車間和閉環車間。②單臺處理機、多臺并行機、Flow shop和Job shop。③基于調度費用和基于調度性能的指標。④確定性調度、隨機性調度。⑤靜態調度，動態實時調度。⑥有序加工，無序加工。
現代車間調度類型往往是Job shop型的，其調度問題有以下特點：①建模復雜性。②計算復雜性。③動態隨機性。④多約束性。⑤多目標性。

1.3 SMT產品制造系統車間調度問題的描述
SMT產品制造系統的車間調度優化對象為SMT 生產線，并且配置的機器設備可能各不相同。有的生產線就是通常意義上的主要由絲網印刷機，高速貼片機，多功能貼片機，回流焊爐以及一些輔助設備組成。有的生產線在此基礎上添加了AOI在線檢測設備，分別配置在絲網印刷機后、多功能貼片機后、回流焊爐后。這種生產線主要用于要求精度很高的印制板的生產，可以實現在線檢測，找出不良品進行返修。還有的生產線在以上的基礎上又增加點膠機和波峰焊爐，以實現不同規格的印制板的生產。同時，在每條生產線上都裝備一些輔助設備，如：上板機、下板機、翻板機、轉板機，以及PCB傳輸線、SMC/SMD備料架與備料庫、各種動力驅動設備等。每一條生產線的主要設備之間都通過傳輸設備與其它生產線相連接，這樣就構成一種網狀的制造單元，使各條生產線之間能夠協同工作。使這些生產線能夠在生產不同規格的印制板時能夠高效的生產是車間調度優化的目標。

1.4 SMT產品制造系統的車間調度與其他制造系統車間調度問題的區別
傳統的制造系統車間調度分為作業車間調度問題(Job Shop Scheduling Problem, JSSP)和流水車間調度問題(Flow Shop Scheduling Problem, FSSP)兩種類型，在JSSP中，產品品種多、數量少、加工路徑短且有隨機性，其任務就是在滿足工件工藝路線要求的前提下，為各個工件尋找一條有時間限制的路線，使得工件按照這種有時限的路線能夠順利生產出來；在FSSP中,產品單一、大批量生產、加工路徑相對固定。每種產品，盡管材料規格不同，整個車間總是采用同樣的流程。實際上，流水車間調度問題是JSSP的一個特例，它是在JSSP的基礎上統一了工件流經加工網絡的路線，因而比一般的JSSP大大簡化。而在SMT產品制造系統中，既有面向庫存的大批量生產，也有面向定單的生產，只在有訂單需求下才生產；更多的是根據顧客需求量身定做，不但產品種類繁多，各類產品需求量亦多不大。所以，SMT產品制造系統的車間調度問題是不同于JSSP和FSSP的混合型制造系統，其典型特征是生產分階段進行，設備按階段使用，在不同的生產階段遵循不同的生產方式?；诖? SMT產品制造系統的車間調度優化問題用傳統算法很難解決，難點主要有兩個方面：一是問題描述難，二是求解難。這也正是SMT產品制造系統區別于一般制造系統的重要特點。

2.  車間調度問題的建模方法
一般的車間調度都是對于具體生產環境中復雜動態、多目標、多約束調度問題的一種抽象和簡化，其首要問題是對制造系統進行建模。目前建模方法很多，主要有以下兩大類。

2.1圖與網絡方法
作為制造系統主要的建模方法，主要有活動循環圖、關鍵路徑法、組合網絡、Petri網、GRAI網等，而其中Petri網以其獨特的優勢廣泛應用在制造系統的設計、分析與仿真中。這里，主要介紹一下Petri網。

(1)基本Petri網。
基本Petri網模型具有直觀易理解的優點，但其在描述復雜系統時節點數目過多，因而只適用于簡單制造系統的建模。

 (2)擴展Petri網。
這里介紹幾種典型擴展Petri網。①EP-N模型。它通過增加決策節點，使Petri網具有描述諸如FMS調度決策過程的能力。這種模型有節點數目過多的缺點，只適用于簡單系統的建模。②CP-N模型。CP-N是Petri網的壓縮形式，同基本Petri網相比它具有較少的節點數目，較適合復雜系統的建模，但其分析方法較為復雜。③TP-N模型。它不僅能夠描述系統中事件和狀態演化中的邏輯關系，而且通過設置時間與變遷或庫所的聯系來分析Petri網演化過程。有的學者將TP-N應用到了FMS的局域網建模、控制和仿真當中。④P/TP-N模型。這種網比EP-N有更少的節點和更簡單的結構，但沒有決策節點。⑤HLP-N模型。將P/TP-N和CP-N結合起來，就組成了HLP-N模型。我國的學者嚴洪森在HLP-N和EP-N的基礎卜，提出了EHLEP-N，該網結構簡單、節點少，很適合于FMS的建模、仿真與控制。

(3) Petri網的最新發展。
隨著面向對象(OO)技術的發展與應用，人們開始研究如何將兩者結合起來，以增強Petri網的設計描述能力和功能實現能力，降低其建模和分析的系統依賴性與難度。Petri網技術與00技術的結合有以下兩種方式：Objects inside Petri Net和Petri Nets inside Objects，并將此類Petri網分為基于對象的Petri網(OBPN)、面向對象的Petri網(OOPN)和對象Petri網(OPN)。

2.2非圖或網絡的建模方法
這類方法主要有3種。
 (1)控制論的方法(主要為擾動分析法(PA)和極大代數法)。PA兼容了仿真法與理論分析的長處，同時也避免了單純用仿真法的大量計算和理論分析研究復雜問題所遇到的困難。它主要用于研究制造系統的性能指標(生產率等)對參數變化的敏感性，并以此為基礎對系統的運行進行優化。其缺點是:對多參數的擾動很難用表或狀態方程表示仿真運行過程，擾動較大時，近似度較差。極大代數法用與解決線性系統相類似的方法對DEDS進行建模。它根據系統的運行關系建立起一系列事件發生時間的關系方程。但用極大代數法時，必須在工件加工順序事先確定的條件下，才能進行建模分析，因而僅適合制造系統的性能分析，而不適合調度。

 (2)數學規劃法排隊網絡(QN)可以分析系統生產率、平均生產時間等，但它很難將車間的其他資源(如AGV等)考慮進去，很難處理系統出現異常時的情況。QN主要用于FMS初步的定性分析[6]、此外，常用的方法還有線性規劃(LP)法等。

(3)仿真法仿真是研究DEDS的另一常用方法，較常見的計算機仿真語言如SIMSCRIP-，SIMAN .ECSL，SIMON，SLAM，GPSS等等。仿真法的主要問題是代價高昂。

2.3 SMT產品制造系統車間調度的建模方法
本文提出一種基于對象的Petri網建模的方法。面向對象方法是當前較為先進的建模技術，它的主要思想是將系統所涉及的數據及相關的操作以對象對待，通過消息的傳遞機制讓對象完成其操作。Petri網處理復雜問題的辦法是對系統建立層次化和模塊化的模型，而面向對象思想可以把各個單元網更好地組織起來，可以直觀反映系統的結構和功能分布、并使建模過程符合人們的思維模式。由于Petri網有堅實的數學基礎作為依據，能夠比較精確地描述系統結構、系統事件之間的順序或并發關系、資源的約束、事件發生的條件以及引起的后果，并能夠進行有效的系統分析和仿真，因而被廣泛的應用于FMS 的建模和仿真。而SMT產品制造系統正是比較典型的柔性制造系統，而且 Petri網最重要的應用是系統建模以及在模型基礎上對系統進行分析，所以基于對象的Petri網建模方法是二者相結合較為有效的一種方式。
　
3. SMT產品制造系統的Petri網建模
3.1 擴充的面向對象Petri網（EOPN）定義
在一個OPN模型中，一個系統描述為可相互通信的物理對象和它們之間的聯系。在進一步引入依賴消息的EOPN中,可作如下定義。
定義1 ： S=(O，R ).
其中，O={Oi | i=1, 2, … , I , I∈N}，Oi是物理對象的EOPN，即EOPNi，Oi就是系統中所有物理對象(EOPNi)的集合。
R={Rij | i,j=1, 2, … , I ,  i≠j , I∈N} ，R是物理對象(EOPNi)間消息傳送關系的集合。
定義2 Oi=( Spi, Mpi, Ti, Fi, dep_MPi, dep_Fi, Mo）。

其中，SPi是Oi中的狀態庫所；MPi是Oi中的消息庫所；Ti是活動變遷集；Fi是Oi中活動變遷與狀態消息庫所之間的輸入輸出關系；dep_MPi為依賴消息庫所集，該集合中某一元素依賴于MPi中某一元素的存在而存在，在EOPN的圖形中表為虛線橢圓框；dep_Fi稱為依賴消息流關系，它是dep_MPi中某一消息庫所到Ti中某一變遷的有序偶集合，即dep_Fi 內含于dep_MPi×Ti， 在EOPN的圖形中表為有向虛線；Mo為初始標識。

一個物理對象的行為表現在兩個方面，一是其自身內部的行為變遷，二是外部的消息傳送。在這里，內部的行為變遷用狀態庫所和活動變遷來描述，而外部的不同對象間消息的傳送和接收是通過消息庫所來實現的。如對于消息發送對象Oi、消息接收對象Oj之間的通信用互連關系Rij(i≠j)表示，它定義為Rij={(MPi,Gij,MPj)}，其中Gij是一種特殊類型的變遷，稱它為門(Gate)。當在消息庫所MPi中有一托肯(token)或由外部指定控制規則時Gij被點火，一個消息庫所MPj可以接收一個消息(即token)的條件是消息發送對象中有托肯且Gij可被點火。

3.2 貼片機系統的描述
根據EOPN模型來為一貼片機(SMT)系統建模，以SIEMENSMS-102貼片自動拾放系統為例，其工作平臺如圖1所示。

貼片機系統是由CAD文件驅動的，該文件包括元件類型名稱、元件坐標值、位號等消息,需貼裝的元件放在可移動物料區內，機械手在可取區內一定的槽位上吸取一個元件，放置在PCB上的相應位置。當一個料位內的元件取完時，下一個可移動物料區前移進入機械手可取區內?？砂堰@個貼片機系統看成是由機械手、可移動物料區PCB軌道組成的。按EOPN模型的要求，可進一步抽象成為四個對象：機械手、PCB軌道、可移動物料區、指令集,其中指令集由CAD文件得到并包含元件所處的物料區號等消息。
圖2至圖5分別給出了PCB軌道的EOPN模型、指令集的EOPN模型、可移動物料區的EOPN模型和機械手的EOPN模型。

圖5中,用虛線橢圓框表示的依賴消息庫所MP43,含義是它的存在要依賴于另一個消息庫所MP42,即若未產生消息庫所MP42,則不會產生依賴消息庫所MP43;用有向虛線表示的從MP43到T44的依賴消息流關系含義是,活動變遷T44是否能夠發生變遷不完全依賴于消息庫所MP43,也就是說,當狀態庫所P44中有托肯存在時,若這時由于機器出現故障或由于人為干預而使機器暫停,則會產生一消息庫所MP42,在故障解除或工作人員查看完畢后發出故障恢復消息,即依賴消息庫所MP43,這時T44發生變遷條件滿足,機器從剛才暫停處繼續工作,否則,未發生故障.若消息庫所MP42不存在,則依賴消息庫所MP43也不存在,活動變遷T44的發生只與狀態庫所P44有關。

整個PCB貼裝的過程可以描述如圖6。其中的PCB放送器、PCB拾取器、PCB軌道、指令集、可移動物料區、機械手以及人等對象的內部行為對外是不可見的，它們之間的通信由消息庫所來完成，門負責系統的邏輯控制?？梢詾橐粋€制造系統中的每個對象的EOPN建立類庫(比如物理對象類、消息類等)，當有一個新的系統需要增加或者要對現有系統進行部分修改時，可從目前已有系統的EOPN類庫中派生出所需的EOPN，即，首先構造好新系統的EOPN，或抽取出原有系統中需修改部分的EOPN進行補充修改。然后將它們與原有系統的EOPN結合起來，形成所需新系統的完整的EOPN模型。在這樣的系統中，各個EOPN對應的物理設備的功能基本不會發生變化，而因新系統或某些補充部分的引入，故可能引起控制邏輯的改變，這時只須引入一些特殊的門來指定新系統的控制邏輯就可以了，從而提高了EOPN模型的模塊性和可重用性。

4. 結 論
本文通過對車間調度問題的分析，得到SMT產品制造企業車間調度的描述。并且針對現有Petri網在建模過程中存在的諸如結點數過多、面對復雜系統的決策能力不強及其關矩陣的空間過大等問題，提出了擴充的面向對象Petri網(EOPN)模型，并建立了一臺貼片機系統的完整的EOPN模型。從建模中可以發現，用EOPN建?？梢詫⑾到y的邏輯復雜性分解在建模的不同階段和不同的層次當中，而且模型結構與系統的實際結構可以很清晰的對應起來，可以很容易地發現模型中錯誤發生的地方。此外，由于EOPN模型采用分層建模，將方法作為類的子網，而在最終對整個系統，以及分析和性能評價時可以完全不考慮各對象的內部結構，這樣使得系統模型的規模與復雜度減小。EOPN模型的建立對SMT產品制造企業車間調度系統的優化及仿真的實現打下了基礎，是進行下一步研究的必要條件。

參考文獻：

1. 李培根、張 潔. 敏捷化智能制造系統的重構與控制［M］ 北京：機械工業出版社，2003
2. 江志斌. Petri網及其在制造系統建模與控制中的應用[M]. 北京: 機械工業出版社,2004.
3. 范玉順,曹軍威編著. 復雜系統的面向對象建模分析與設計. 清華大學出版社,2000,9
4. 方劍，席裕庚. FMS中的工件調度. 北京:高技術通訊. 2001(7)
5. Zuberek W M. Time Petri nets in modeling and analysis of the simple scheduling for manufacturing cells〔J〕.Computers and Mathematics  with Applications,1999,37(11-12)
6. Champagnat R, Esteban P, Ping aud H, Valette R. Petri net Based modeling of hybrids ystems〔J〕.Computers in Industry,1998,36(1-2)