黃 彬1, 2，高誠(chéng)輝1, 2，陳 亮1

?

基于時(shí)延庫(kù)所Petri網(wǎng)的動(dòng)態(tài)聯(lián)盟任務(wù)調(diào)度研究

黃 彬，高誠(chéng)輝，陳 亮

（1. 福州大學(xué)機(jī)械工程及自動(dòng)化學(xué)院，福建福州 350108；2. 福建省制造業(yè)數(shù)字化設(shè)計(jì)工程研究中心，福建福州350002）

針對(duì)動(dòng)態(tài)聯(lián)盟中任務(wù)調(diào)度的特點(diǎn)，提出了采用時(shí)延庫(kù)所Petri網(wǎng)對(duì)動(dòng)態(tài)聯(lián)盟任務(wù)調(diào)度進(jìn)行建模。給出了模型的形式化描述及變遷規(guī)則，對(duì)動(dòng)態(tài)聯(lián)盟中的產(chǎn)品加工類型進(jìn)行了分類，并建立了各種加工類型的時(shí)延庫(kù)所Petri網(wǎng)模型，分析了通過(guò)模型中零時(shí)差的庫(kù)所求解關(guān)鍵路徑和利用可達(dá)圖求解合理調(diào)度方案的方法。最后，以實(shí)例表明了該方法的可行性和有效性。

任務(wù)調(diào)度；時(shí)延庫(kù)所Petri網(wǎng)；動(dòng)態(tài)聯(lián)盟

敏捷制造是美國(guó)于1991年在“美國(guó)21世紀(jì)制造戰(zhàn)略報(bào)告”中提出的一種新的制造模式，被稱為“21世紀(jì)制造企業(yè)的戰(zhàn)略”。在敏捷制造模式下，借助動(dòng)態(tài)聯(lián)盟這種組織形式，盟主企業(yè)通過(guò)快速集成動(dòng)態(tài)聯(lián)盟內(nèi)各成員企業(yè)的核心優(yōu)勢(shì)，進(jìn)行快速的產(chǎn)品設(shè)計(jì)、制造、銷售和服務(wù)，向用戶提供各種符合個(gè)性要求的定制化產(chǎn)品，使企業(yè)能夠從容應(yīng)對(duì)快速變化的市場(chǎng)需求，最終贏得市場(chǎng)競(jìng)爭(zhēng)。對(duì)于敏捷制造而言，生產(chǎn)運(yùn)作仍然是其最基本的活動(dòng)，要實(shí)現(xiàn)敏捷制造的目標(biāo)，關(guān)鍵在于如何組織來(lái)自于動(dòng)態(tài)聯(lián)盟內(nèi)不同企業(yè)實(shí)體的各種資源，快速實(shí)現(xiàn)共同的市場(chǎng)機(jī)會(huì)。

動(dòng)態(tài)聯(lián)盟中的任務(wù)調(diào)度（企業(yè)間的調(diào)度）與傳統(tǒng)的車間調(diào)度不同。首先，動(dòng)態(tài)聯(lián)盟中的各成員企業(yè)都是利益自治體，相互之間不存在強(qiáng)制的集中式控制（包括盟主企業(yè)對(duì)成員企業(yè)）。其次，每個(gè)成員企業(yè)只負(fù)責(zé)整個(gè)產(chǎn)品的某個(gè)或某些部件的生產(chǎn)，成員之間對(duì)各自內(nèi)部的生產(chǎn)過(guò)程不了解。但由于不同產(chǎn)品部件的生產(chǎn)存在時(shí)序約束關(guān)系，使得成員企業(yè)不能不考慮其他成員企業(yè)的生產(chǎn)進(jìn)度對(duì)本企業(yè)生產(chǎn)過(guò)程的影響以及本企業(yè)的進(jìn)度對(duì)整個(gè)聯(lián)盟的影響等，這就要求成員企業(yè)之間的生產(chǎn)過(guò)程必須彼此協(xié)調(diào)，因此動(dòng)態(tài)聯(lián)盟企業(yè)的調(diào)度問(wèn)題對(duì)傳統(tǒng)的生產(chǎn)調(diào)度方法提出了新的挑戰(zhàn)。通常采用的解析法、神經(jīng)網(wǎng)絡(luò)、遺傳算法等純數(shù)學(xué)方法已不能解決動(dòng)態(tài)聯(lián)盟企業(yè)任務(wù)調(diào)度的問(wèn)題。

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

1 基本概念

定義1 時(shí)延庫(kù)所Petri網(wǎng)是一個(gè)六元組

TPPN= (,,,,,)

式中為TPPN的庫(kù)所集，表示某項(xiàng)任務(wù)，用布爾量表示，容量為1；為TPPN的變遷集，表示某項(xiàng)任務(wù)的開始或結(jié)束，和滿足；：，：，這里，和的權(quán)系數(shù)均為1；：→（為非負(fù)整數(shù)集），表示所有庫(kù)所的時(shí)延集，即完成中托肯所對(duì)應(yīng)的任務(wù)需要的時(shí)間；為系統(tǒng)的初始標(biāo)識(shí)。TPPN是一個(gè)出現(xiàn)網(wǎng)，即TPPN滿足：

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

定義2 變遷觸發(fā)條件

定義3 變遷觸發(fā)結(jié)果

