基于時間Petri網(wǎng)的區(qū)間作業(yè)車間調(diào)度問題建模與分析

潘 理,楊 勃(湖南理工學(xué)院 信息與通信工程學(xué)院,湖南 岳陽 414006)

?

基于時間Petri網(wǎng)的區(qū)間作業(yè)車間調(diào)度問題建模與分析

潘 理,楊 勃
(湖南理工學(xué)院 信息與通信工程學(xué)院,湖南 岳陽 414006)

摘 要:區(qū)間作業(yè)車間調(diào)度問題近年來已成為生產(chǎn)調(diào)度研究的熱點,現(xiàn)有研究工作主要集中于問題描述和優(yōu)化求解方面,在理論模型、動態(tài)性質(zhì)等方面還缺乏實質(zhì)性成果.使用時間Petri網(wǎng)模型建模區(qū)間作業(yè)車間調(diào)度問題,并運用狀態(tài)類可達性分析方法,分析模型所有可行調(diào)度,進而求解具有最小下界和最小上界的優(yōu)化調(diào)度,為區(qū)間作業(yè)車間調(diào)度問題的建模與分析提供有益參考.

關(guān)鍵詞:區(qū)間作業(yè)車間調(diào)度; 時間Petri網(wǎng); 建模與分析

引言

在實際生產(chǎn)過程中,由于系統(tǒng)的實時特性和外界不確定因素的影響,作業(yè)操作的持續(xù)時間并不能準(zhǔn)確地固定下來,但是作業(yè)開始和結(jié)束的時間范圍多數(shù)可以界定[1].近年來,國內(nèi)外研究人員開始探討基于區(qū)間不確定性的作業(yè)車間調(diào)度問題[2～4],并逐漸成為柔性制造系統(tǒng)調(diào)度問題研究的關(guān)注點.

區(qū)間使用上界和下界刻畫時間的不確定性,不僅描述簡單,而且容易從實際生產(chǎn)中獲取,更便于決策者理解.Lei[1]提出區(qū)間作業(yè)車間調(diào)度問題,并以最小總延遲為優(yōu)化目標(biāo),使用遺傳算法求解該問題的優(yōu)化解.Sotskov[2]等使用區(qū)間描述作業(yè)加工時間,以最小化加權(quán)完工時間為目標(biāo),求解單臺機器的作業(yè)調(diào)度問題.Lu[4]等使用區(qū)間描述作業(yè)加工時間和順序相關(guān)調(diào)整時間,以最小化魯棒調(diào)度序列時間與最大完工時間之差為目標(biāo),利用局部搜索技術(shù)求解單臺機器作業(yè)調(diào)度問題.

近三十年來,Petri網(wǎng)被廣泛應(yīng)用于作業(yè)車間調(diào)度問題的建模和優(yōu)化,涌現(xiàn)出許多高水平成果[5～8].但是這些建模方法均采用時延Petri網(wǎng)模型,處理時間約束為確定值的作業(yè)車間調(diào)度問題,不能有效處理不確定時間約束的作業(yè)車間調(diào)度問題.因此,研究區(qū)間作業(yè)車間調(diào)度問題的時間Petri網(wǎng)建模與分析方法,對于實際作業(yè)車間調(diào)度生產(chǎn)具有重要意義.

區(qū)間作業(yè)車間調(diào)度問題是新近提出的作業(yè)車間調(diào)度問題,現(xiàn)有工作主要集中于問題描述和優(yōu)化求解方面,在理論模型、動態(tài)性質(zhì)等方面還沒有實質(zhì)性成果,也沒有公開發(fā)表的文獻探討該問題的Petri網(wǎng)建模和分析方法.時間Petri網(wǎng)是Petri網(wǎng)的時間區(qū)間擴展形式[9],很自然可用于區(qū)間作業(yè)車間調(diào)度問題的描述.本文嘗試使用時間Petri網(wǎng)作為形式化模型,探討區(qū)間作業(yè)車間調(diào)度問題的建模與分析方法,為區(qū)間作業(yè)車間調(diào)度問題的研究提供一種有益的探索.

1　時間Petri網(wǎng)

1.1 理論模型

定義1[9]時間Petri網(wǎng)TPN是一個6元組(P,T,Pre ,Post ,M0,SI),其中

(1)P是庫所集;

(2)T是變遷集;

(3)Pre: P T →N是前置關(guān)聯(lián)矩陣;

(4)Post: P T →N是后置關(guān)聯(lián)矩陣;

(5)M0: P →N是初始標(biāo)識;

標(biāo)識M是一個|P |維向量,M(p)表示庫所p的令牌數(shù).

用En(M)表示M的使能變遷集,用Newly(M ,t)表示在M實施t后新使能的變遷集.

1.2 狀態(tài)類方法

狀態(tài)類方法是Petri網(wǎng)可達性分析最常用的方法之一.

(1)Mi是標(biāo)識;

條件(1)保證t使能; 條件(2)保證t不是過期變遷; 條件(3)保證t在與其不沖突的變遷之前實施.用 Fr(Ck)表示Ck的可實施變遷集.

規(guī)則(1)計算新標(biāo)識Mk 1; 規(guī)則(2.i)計算tj相對于當(dāng)前狀態(tài)類的實施間隔; 規(guī)則(2.ii)計算tj和tj之間的相對實施間隔.

2　區(qū)間作業(yè)車間調(diào)度問題建模與分析

2.1 時間Petri網(wǎng)調(diào)度模型

作業(yè)車間調(diào)度問題描述為: 在M個機器上加工N個工件,每個工件Ji由nj個工序組成,工件的每道工序可由多臺機器加工.用Oijk表示第i個工件的第j道工序在機器Mk上加工.區(qū)間作業(yè)車間調(diào)度問題采用間隔描述加工時間[1].

