Research on Production Process Control Method Combined Stochastic Process Algebra and Stochastic Pet

Research on Production Process Control Method Combined StochasticProcess Algebra and Stochastic Petri NetsLIU Chang SHI Haibo( Shenyang Inst. of Automation , Chinese Academy of Sciences , Shenyang 110016 , China E mail ichangl@sia. cn )Abstract : A hierarchical closed loop procduction control scheme integrating scheduling , control and per. formance eraluation isdiscussed. Firstly the production process is dirvided into two main hierarchies : the lonrcer lerel is the physical operation level andthe upper one is the management level. Scondly , the schedule tem, plate for the management level and the activity template for theplhysical operation level are constructed separately , the tasks in the schelule hare the ability to make partial decisions , and the per.formance parameters are introduced into activity template. Thirdly , the two levels use different model representations : stochasticprocess algebra for the management level whose output is the control commands and stochastic Petri net for the physical operation lev-el which is the erecution of the control commands. Then , the integration of the two levels is the control commands mapping into thelorwer physical operat ions and the responses feeding back to the upper decision -making that are defined by some transition functions.Under the proposed scheme , the production process control of a flexible assembly is exemplified. It is concluded that the process con-trol model has partial ability to make decision on-line for uncertain and dymamic environments and facilitates reasoning about the be-haviors of the process control , and performance eraluation can be done omline for real-ime schecluling to ensure the global optimiza-tionKey words: production process control ; stochastic process algebra ; stochastic Petri net ; hierarchical control1 IntroductionThe objective of production process control is to make manufacturing system operate in optimal mode , andthe functions embody organizing , scheduling , coordinating and controlling the production processes. Productionprocess exhibits as the material flow , whereas the material flow is controlled by a set of production control com-mands( information ), which is the result of a set of decision-making activities. The basis of decision- making isthe information of the manufacturing system , including the status of the manufacturing resources and the resultsof performance evaluation. Scheduling , coordination , control and performance evaluation working on each otherare a whole and uniformly called' control' . At present , most manufacturing control architecture was hierarchi-cal. However , practical experience has indicated that many hierarchical systems tend to have problems with re-activity to disturbances , but have advantage with global optimization. In order to achieve fast response to unex-pected events in a stochastic manufacturing system , the control mechanism must also have the capability to mon-itor and evaluate the real-time performance online. Assessing the performance measures of a stochastic manufac-turing system at the end of a production period provides only limited insight since the next production can becompletely different , and improvement of these measures becomes impossible.Due to the graphical representation and the mathematical method , Petri nets have been used extensively tomodel , analyze and control of manufacturing systems. Stochastic manufacturing systems have more uncertaintyevents and stochastic behaviors , such as machine failures , operator absences , material unavailability , surges indemand , and variations of processing time. Stochastic Petri nets( SPN ) are effective tools to describe such un-certain events and stochastic behaviors. Process algebras ( PA ) have a much greater descriptive power than au-tomata and Petri nets 1. It has been noted that applies process algebra to the modeling and analysis of manufac-turing systems. Nevertheless , compared with Petri net , in process algebra based formalisms , causality is not ex-hibited and there is no clear notion of state , and the concept of state and model coincide. From a modeling pointof view , process algebra is focused on actions. It is concluded that the two formalisms have distinctive strengthsand weaknesses , accordingly the combination of the two formalisms for the modeling and performance evaluationof manufacturing systems is worthy of being discussed.中国煤化工Using recursive processes in a top -down way ,a hierarchicMHC N M H Give control design tech-nique for a flexible manufacturing system is developed , which preserves system modularity and integrity1. Hi-erarchical control structure model based on Petri nets is discussed271. A modeling framework for general routingand resource booking problems is presented , and the modeling language combined Petri nets and process algebrais provided8]._ .428In this paper，the hierarchical production process control structure is adopted which decomposes the compli-cated task into more detailed subtasks step by step. Under the hierarchical scheme , the scheduling and controlare integrated. And that , the model has the ability of online performance evaluation ,and the result of the per-formance evaluation being the feedback information which is the basis of the upper level' s decision- making. Furthermore，the production process control structure for assembly is still based on the assembly process informa-tion ,which consists of not only sequential but also parallel and competitive relationship. The process controlmodel based on stochastic process algebra( SPA ) represents as a set of concurrent , communicating computationalprocesses. The process execution model is partitioned into sub-systems according to the equipment types , meta-models are constructed for each sub- systems based on SPN. And then , the top- down method is used to synthe-size the system model. The model can be applied to both the simulation analysis and real-time control.Some advantages of the model are demonstrated by taking the flexible assembly as an example. The processcontrol model has partial ability to make decision on- line for uncertain and dynamic environments , and facilitatesreasoning about the behaviors of the process control model. The schedule and information flow can shrink or ex-pand over time. Especially , thanks to performance parameters introduced into activity , performance can evaluat-ed online for real-time scheduling.2 Production Process and Control SchemeIn this paper , the production process is the whole procedure from the shop floor planning to the finishedgoods shipping , which consists of a physical operation level and a management level. One task , for the manage-ment level，is a set of production commands including transporting command，storing command，machiningcommand , assembling command and testing command , while for the physical operation level , is the execution ofa set of correlative physical operations to achieve a special production objective. The relationship is exhibited inFig.1. The management activity transforms input into output which is being the control command made knownto the physical activity by information system , while the result of the physical activity feeding back to the man-agement activity as the input. Thus ，the control flow top-down and the response flow bottom-up are formed.The latter section will discuss the schedule template for the management level and the activity template for thephysical operation level.2.1 Schedule TemplateA schedule is a partial order relation defined on a set of tasks. let us denote a schedule by a partial order re-lation set :Definition 2.1 Schedule=( TS,< ), where TS=( T1 , T2...，Tn ), T;( i=1 ,2.... ,n )are n tasks ,“<" is a partial order relation.InputPersonnel .ManagementInformationactivity 1activity 2systemOutput(contolfeedback )Instruction,FoedbackPhysicaloperation 1operation 2PartEquipment 1Materiell Equipment 2Material2Operator 1Operator 2Fig.1 Hierarchical model of production processesA schedule defines a processing order among tasks of the中国煤化工s a sequence of elemen-tal events that must occur in a given order , thereby ,a task is|YHC N MH Gfined on a set of opera-tions.Definition2.2 T=( OS ,< ), where Os=(O1 ,O2 ... ,Om),O,( j=1 ,2 ... ,m )are m operations ,“< <”is a partial order relation.Once the manufacturing system running ,it is dynamic and stochastic , and there are many complicated rela-.-429一tions，including sequential/ parallel relation ，resource - sharing and conflicting ，performance/ objective correla-tive. Thus , the scheduling function should react to the interior and the outer exceptions when system running ,and handle in time. An extension to the definition 2.1 is given below , which has the capability to schedule on-lineDefinition2.3 Task=(S ,R ,E ),where S isa sensory process ,E an execution process ,and R a rea-soning process describing the relationship between! S and E.The control mechanism proposed in this paper is based on the optimization of desired performance measures.Therefore , the scheme consists of monitor and performance evaluation. Sensory process monitors the states ofthe system resources and the results of performance evaluation. State abnormity and performance deviation as theexception of the production process trigger the reasoning process to adjust the abnormal task. When the deviationis too large to correct , the abnormity will be handed over to the upper module to deal with. Definition 2.3 de-composes the decision- making capability partially into each task which has some ability to reason , coordinateand control the production process according to the resource states and the performance results.2.2 Physical Operation TemplateIn order to associate the resources with the production processes , the physical operation template is definedthat involves outer template and interior template. The outer template describes the input interface , activity typeand output interface ,of which the inside action is invisible to the management level and the communicating with .the environment through the input/ output interface. The interior template defines the detailed activities infor-mation for the physical operation level , which include action type , the correlative resources , temporal parame-ter , cost and quality specification.Definition 2.4 outer template : Process = ( Request , Action , Response );Interior template :Action = ( Name , Type , Resource ( Equipment[ Operator I ,Material ]I ,Time ICost I Quality ]) . whereRequest denotes command，such as machining command , transporting command and storing command.Response denotes the feedback , which is the result of the execution.Name denotes the identifier of the action.Type defines the category of the action. The equipment is usually classified into the machining , the trans-porting , the storing , and the testing. The type of the physical activity is determined by the type of the relativeequipment.Resource( Equipment [ Operator ][ ,Material ]) defines the required resources for the activity execution.The item embraced by denotation”[ ]' is the optional. Equipment defines the information of the equipment implementing activity , Operator the information of the operator associating with the activity , Material the re-sources or parts listing in the BOM( bill of materials ) of the activity , while the consumable , such as water andelectricity , not involved.Time , Cost and Quality respectively define the delay of the activity , the used cost and the quality specifica-tion.The physical operation template integrates the process and the resource together , thus the resource alloca-tion and performance evaluation carry out based on the template.2.3 The Mapping Between the Task Template and the Physical Operation TemplateThere is a corresponding relation between the task template and the physical operation template , that is ,the operation sequences of the execution process E corresponds to the command Request of the outer activitytemplate , while Response of the outer activity template corresponds to the sensory process S of the task tem-plate. The mapping is given below.业: Request Set= f( E ),the execution process E of the task template maps to the instruction set.φ : S= g( Response/ Response set ) , the mapping from the feedback Response of the outer activity templateto the sensory process is defined.3 SPN Definition for Physical Operation Meta-modelThe definitions of stochastic Petri nets91 , in this paper中国煤化工ables to transitions andthe temporal variables being with exponential distribution.MHCNMHGThe meta -model of physical operation based on SPN is defined below. Ihe main states , the transitions be-tween the states and the interfaces of the object are to be described. In this paper ，the places represent thestates , the immediate transitions denote the logic condition verification , the timed transitions denote the physicaloperations , and the information places represent the interfaces of the objects. It is made out that the meta- model-436is operating in cyclic manner during the practical production. For the assembly shop floor , the physical opera-tions are the assembly procedure , the sub- assembly procedure，transporting , storing and testing according to theequipment categories.A transmission case assembly is exemplified to illustrate the proposed meta -model based on SPN.Taking .the workstation as the unit , the meta-model is constructed for the assembly line which consists of two kinds ofactivities : assembling and transporting. The meta-models of the assembly workstation and the AGV working onthe assembly line are ilustrated( see Fig.2 ).ToutaTinbPeT) Pw凸rt)0)PTinaTouthFig.2(a) Meta-rmodel for the assembly stationFig2b) Meta-model for the AGV( 1 ) Timed transitions : Ta represents the assembly operation ; T, represents the transport operation.( 2 ) Immediate transitions : I ina denotes the part arriving at the workstation ; Touta denotes the part leavingfrom the workstation. Timb represents the AGV entering assembly line with the part , Towtb represents the AGVdeparting from the assembly line to the warehouse with the finished goods.(3 ) Places : Pa represents the part assembling at the assembly workstation , Pe represents the ending of thepart assembling and leaving from the workstation , Pw represents the workstation free and waiting for the nextpart' s arrival. P: denotes the AGV transporting , P, denotes the AGV arriving at the destination , Pf denotesthe AGV vacant.( 4 ) Information places : Ia denotes assemnbly instruction ; Oa denotes the response of the assembly complet-ing. It , the transporting instruction ; O;，the response of the transporting ending.The AGV ,running at constant speed through assembly line from one station to another ,is in the transport-ing state until it leaves from the line , so the transportation operation is repeated between the stations.4 Production Process Control Model Based on SPA DefintionThe production process control plans some optimal schemes to control the order relation and the time con-straint of the production tasks and production operations , and which may be adjusted partially or improved en-tirely according to the actual resources states and the results of the performance evaluation. The production pro-cess control model corresponds to the schedule template for the management level defined in section 2.4.1 Stochastic Process Algebra( SPA )The main motivation behind the development of stochastic process algebra has been to accurately describeand investigate the behavior of resource - sharing systems and to benefit from their unique properties also in caseof performance modeling. Temporal information has been attached to activity governing its duration in the pro-cess descriptions in the form of exponential distribution. The concept of SPA follows the lines of classical processalgebras.The syntax for SPA terms is defined as fllowsDefinition4.1 P ::= Stop |(a ,y). P|P ;Q|P+Q|PllQ|P/QlrecX :P|XThe intuitive meaning of the operators is the following.Stop denotes the halting process. The prefixed process(a ,Y ). P behaves as P after the action a perform-ing with a certain delay Y. The choice operatorf" + ”allows one to model alternative behavior. The sequentialoperatof"” behaves as P , then Q. By means of the parallel operato"山li" two processes are modeled to pro-ceed independently , but they have to synchronize on actions中国煤化工Iled the cooperation setand defines the action types on which the components must synHCN M H Gnd Q proceed indepen-dently with any activities whose types do not occur in the cooperation set L. However , activities with actiontypes in the set L are assumed to require the simultaneous involvement of both components. The resulting activi-ty ( called a shared activity ) will have the same action type as the two contributing activities and a rate reflectingthe rate of the synchronization. Several possibilities exist for defining this resulting rate in terms of the rates of一431-the contributing activities. When the set L is empty " | L”has the effect of parallel composition , allowingcomponents to proceed concurrently without any interaction between them. In this case , the concise notation" P| |Q" is usually used. The hiding operatof /”provides an abstraction mechanism for actions that are internal ata certain level of specification. Infinite behavior is formally expressed by means of the recursion operatot" rec"This can be regarded as a compact notation for the recursive equation”X :=P" , where X reappears in P. Xcomponent is constant. P and Q are the component representing the process.4.2 Production Process Control Model Based on SPAThere are there functions correlative to the production process control in the model : sequencing determinesthe order of the production tasks entering the system , and which may be tuned in term of the actual state of thesystem ; routing decides the route for each part or each part lot according to the product techniques and the sys-tem status , and due to the relative fixed product techniques the routing for the assembly is relative simple ; re-sources allocation provides the required resources for the task.Definition 4.2( Prepare< m>|| Assign ); Action, , is the meta model for the production processcontrol activity , where Prepare< m > is the material preparing , Assign< < r> is the equipment assigning , Ac-tion, represents operation on the equipment r. Notation ”|I”is the parallel operator and' " is the sequential op-erator.The precondition processes Prepare and Assign -occur in the parallel way. Once the precondi-tion is true ,it then behaves like Action,. The model has the ability of resource allocation online.Definition4.3 Sch= T1* T2*...* T。 , where Sch represents the schedule, T1* T2* ...* T, is the se-quence of n production tasks , T;∈T( T is the set of production tasks ) , notation" * ”may be the sequential ,parallel , coordinate or choice operator , and which represents the sequential operator for the pipelined assembly.Schedule defines the partial order relation on a set of operations , which is the elementary task plan made interm of the sequencing rules.The routing defines the relation of the technique operations for a product lot. For the pipelined assembly ,there are parallel and concurrent relations between the assembly and the sub-assembly , while the procedure is se-quential on the assembly or sub- assembly , thereby the route of the assembly or sub assembly is a partial order re-lation. Only the assembly is considered below.Definition 4.4 T;=Oji* O2'”.Oi,T(i=12operations to fulfill the task T; ,O;=( o;' 2; ), o' denotes action type , the negative exponential distributionwith parameter Yj denotes action delay. Concretely ,0; =( Prepare ||Assign ) ;Action,. The nota-tion”￥ ”may be the sequential , parallel , coordinate and choice operator , and which represents the sequentialoperator for the pipelined assembly.There is an overlay relation among the tasks except the sequential or parallel relation in a dynamic schedul-ing model , for instance , when the first operation of the task completes ,the task b in the same buffer with taska no waiting for the completion of all operations of the task a，should enter into the assembly line. The tasksshould communicate each other , and then reschedule according to the environment states. The operator providedin process algebra can not satisfy adequately the dynamic rescheduling , so the new operator should be added andthe semantic of the operator should be enriched. The issue above will be discussed in another paper.Now the prefix operator is adopted , adding the waiting activity wA , then the production process controlmodel is redesigned for the pipelined assembly .Definition 4.5 The production process control model for the pipelined assembly APC= T'll T2'1l...1T。' , where TI' corresponds the first task defined in definition4.3 , T2' is expressed as w1'T2 , where w| de-notes waiting for the completionof T and T2 corresponds the second task defined in definition4.3 ,and w1lshould communicate witho1' of the task TI ,and then determines the waiting time. By the same pattern , T;' isdescribed as wi. w12... T; ,w1'. w12.. . denotes waiting for the first operations of the former( i - 1 ) tasks.Finally ,APC= Till( w'. T2llL( w1'. w12. T1+..l_. Tn )),where L( i=1 2.. m )is the co-operationset ,L1={o1' ,w1},L2={o12，w12 }r.. ,W1中国煤化I:nts the waiting for thecompletionof of and the firing rate of which is determined IMYHCNM H Ging asT".The production process control model based on SPA consists ot a set ot concurrent , communicating andcomputational processes , and the operators of PA fulfill the capabilities of sensing , reasoning and reaction. Con-sequently ,the process control model can accommodate to the uncertain and dynamic environment and make deci-sion online , which facilitates the reasoning about the behavior of the control model.-435 Model IntegrationHow to integrate the process control model based on SPA and the physical operation model based on SPN isthe key issue.Request Set= I( T;), T; in definition 4. 4 corresponds the instruction set ; the instruction set correspondsthe physical operations ,that is , SPN net = 0( Request Set ), function θ is the transition of semantics from SPAmodel to SPN modeF 10].Given that there are four workstations and three vehicles running at constant speed between the neighboringworkstations. There are two tasks with the same route going through all stations ,and the lot size of each task isone. The production process control model is followed :Schedule= Ti T2 ;Tk=O* O2* O35 O4k k={1 2};O;*=( Prepare< m>||Assign );Actionn; ;SPN net= 0( Request Set ), which denotes the SPN net made up of all SPN meta- models correspondingwith Actionri.Extending the SPN meta- model defined in section3 ,i=4 j=3 :( 1 ) Timed transitions : Ta' represents the assembly operation at station i ; T! represents the transport op-eration of the jth AGV.( 2 )Immediate transitions : Tina' denotes the part arriving at the workstationi ; Toua' denotes the part leav-ing from the workstation i. Tmb represents the jth AGV entering assembly line with the part , Toutb representsthe jth AGV departing from the assembly line to the warehouse with the finished goods.(3 ) Places : Pi represents the part assembling at the assembly workstation i , Pi represents the ending ofthe part assembling and leaving from the workstation i , P represents the workstation i free and waiting forthe next part' s arrival. Pi denotes the jth AGV transporting , P' denotes the jth AGV arriving at the destina-tion , P/ denotes the jth AGV vacant.. (4 ) Information places : Ia' denotes assembly instruction ; Oa denotes the response of the assembly com-pleting. I! , transporting instruction ; O? , the response of the transporting ending.The integrated SPN model acts as follow( see Fig.3 ):The assembly line consists of two parts : the assembly workstation meta- model and the AGV transportationmeta- model. The model is iluminated in term of the token flow : Tmi→Pi→Ti→Pi→Toua denotes the as-sembling process; Tmb'- >P/- ➢ TI-→P}- Tou' denotes the transporting process : The jth AGV at the free sta-tus( P} ), receiving the transporting instruction , then entering the line loading case( Tmb ), AGV at runningstate( P{ ), transporting( T{ ) ,arriving to the desired station( P}' ). then the case have arrived i th worksta-tion( Tind ), receiving the assembly command( Ia ) , at assembling state on the assembly workstatior( Pi' ),as-sembling( Ti )on station i ,the end of assembly( Pi ), the case leaving from station i ( Touta' ), sending outthe respons( Oa ) , workstation i free and waiting for the next case( Pw ). AGV continues running , arriving atthe next workstation，assembling , departing , transporting repeatedly until all procedures complete , and thenthe AGV leaving from the line to the warehouse( Toutb' ), making response , the AGV vacant( P} ).Meta-model for workstationMeta- -model for the AGVp:QOpTabC 01r.中r!Op')0,OP'P.' f中国煤化工TYTHCNMHGFig.3 SPN model for a transmisson case assembly一.433-6 ConclusionsOn a background of a class of discrete production process control , this paper introduces the hierarchical con-trol model , and since the temporal aspects can be captured in the representation scheme based on the integrationof SPA and SPN , the model permits performance evaluation. Moreover , the production process control modelmay make partial decision online due to the autonomy and cooperation capability of the task in the schedule.Based on the proposed control scheme , the management and control of a flexible assembly is realized. The modelcan be used for the mathematical analysis , simulation and real time control.Future work includes the synthesis from the respective performance of the physical operation meta - modelbased on SPN to the whole performance of the shop floor model. Furthermore , the operator provided in processalgebra can not satisfy adequately the dynamic rescheduling , so the new operator should be added and the seman-tic of the operator should be enriched. The issues above will be discussed in another paper.AcknowlegementThis work was supported by the National Natural Science Foundation of China under Grant 104 1007-1-04.References[1 ] Spathopoulos M P , RIDDER M. Modeling and Distributive Control Design of a Flexible Manufacturing Systen[ J] Computerin Industry ,1999 38 :115- 130.[2] CHEN Haoxu ,HU Baosheng. Schedule driven Supervisory Control of Flexible Manufacturing System:[ A] Proceedings of the30th IEEE Conference on Decision and Contro[ C ], England : Brighton , 1991 2186-2191.[3] LINJ T ,LEE CC. A Petri Net- based Integrated Control and Scheduling Scheme for Flexible Manufacturing CellJ] Com-puter Integrated Manufacturing Systems , 1997 ,10( 2 ):109-122.[4] THOMASJ P , NISSANKE N , BAKER K D. A Hierarchical Petri Net Framework for Representation and Analysis of Asem-bly{ A] IEEE Transactions on Robotics and Automatior[ C], 1996268-279.[5] REN Yanpin ,ZHANG Zuo , WU Qiufeng. Modeling and Simulation of Switching Rule based Scheduling Systen[ J ] SystemEngineering Theory and Practice ,1999 ,7 16- 11.( in Chinese )[6] HATONO I , YAMAGATA K , TAMURA H. Modeling and Online Scheduling of Flexible Manufacturing Systems usingStochastic Petri Net:[ A] IEEE Transactions on Software Engineering[ C], 1991 ,126- 132.[ 7] Choi J Y , Reveliotis S A. A Generalized Stochastic Petri Net Model for Performance Analysis and Control of Capacitated Reen-trant Line[ A] IEEE Transactions on Robotics and Automatior[ C], 2003 19 3 )474 480.[8] Falkman F ,Lenartson B ,TTTTUS M. Modeling and Specification of Discrete event Systens using Combined Process Algebraand Petri Nets[ A] IEEE/ASME Intermational Conference on Advanced Ielligent Mechatronic[C],2001 2 :1 011-1 016.[9] LIN Chuang. Stochastic Petri Net and System Performance Evaluation( Second Edition I M] Beijing : Tsinghua UniversityPublishing Company , 2005 A( in Chinese ).[ 10 ] Marina Ribaudo. Stochastic Petri Nets Semantics for Stochastic Process Algebras. In Proc. of 16th Int. Workshop on PetriNets and Performance Models ,Durham NC ,1995.中国煤化工MHCNMHG- 43万左数据