如果在下可以被激活，當(dāng)前標(biāo)識(shí)相應(yīng)改變?yōu)楹罄^標(biāo)識(shí)，有并且，中的托肯經(jīng)過(guò)時(shí)延后可用，這一變遷可以表示為[。

2 基于時(shí)延庫(kù)所Petri網(wǎng)的任務(wù)調(diào)度建模

一項(xiàng)需敏捷制造完成的產(chǎn)品經(jīng)過(guò)分解成若干個(gè)零部件后，即形成了若干個(gè)加工任務(wù)，由若干個(gè)相應(yīng)的聯(lián)盟成員完成。動(dòng)態(tài)聯(lián)盟內(nèi)，在產(chǎn)品的完成過(guò)程中包含了以下幾種加工類型：一般加工、順序加工、并行加工、裝配。一般加工指一個(gè)零部件的完成對(duì)應(yīng)于一個(gè)加工任務(wù)，該加工任務(wù)由一個(gè)聯(lián)盟成員負(fù)責(zé)完成；順序加工指一個(gè)零部件的完成對(duì)應(yīng)于若干個(gè)加工任務(wù)，每一個(gè)加工任務(wù)由一個(gè)聯(lián)盟成員負(fù)責(zé)完成，并且在每一個(gè)加工任務(wù)間存在前后道工序關(guān)系；并行加工指若干個(gè)加工任務(wù)在某個(gè)時(shí)間段可以同時(shí)進(jìn)行；若干個(gè)零件經(jīng)由裝配環(huán)節(jié)形成部件，若干個(gè)部件經(jīng)由裝配環(huán)節(jié)形成更大的部件，直至最終形成整個(gè)產(chǎn)品。

一般加工的TPPN模型可用兩個(gè)變遷t和t以及一個(gè)庫(kù)所表示，如圖1所示。其中t表示加工任務(wù)的開始，t表示加工任務(wù)的結(jié)束，庫(kù)所中有一個(gè)托肯時(shí)表示加工任務(wù)正在進(jìn)行，的時(shí)延d表示從t發(fā)生（獲得托肯）開始，至少要經(jīng)過(guò)d個(gè)時(shí)間單位，t才能發(fā)生。

圖1 一般加工的TPPN模型

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

圖2 順序加工的TPPN模型

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

圖4 并行加工的TPPN模型

表示由兩個(gè)一般加工任務(wù)完成的零部件組成裝配的TPPN模型如圖5所示。存在裝配關(guān)系的兩個(gè)零部件1和2都完成后，裝配才能開始，用t表示，經(jīng)時(shí)延d，裝配結(jié)束于t。

圖5 裝配的TPPN模型

3 TPPN任務(wù)調(diào)度模型的分析與求解

3.1 模型的分析

（2）

（3）

（5）

（6）

3.2 模型的求解

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

（1）根據(jù)已知的、、值，計(jì)算各任務(wù)完工的期望平均時(shí)間和方差。

（2）畫出產(chǎn)品加工的TPPN模型。

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

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

4 實(shí) 例

針對(duì)市場(chǎng)機(jī)遇，若干家企業(yè)組成動(dòng)態(tài)聯(lián)盟生產(chǎn)某產(chǎn)品。產(chǎn)品分解后得到的加工任務(wù)，各任務(wù)之間的前后工序關(guān)系、各任務(wù)的、、值及經(jīng)計(jì)算得到的各任務(wù)的期望平均工期如表1所示。

由表2得產(chǎn)品加工的關(guān)鍵路徑為：A→B→H→F→G→L。

表1 產(chǎn)品的任務(wù)組成、任務(wù)的前后工序關(guān)系及工期

圖6 產(chǎn)品加工的TPPN模型

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

合理的調(diào)度方案有三種：

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

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

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

由此，畫出任務(wù)調(diào)度的Gantt圖，如圖8所示。

圖7 圖6的可達(dá)圖

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

圖8 任務(wù)調(diào)度的Gantt圖

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

本研究利用時(shí)延庫(kù)所Petri網(wǎng)對(duì)動(dòng)態(tài)聯(lián)盟的任務(wù)調(diào)度進(jìn)行了建模分析與求解，反映出了其中多任務(wù)間的并發(fā)、異步等動(dòng)態(tài)行為，該模型不僅可以及時(shí)了解產(chǎn)品各個(gè)組成部分的生產(chǎn)進(jìn)展，也可根據(jù)實(shí)際生產(chǎn)狀況動(dòng)態(tài)修改原計(jì)劃調(diào)度或進(jìn)行再調(diào)度，以適應(yīng)不斷變化的新環(huán)境，提升企業(yè)的敏捷性。

[1] 羅振璧, 汪勁松, 周兆英, 等. 靈捷制造——21世紀(jì)制造企業(yè)的戰(zhàn)略[J]. 機(jī)械工程學(xué)報(bào), 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. 敏捷企業(yè)(上)[J]. 張申生譯. 中國(guó)機(jī)械工程, 1996, 7(3): 22-27.

[4] 袁崇義. Petri網(wǎng)原理與應(yīng)用[M]. 北京: 電子工業(yè)出版社, 2005. 2-7.

[5] 吳哲輝. Petri網(wǎng)導(dǎo)論[M]. 北京: 機(jī)械工業(yè)出版社, 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

國(guó)家自然科學(xué)基金資助項(xiàng)目（50875049）；福建省重大科技資助項(xiàng)目（2007H2011）；福建省教育廳科技資助項(xiàng)目（JA09031）

黃 彬（1971-），男，江西南昌人，副教授，博士研究生，主要研究方向?yàn)槊艚葜圃臁⒅圃煜到y(tǒng)工程。