王曉華，王瑞卿，洪 良，張 蕾，張宏偉

(西安工程大學(xué) 電子信息學(xué)院，陜西 西安710048)

隨著服裝市場消費檔次的多樣化發(fā)展，服裝的生產(chǎn)類型從批量大、品種少和周期長逐步過渡為批量小、品種多和周期短的類型，因而要求企業(yè)具有快速反應(yīng)的生產(chǎn)能力[1]。從20世紀(jì)70年代發(fā)展起來的服裝吊掛系統(tǒng)可以快速地更換產(chǎn)品類型，但是服裝生產(chǎn)柔性度不高，同時進(jìn)行多品種加工生產(chǎn)時容易出現(xiàn)設(shè)備競爭、工作站配置和流水線平衡等問題[2]。學(xué)者們針對服裝吊掛系統(tǒng)的優(yōu)化問題展開了研究[3-5]。文獻(xiàn)[6]應(yīng)用蟻群算法重新編排流水線工序，獲得了制品傳遞距離最小化下的系統(tǒng)優(yōu)化結(jié)果，但缺少對設(shè)備競爭工序控制策略的考察。文獻(xiàn)[7]結(jié)合標(biāo)準(zhǔn)資料法和學(xué)習(xí)曲線法制定了工時定額法，一定程度上滿足了服裝生產(chǎn)柔性度的要求，但難以適用于多品種服裝生產(chǎn)工序的優(yōu)化。文獻(xiàn)[8-9]應(yīng)用遺傳算法對整個生產(chǎn)線上的個別生產(chǎn)工序進(jìn)行了優(yōu)化，但未考慮全部生產(chǎn)工序及各項資源，特別是多任務(wù)生產(chǎn)情況，存在一定的局限性。Petri網(wǎng)在柔性制造系統(tǒng)優(yōu)化調(diào)度方面[10-12]具有一定的優(yōu)越性，使其在機械、化工[13-14]等生產(chǎn)領(lǐng)域及數(shù)控系統(tǒng)的在線實時故障診斷[15]中得到了廣泛應(yīng)用。文獻(xiàn)[16-17]建立了制造系統(tǒng)的時間Petri網(wǎng)模型，給出了柔性生產(chǎn)過程的優(yōu)化調(diào)度方法。文獻(xiàn)[18]應(yīng)用Petri網(wǎng)建模和遺傳算法優(yōu)化了模具車間的作業(yè)調(diào)度，但未給出具體的工序排列方法。文獻(xiàn)[19]將Petri網(wǎng)引入到服裝生產(chǎn)線中，但未涉及具體的建模方法和工序調(diào)度策略算法。

本文采用賦時庫所Petri網(wǎng)建模方法，解決服裝吊掛系統(tǒng)多任務(wù)生產(chǎn)中設(shè)備資源競爭的工序優(yōu)化問題?？疾於嗳蝿?wù)生產(chǎn)線的約束條件和優(yōu)化目標(biāo)，對多任務(wù)生產(chǎn)進(jìn)行賦時庫所Petri網(wǎng)建模，應(yīng)用工序最優(yōu)調(diào)度策略算法，通過模型演化推導(dǎo)出考慮設(shè)備競爭的服裝加工工序?qū)嵤╉樞?，獲得多任務(wù)條件下時間最短的生產(chǎn)實施方案，提高服裝吊掛系統(tǒng)的柔性生產(chǎn)程度。

1 基本概念

基本的標(biāo)識Petri網(wǎng)(PN)可表示為一個5元組N=(P，T，F(xiàn)，W，M0)，其中，P為有限非空的庫所集合，庫所p∈P用圓圈表示，代表系統(tǒng)的狀態(tài);T為有限非空的變遷集合，變遷t∈T用方框表示，代表系統(tǒng)中的事件;F?(P×T)∪(T×P)為流關(guān)系或有向弧的集合;W: (P×T)∪(T×P)→N+為有向弧的權(quán)函數(shù);M0:P→N+為一個列向量，表示系統(tǒng)初始狀態(tài)下所有庫所中的托肯數(shù)，稱為N的初始標(biāo)識。·t表示t的所有輸入庫所的集合。PN的運行規(guī)則為：變遷t∈T在標(biāo)識M下是使能的，當(dāng)且僅當(dāng)?p∈·t，M(p)≥W(p，t)時，使能的變遷t發(fā)射產(chǎn)生新標(biāo)識M′(p)，表示系統(tǒng)躍遷狀態(tài)，M′(p)=M(p)-W(p，t)+W(t，p)。當(dāng)?p∈P，變遷t發(fā)射后，根據(jù)該變遷的W(p，t)和W(t，p)，系統(tǒng)將從輸入庫所中移出與變遷的輸入有向弧權(quán)值相應(yīng)數(shù)量的托肯到輸出庫所。賦時庫所Petri網(wǎng)(Timed Place Petri Net，TPPN)TPPN=(P，T，F(xiàn)，W，M0，D)，其中，P，T，F(xiàn)，W，M0與基本PN的定義相同。D={d1，d2，...，dn}為庫所的時延集合，其中，di為pi的時延。TPPN的變遷發(fā)射與基本PN的規(guī)則相同，改變輸入與輸出庫所中的托肯數(shù)，但放入輸出庫所中的托肯必須等待一定時間才可以使用，這段時間稱為該庫所的時延。

