基于時延庫所Petri網的動態聯盟任務調度研究

黃 彬1, 2，高誠輝1, 2，陳 亮1

?

基于時延庫所Petri網的動態聯盟任務調度研究

黃 彬，高誠輝，陳 亮

（1. 福州大學機械工程及自動化學院，福建福州 350108；2. 福建省制造業數字化設計工程研究中心，福建福州350002）

針對動態聯盟中任務調度的特點，提出了采用時延庫所Petri網對動態聯盟任務調度進行建模。給出了模型的形式化描述及變遷規則，對動態聯盟中的產品加工類型進行了分類，并建立了各種加工類型的時延庫所Petri網模型，分析了通過模型中零時差的庫所求解關鍵路徑和利用可達圖求解合理調度方案的方法。最后，以實例表明了該方法的可行性和有效性。

任務調度；時延庫所Petri網；動態聯盟

敏捷制造是美國于1991年在“美國21世紀制造戰略報告”中提出的一種新的制造模式，被稱為“21世紀制造企業的戰略”。在敏捷制造模式下，借助動態聯盟這種組織形式，盟主企業通過快速集成動態聯盟內各成員企業的核心優勢，進行快速的產品設計、制造、銷售和服務，向用戶提供各種符合個性要求的定制化產品，使企業能夠從容應對快速變化的市場需求，最終贏得市場競爭。對于敏捷制造而言，生產運作仍然是其最基本的活動，要實現敏捷制造的目標，關鍵在于如何組織來自于動態聯盟內不同企業實體的各種資源，快速實現共同的市場機會。

動態聯盟中的任務調度（企業間的調度）與傳統的車間調度不同。首先，動態聯盟中的各成員企業都是利益自治體，相互之間不存在強制的集中式控制（包括盟主企業對成員企業）。其次，每個成員企業只負責整個產品的某個或某些部件的生產，成員之間對各自內部的生產過程不了解。但由于不同產品部件的生產存在時序約束關系，使得成員企業不能不考慮其他成員企業的生產進度對本企業生產過程的影響以及本企業的進度對整個聯盟的影響等，這就要求成員企業之間的生產過程必須彼此協調，因此動態聯盟企業的調度問題對傳統的生產調度方法提出了新的挑戰。通常采用的解析法、神經網絡、遺傳算法等純數學方法已不能解決動態聯盟企業任務調度的問題。

Petri網是聯邦德國的Carl Adam Petri教授于1962年首次提出的一種網絡理論，它是一種圖形化的建模工具，特別便于描述分布式系統中進程或部件的順序、并發、沖突以及異步關系。為了模擬和分析系統在時間層次上的關系，又定義和研究了各種含時間因素的Petri網。目前，研究人員在基于Petri網模型的調度方法方面做了很多工作，但多見于車間調度問題。本研究采用時延庫所Petri網對動態聯盟任務調度進行建模，建立了動態聯盟中各種加工類型的時延庫所Petri網模型，所有變遷的觸發都是瞬時的，通過在庫所上增加一個延時來描述動態聯盟任務進行時的持續時間。

1 基本概念

定義1 時延庫所Petri網是一個六元組

TPPN= (,,,,,)

式中為TPPN的庫所集，表示某項任務，用布爾量表示，容量為1；為TPPN的變遷集，表示某項任務的開始或結束，和滿足；：，：，這里，和的權系數均為1；：→（為非負整數集），表示所有庫所的時延集，即完成中托肯所對應的任務需要的時間；為系統的初始標識。TPPN是一個出現網，即TPPN滿足：

在敏捷制造模式下，由于許多任務都是一次性的，完工時間的不確定性較大，所以一般給出3個估計值：，，，其中表示最樂觀時間，表示最保守時間，表示最可能時間，然后應用概率的方法計算各項任務時間的期望平均值，任務時間的期望平均值，TPPN網中的指的就是任務完成時間的期望平均值。