考慮一個作業(yè)車間調(diào)度問題,它由3臺機器組成,可處理3種作業(yè),每種作業(yè)需3道工序完成.表1描述了每種作業(yè)的資源需求.

根據(jù)上述需求描述,建立該問題的時間Petri網(wǎng)模型,如圖1所示.其庫所和變遷說明見表2.

表1 作業(yè)的資源需求

圖1 作業(yè)車間調(diào)度問題的時間Petri網(wǎng)模型

表2 庫所變遷描述

2.2 時間Petri網(wǎng)調(diào)度分析

作業(yè)車間調(diào)度就是在滿足一定約束條件情況下,在M臺機器上安排N個工件的加工任務(wù),并最優(yōu)化某些性能指標(biāo)(例如,最小完工時間makespan).

利用第1.2節(jié)提出的狀態(tài)類方法(定義4和定義5),可以構(gòu)造時間Petri網(wǎng)模型的狀態(tài)類類樹,獲得所有可行調(diào)度.根據(jù)上述狀態(tài)類方法,研制了基于Matlab平臺的時間Petri網(wǎng)建模和分析工具,工具網(wǎng)址為: http://61.187.92.238:8204/html/kexueyanjiu/2013/0614/1053.html.

運用工具對作業(yè)車間調(diào)度問題的Petri網(wǎng)模型進行狀態(tài)類分析,共產(chǎn)生狀態(tài)類244104個,得到可行調(diào)度118657條.計算獲得最優(yōu)下界調(diào)度為t12t7t2t13t4t8t15t5t10,時間間隔[8,13],如圖2所示.計算獲得最優(yōu)上界調(diào)度為t12t7t2t4t8t13t5t15t10,時間間隔[9,12],如圖3所示.

圖2 最優(yōu)下界調(diào)度

圖3 最優(yōu)上界調(diào)度

3　結(jié)論

作業(yè)車間調(diào)度是企業(yè)提高生產(chǎn)效率、快速響應(yīng)市場需求的有效手段.針對新近出現(xiàn)的區(qū)間作業(yè)車間調(diào)度問題,提出基于時間Petri網(wǎng)的形式模型和基于狀態(tài)類的可達性分析方法,實現(xiàn)了基于Matlab的建模和分析,并運用工具分析了區(qū)間作業(yè)車間調(diào)度問題的優(yōu)化調(diào)度,為區(qū)間作業(yè)車間調(diào)度問題的建模和分析提供了一條新的探索途徑.

參考文獻

[1] Lei D M.Interval job shop scheduling problems[J].The International Journal of Advanced Manufacturing Technology,2012,60(1-4): 291～301

[2] Sotskov Y N,Lai T C,Werner F.Measures of problem uncertainty for scheduling with interval processing times[J].OR spectrum,2013,35(3): 659～689

[3] Lei D M,Guo X P.An effective neighborhood search for scheduling in dual-resource constrained interval job shop with environmental objective[J].International Journal of Production Economics 2015,159: 296～303

[4] Lu C C,Lin S W,Ying K C.Minimizing worst-case regret of makespan on a single machine with uncertain processing and setup times[J].Applied Soft Computing,2014,23: 144～151

[5] Lee D Y,DiCesare F.Scheduling flexible manufacturing systems using Petri nets and heuristic search[J].IEEE Trans.Robotics and Automation,1994,10(2): 123～132

[6] Li C,Wu W,Feng Y,et al.Scheduling FMS problems with heuristic search function and transition-timed Petri nets[J].Journal of Intelligent Manufacturing,Springer,2015,26: 933～944

[7] Ahmad F,Khan S A.Module-based architecture for a periodic job-shop scheduling problem[J].Computers & Mathematics with Applications,2012,64(1): 1～10

[8] Huang H,Du H,Ahmad F.Job Shop Scheduling with Petri Nets[J].Handbook of Combinatorial Optimization,Springer,2013: 1667～1711

[9] 潘 理,丁志軍,郭觀七.混合語義時間Petri網(wǎng)模型[J].軟件學(xué)報,2011,22(6): 1199～1209

Modelling and Analysis of Interval Job Shop Scheduling Problems Based on Time Petri Nets

PAN Li,YANG Bo
(College of Information and Communication Engineering,Hunan Institute of Science and Technology,Yueyang 414006,China)

Abstract:Interval job-shop scheduling problem is a new research hotspot in work-shop scheduling.The existing research work focused on problem description and optimization,but substantial results is lacking on theoretical model and dynamic properties.We present a time Petri net to model interval job-shop scheduling problems,and uses a reachability method based on state classes to analyze all feasible schedules of this model,and then solves optimal schedules with least upper bound and least lower bound.The proposed method can provide a helpful reference for modelling and analyzing interval job-shop scheduling problems.

Key words:interval job shop scheduling,time Petri nets,modelling and analysis

通訊作者:楊 勃(1974?),男,湖南岳陽人,博士,湖南理工學(xué)院信息與通信工程學(xué)院副教授.主要研究方向: 模式識別

作者簡介:潘 理(1975?),男,湖南平江人,博士,湖南理工學(xué)院信息與通信工程學(xué)院副教授.主要研究方向: 系統(tǒng)建模與優(yōu)化

基金項目:國家自然科學(xué)基金項目(61473118); 湖南省教育廳科學(xué)研究重點項目(15A079); 湖南省科技計劃項目(2014GK3026)

收稿日期:2015-11-25

中圖分類號:TP301

文獻標(biāo)識碼:A

文章編號:1672-5298(2016)01-0033-04