2 服裝吊掛系統(tǒng)的TPPN模型建立

假定一個服裝吊掛系統(tǒng)需要同時進(jìn)行n種服裝的生產(chǎn)，其生產(chǎn)任務(wù)分別表示為J1，J2，...，Jn。各任務(wù)包含的工序數(shù)分別為X1，X2，...，Xn; 加工時要用到燙臺、包縫機、雙針平縫機、筒形卷邊機等Y種設(shè)備，每種設(shè)備各一臺; 需要Z種裁片S1，S2，...，SZ。多任務(wù)生產(chǎn)時，由于并發(fā)過程的存在和設(shè)備資源競爭等問題，工序的執(zhí)行順序不同，完成n項任務(wù)的時間也不相同。結(jié)合TPPN的基本概念與服裝加工過程的特點，需建立服裝吊掛系統(tǒng)多任務(wù)生產(chǎn)的TPPN模型。

以包含2項生產(chǎn)任務(wù)的J1和J2服裝吊掛系統(tǒng)為例[19-20]，建立系統(tǒng)的TPPN模型。任務(wù)J1有13項工序，在模型中表示為13個生產(chǎn)階段J1，1，J1，2，...，J1，13；任務(wù)J2有15項工序，在模型中表示為15個生產(chǎn)階段J2，1，J2，2，...，J2，15。共需要4臺設(shè)備即燙臺、釘扣機、包縫機和平縫機。加工一件衣服需要12種裁片，前衣片(2片)、后衣片(1片)、門里襟(2片)、胸袋(1片)、過肩(2片)、袖片(2片)、袖頭(4片)、衩里襟(4片)、衩門襟(2片)、領(lǐng)座(2片)、翻領(lǐng)(2片)、口袋(2片)，分別表示為S1，S2，...，S12。根據(jù)2種服裝各自的工序排列順序，將裁片送往相應(yīng)的工作站，結(jié)合人工操作與所需的加工設(shè)備，完成2種服裝的生產(chǎn)。2項生產(chǎn)任務(wù)中服裝吊掛系統(tǒng)任務(wù)(加工時間、所需設(shè)備、裁片類型、數(shù)量)如表1所示。

表1 服裝吊掛系統(tǒng)任務(wù)表Table 1 Task table of garment hanging system

通過共享資源庫所連接的2個子系統(tǒng)模型NJ1和NJ2可得服裝吊掛系統(tǒng)的TPPN模型，如圖1所示。

圖1 由共享資源庫所連接任務(wù)J1和J2的Petri網(wǎng)模型獲得的服裝吊掛系統(tǒng)TPPN模型Fig.1 The TPPN model of garment hanging system obtained from the Petri net model of J1 and J2 connected with shared resource places

3 服裝吊掛系統(tǒng)最優(yōu)調(diào)度策略算法

應(yīng)用所建立的服裝吊掛系統(tǒng)的TPPN模型，利用有限的資源來找出完成多任務(wù)用時最少的工序排列方法，以實現(xiàn)最優(yōu)加工。最優(yōu)調(diào)度策略算法為設(shè)置n項任務(wù)的優(yōu)先級，得到多種實施方案。每種方案中最后完工任務(wù)Ji的用時為dr，找出所有實施方案中最小dr值對應(yīng)的變遷發(fā)射序列，得出工序最優(yōu)調(diào)度策略。多任務(wù)生產(chǎn)線的目標(biāo)函數(shù)為

(1)

多任務(wù)生產(chǎn)線的約束條件如下：

(1)Petri網(wǎng)的變遷使能和發(fā)射規(guī)則。當(dāng)且僅當(dāng)?p∈·t，M(p)≥W(p，t)，使能的變遷t在滿足服裝加工規(guī)則后發(fā)射產(chǎn)生新的狀態(tài)標(biāo)識M′(p)，M′(p)=M(p)-W(p，t)+W(t，p)。

(2)服裝加工規(guī)則。任務(wù)的工序按一定順序排列，即具體的某項任務(wù)Ji中變遷t的發(fā)射順序是固定的。

(3)設(shè)備資源競爭。設(shè)任務(wù)Ji包含ki臺設(shè)備，n項任務(wù)J1，J2，...，Jn所需設(shè)備數(shù)量k為(k1，k2，...，kn)，其中每類設(shè)備各一臺。當(dāng)不同任務(wù)的工序競爭同一臺設(shè)備時，根據(jù)優(yōu)先級或使能時刻確定其使用順序。