定義2 變遷觸發條件

定義3 變遷觸發結果

如果在下可以被激活，當前標識相應改變為后繼標識，有并且，中的托肯經過時延后可用，這一變遷可以表示為[。

2 基于時延庫所Petri網的任務調度建模

一項需敏捷制造完成的產品經過分解成若干個零部件后，即形成了若干個加工任務，由若干個相應的聯盟成員完成。動態聯盟內，在產品的完成過程中包含了以下幾種加工類型：一般加工、順序加工、并行加工、裝配。一般加工指一個零部件的完成對應于一個加工任務，該加工任務由一個聯盟成員負責完成；順序加工指一個零部件的完成對應于若干個加工任務，每一個加工任務由一個聯盟成員負責完成，并且在每一個加工任務間存在前后道工序關系；并行加工指若干個加工任務在某個時間段可以同時進行；若干個零件經由裝配環節形成部件，若干個部件經由裝配環節形成更大的部件，直至最終形成整個產品。

一般加工的TPPN模型可用兩個變遷t和t以及一個庫所表示，如圖1所示。其中t表示加工任務的開始，t表示加工任務的結束，庫所中有一個托肯時表示加工任務正在進行，的時延d表示從t發生（獲得托肯）開始，至少要經過d個時間單位，t才能發生。

圖1 一般加工的TPPN模型

順序加工的TPPN模型如圖2所示。該模型表示加工任務是加工任務的前道工序，d表示零部件從完成任務的加盟成員到達承擔任務的加盟成員所需的物流時間。當d＝0，即不考慮物流時間時，可將p去除，加工任務的t和加工任務的t重合，圖2簡化為圖3所示。由于物流時間的不確定性和網模型的復雜性，本研究不考慮物流時間因素，即順序加工的TPPN模型以圖3為據。

圖2 順序加工的TPPN模型

圖3 不考慮物流時間的順序加工TPPN模型

圖4 并行加工的TPPN模型

表示由兩個一般加工任務完成的零部件組成裝配的TPPN模型如圖5所示。存在裝配關系的兩個零部件1和2都完成后，裝配才能開始，用t表示，經時延d，裝配結束于t。

圖5 裝配的TPPN模型

3 TPPN任務調度模型的分析與求解

3.1 模型的分析

（2）

（3）

（5）

（6）

3.2 模型的求解

具體的模型求解步驟如下：

（1）根據已知的、、值，計算各任務完工的期望平均時間和方差。

（2）畫出產品加工的TPPN模型。

（3）以各任務完工的期望平均時間作為完工時間，根據公式(1)~(4)計算出TPPN模型中的、以及，并求出產品的關鍵路徑。

（4）畫出TPPN模型的可達圖，并根據公式(5)、公式(6)求出圖中的和。

4 實 例

針對市場機遇，若干家企業組成動態聯盟生產某產品。產品分解后得到的加工任務，各任務之間的前后工序關系、各任務的、、值及經計算得到的各任務的期望平均工期如表1所示。

由表2得產品加工的關鍵路徑為：A→B→H→F→G→L。

表1 產品的任務組成、任務的前后工序關系及工期

圖6 產品加工的TPPN模型

從表3可以看出，合理的M為：M、M、M、M、M、M、M、M、M、M。M的存在時間區間為[0,6]，從圖7知道，在M狀態下，只有任務A進行；M的存在時間區間為[6,13]，在M狀態下，只有任務B進行；M的存在時間區間為[13,27]，在M狀態下，任務C、D、H、I、J并行進行；M的存在時間區間為[21,32]，在M狀態下，任務C、E、H、I、J并行進行；M的存在時間區間為[23,27]，在M狀態下，任務C、D、H、I、K并行進行；M的存在時間區間為[32,36]，在M狀態下，任務C、F、I、J并行進行；M的存在時間區間為[23,32]，在M狀態下，任務C、E、H、I、K并行進行；M的存在時間區間為[32,40]，在M狀態下，任務C、F、I、K并行進行；M的存在時間區間為[40,51]，在M狀態下，任務C、G、K并行進行；M的存在時間區間為[51,55]，在M狀態下，只有任務L進行。

合理的調度方案有三種：

M→M→M→M→M→M→M→M

M→M→M→M→M→M→M→M

M→M→M→M→M→M→M→M

由此，畫出任務調度的Gantt圖，如圖8所示。

圖7 圖6的可達圖

表3 圖7中Mi的ES(Mi)和LF(Mi)值

圖8 任務調度的Gantt圖

5 結束語

本研究利用時延庫所Petri網對動態聯盟的任務調度進行了建模分析與求解，反映出了其中多任務間的并發、異步等動態行為，該模型不僅可以及時了解產品各個組成部分的生產進展，也可根據實際生產狀況動態修改原計劃調度或進行再調度，以適應不斷變化的新環境，提升企業的敏捷性。

[1] 羅振璧, 汪勁松, 周兆英, 等. 靈捷制造——21世紀制造企業的戰略[J]. 機械工程學報, 1994, 30(4): 1-6.

[2] Yusuf Y Y, Sarhadi M, Gunasekaran A. Agile manufacturing: the drivers,concepts and attributes [J]. International Journal of Production Economics, 1999, 62: 33-43.

[3] [美]Rick Dove. 敏捷企業(上)[J]. 張申生譯. 中國機械工程, 1996, 7(3): 22-27.

[4] 袁崇義. Petri網原理與應用[M]. 北京: 電子工業出版社, 2005. 2-7.

[5] 吳哲輝. Petri網導論[M]. 北京: 機械工業出版社, 2006. 1-19.

[6] Murate T. Petri nets: properties, analysis and applications [J]. Proceedings of IEEE, 1989, 77: 541-580.

[7] Bowden F D J. A brief survey and synthesis of the roles of time in Petri nets [J]. Mathematical and Computer Modelling, 2000, 31: 55-68.

[8] Lee D Y, Dicesare F. Scheduling flexible manufacturing systems using Petri nets and heuristic search [J]. IEEE Transaction on Robotics and Automation, 1994, 10(2): 123-132.

[9] Chen J H, Fu L C, Lin M H, et al. Petri-net and GA-based approach to modeling, scheduling, and performance evaluation for wafer fabrication [J]. IEEE Transaction on Robotics and Automation, 2001, 17(5): 619-636.

[10] Mahas G, Parisa A B, Peter L, et al. Petri-net based formulation and algorithm for short-term scheduling of batch plants [J]. Computers and Chemical Engineering, 2005, 29: 249-259.

Research on Virtual Enterprises Task Scheduling Based on Timed Place Petri Net

HUANG Bin,GAO Cheng-hui, CHEN Liang

( 1. College of Mechanical Engineering and Automation, Fuzhou University, Fuzhou Fujian 350108, China; 2. Fujian Province Digital Design Center for Manufacturing, Fuzhou Fujian 350002, China )

Considering the characteristics of virtual enterprises task scheduling, timed place Petri-net(TPPN) based approach is proposed to model the task scheduling. On the basis of formal definition and transition rules of the TPPN, product manufacturing types in virtual enterprises are classified, and the TPPN model of each kind of manufacturing is provided, then the methods of resolving critical path with place zero activity floats and solving reasonable scheduling scheme with reachability graph are analyzed. Finally, the simulation of a case indicates that the approach is feasible and effective.

task scheduling; timed palce Petri-net; virtual enterprises

TH 165

A

1003-0158(2011)01-0148-06

2009-04-01

國家自然科學基金資助項目（50875049）；福建省重大科技資助項目（2007H2011）；福建省教育廳科技資助項目（JA09031）

黃 彬（1971-），男，江西南昌人，副教授，博士研究生，主要研究方向為敏捷制造、制造系統工程。