根據(jù)服裝吊掛系統(tǒng)多任務(wù)生產(chǎn)線的目標(biāo)函數(shù)和約束條件，得出系統(tǒng)最優(yōu)調(diào)度策略算法，其中，算法的輸入、輸出及實施步驟如下所述。

輸入：n項任務(wù)的服裝吊掛系統(tǒng)TPPN。

輸出：完成n項任務(wù)最短時間d，變遷最優(yōu)發(fā)射序列。

Step2：由初始標(biāo)識M0開始，當(dāng)變遷t的前集庫所中的托肯滿足M(p)≥W(p，t)時，變遷t使能，找出所有使能的變遷。

Step3：搜索使能變遷，執(zhí)行Step 3.1或3.2。

Step4：跳轉(zhuǎn)至Step3，直至所有變遷都已發(fā)射。

Step6：跳轉(zhuǎn)至Step 1，直至n!+n種實施方案都已完成。

在服裝吊掛系統(tǒng)多任務(wù)生產(chǎn)工序調(diào)度問題中，考慮Petri網(wǎng)變遷的使能和發(fā)射規(guī)則、服裝加工規(guī)則和設(shè)備競爭等約束條件，將完工時間最短設(shè)為調(diào)度目標(biāo)，找出最短時間條件下變遷的發(fā)射時間和序列。映射變遷到服裝吊掛系統(tǒng)中與工序關(guān)聯(lián)的事件，得出n項任務(wù)的工序排列順序和時刻，即最優(yōu)調(diào)度策略。賦時庫所Petri網(wǎng)TPPN模型工序最優(yōu)調(diào)度策略算法流程如圖2所示。

圖2 賦時庫所Petri網(wǎng)TPPN模型工序最優(yōu)調(diào)度策略算法流程Fig.2 Flow chart of optimal scheduling policy algorithm of process based on TPPN model

4 試驗與分析

方案1的最后完工任務(wù)為J2，則

方案2的最后完工任務(wù)為J1，則

(13+6)+(36+81)+(25+0)+(32+0)+(22+

0)+(30+0)+(33+0)+(105+0)+(47+0)+

(94+0)+(127+0)=1 097 s

方案3的最后完工任務(wù)為J2，則

(13+0)+(36+12)+(10+0)+(7+0)+(25+

0)+(32+0)+(22+0)+(30+8)+(33+3)+

(105+72)+(47+0)+(94+47)+(127+33)=902 s

方案4的最后完工任務(wù)為J1，則

(13+0)+(36+23)+(25+6)+(32+7)+(22+

0)+(30+8)+(33+3)+(105+72)+(47+0)+

(94+47)+(127+33)=926 s

表2 加工時間最短條件下變遷發(fā)射序列Table 2 The transition firing sequence under the minimum processing time

表3 基于Petri網(wǎng)的服裝柔性生產(chǎn)工序最優(yōu)調(diào)度策略Table 3 Optimal scheduling policy of garment flexible production process based on Petri net

為驗證基于Petri網(wǎng)的服裝柔性生產(chǎn)工序優(yōu)化方法的實用性，本文整理了其他研究者獲得的服裝生產(chǎn)優(yōu)化的信息[20-21]，多品種服裝的多任務(wù)加工數(shù)據(jù)如表4所示。

表4 多品種服裝的多任務(wù)加工相關(guān)數(shù)據(jù)Table 4 Multitask processing-related data of various clothing

將n值依次設(shè)為2，3，4，5，6，輸入工序、時間和設(shè)備等數(shù)據(jù)，使用最優(yōu)調(diào)度策略算法進(jìn)行工序優(yōu)化，計算得到的完工時間分別為902、1 638、1 167、1 543、1 268 s，其與由原文數(shù)據(jù)計算出的生產(chǎn)時間的對比如表4所示。

由表4可以看出，本文算法適合不同種類和多種款式服裝的工序優(yōu)化，利用最優(yōu)加工策略算法對各工序的加工時刻進(jìn)行合理分配，使得總體時間減少，提高了服裝吊掛系統(tǒng)對于小批量和多品種的服裝生產(chǎn)效率。

5 結(jié) 語

本文將賦時Petri網(wǎng)理論引入服裝吊掛系統(tǒng)的生產(chǎn)工序優(yōu)化研究中，結(jié)合Petri網(wǎng)的概念、服裝在生產(chǎn)線上的加工特性和工序優(yōu)化的規(guī)則，編寫出最優(yōu)調(diào)度策略算法。試驗證明，應(yīng)用基于Petri網(wǎng)的最優(yōu)調(diào)度策略方法可縮短多種服裝同時加工的時間，提高系統(tǒng)的運行效率。但本研究只考慮每種設(shè)備僅有一臺的情況，根據(jù)各臺設(shè)備在完成一次任務(wù)中的使用頻率，將對于設(shè)備種類和數(shù)量的優(yōu)化做為下一步研究的目標(biāo)。

參 考 文 獻(xiàn)

[1] 蔡文靜，金京. 服裝吊掛傳輸系統(tǒng)發(fā)展概況及應(yīng)用研究[J]. 輕工科技，2015(8): 115-117.

[2] 吳鑫，俞建定，趙鵬飛，等. 基于以太網(wǎng)和RS485的服裝吊掛生產(chǎn)線控制系統(tǒng)[J].機電工程，2013，30(10): 1280-1285.

[3] MORK P Y，CHEUNG T Y. Intelligent production planning for complex garment manufacturing [J]. Journal of Intelligent Manufacturing，2013，24(1): 133-145.

[4] CUI H R，YAN Y N. The optimization design of uniform’s hanging production line [J]. International Journal of Clothing Science and Technology，2015，27(3): 370-389.

[5] ZHANG R，CHANG P C，SONG S. A multi-objective artificial bee colony algorithm for parallel batch-processing machine scheduling in fabric dyeing processes [J]. Knowledge-Based Systems，2017，116(1): 114-129.

[6] 于昕辰，曾培峰，趙冉，等. 基于蟻群算法的服裝生產(chǎn)流水線作業(yè)平衡[J]. 東華大學(xué)學(xué)報(自然科學(xué)版)，2014，40(4): 456-460.

[7] 葉寧，閻玉秀. 多品種小批量服裝生產(chǎn)的工時定額制定方法[J]. 紡織學(xué)報，2012，33(6): 101-106.

[8] WANG J A，PAN R，WANG H. An automatic scheduling method for weaving enterprise based on genetic algorithm [J]. Journal of the Textile Institute，2015，106(12): 1377-1387.

[9] 王東云，劉慧琴. 基于遺傳算法的鋪布與裁剪過程的優(yōu)化調(diào)度[J]. 紡織學(xué)報，2005，26(5): 111-114.

[10] HONG L，CHAO D Y. Enumeration of reachable states for arbitrary marked graphs [J]. IET Control Theory & Applications，2012，6(10): 1536-1543.

[11] HONG L，HOU Y F，JING J F，et al. Deadlock prevention policy with behavioral optimality or suboptimality achieved by the redundancy identification of constraints and the rearrangement of monitors[J]. Discrete Dynamics in Nature and Society，2015，2015(1): 1-15.

[12] HONG L，WANG A R，JING J F，et al. Combinatorics and resource circuit-based enumeration of reachable states for S3PR [J]. Advances in Mechanical Engineering，2015，8(6): 1-11.

[13] 蘇國軍，汪晉，田立國. 基于Petri網(wǎng)模型的柔性制造系統(tǒng)優(yōu)化調(diào)度[J]. 系統(tǒng)工程理論與實踐，2014，34(10): 2717-2721.

[14] 周家忠，羅繼亮，詹瑜坤. 間歇式化工系統(tǒng)的Petri網(wǎng)優(yōu)化調(diào)度與控制方法[J]. 控制理論與應(yīng)用，2016，33(6): 809-815.

[15] 田仁鐵，楊建國. 一種基于Petri網(wǎng)模型的數(shù)控系統(tǒng)的分析與在線實時故障診斷方法[J]. 東華大學(xué)學(xué)報(自然科學(xué)版)，2015，41(4): 503-508.

[16] JUNG C，KIM H，LEE T. A branch and band algorithm for cyclic scheduling of Timed Petri nets[J]. IEEE Transitions on Automation Science and Engineering，2015，12(1): 309-323.

[17] PANG C，LE C V. Optimization of total energy consumption in flexible manufacturing system using weighted P-Timed Petri nets and dynamic programming [J]. IEEE Transition on Automation Science and Engineering，2013，11(4): 1083-1096.

[18] YAO W L，PAN Y M. A Petri nets and genetic algorithm based optimal scheduling for Job Shop manufacturing system [C] //ICSSE-IEEE International Conference on System Science and Engineering. 2013: 99-104.

[19] 張玉斌，陳雁. Petri網(wǎng)在服裝生產(chǎn)平衡中的應(yīng)用[J]. 輕紡工業(yè)與技術(shù)，2009，38(1): 38-40.

[20] 陳海湄. 服裝縫制流水線的作業(yè)編排與優(yōu)化研究[D]. 蘇州: 蘇州大學(xué)紡織與服裝工程學(xué)院，2005.

[21] 劉謠. 基于ProModel的仿真系統(tǒng)的服裝混合流水線平衡優(yōu)化[D]. 上海: 東華大學(xué)紡織學(xué)院，2015.