MTAT.03.083 – Systems Modelling

Petrinetshomework

  • You may complete the homework individually or pairs.
  • Submit your homework as a zip file using the Submit button in the course Web page. The zip file should contain a Woped (.pnml) file with the solution to part A and a Word, OpenOffice or PDF file with the answers to part B.

Part A. Automated Factory Line (4 points)

We consider a segment of a factory with two conveyor belts, two machines, one robot and one buffer. Raw parts arrive through a first conveyor belt, called the raw line. The robot moves each part from the raw lineinto machine M1. Machine M1 immediately starts processing the raw part. Eventually, the machine will finish processing the part and the robot may then move the processed part into the buffer. Eventually, the robot moves the part from the buffer into machine M2. Machine M2 will start processing it. When machine M2 finishes processing the part, the robot will then move that part from machine M2 into a second conveyor belt (called the finished line).

Figure 1 illustrates the factory line in the state where the raw line holds 2 parts, M1 and M2 hold one part each, the buffer holds two parts, and the finished line holds one part.

Figure 1: Factory Line Structure

M1 can hold at most one part at a time, and the same applies for M2. The robot can only move one part a time. Whenmachine 2 isfree, the robot canmove a part directlyfrommachine 1 intomachine 2 instead of movingthe part tothebuffer.

The conveyor belts can hold any number of parts but the buffer can hold at most7 parts. Whenthebufferisfull, the robot willnotput a part intomachine 1, evenifmachine 1 isempty. Thisconstraintisintendedtoavoidthesituationwheremachine M1 finishesprocessing a part and the robot isnotableto take awaytheprocessed part from M1.

This segment of factoryline (in its “empty” state) ismodelledas a Petri net in Figure 2.

Figure 2: Petri net of the system in its initial (empty) state.

Extend and modify the above Petri net as needed in order to capture the following requirements.

  1. In the above Petri net, we do not distinguish between the state where a part is being processed by a machine, and the state where a part is still inside a machine but has already been processed. Naturally, the robot should only remove a part from a machine if it has already been processed, and not while the part is being processed.
  2. Both machines M1 and M2 are replaced with larger machines (called M1L and M2L). Each of the new machines can process two items concurrently (but it can also process one item at a time). It is possible to add a second part to a machine while it is processing another part. The robot still has capacity for transporting only one part at a time.
  3. From times to times, it happens that a machine breaks down. In this case the machine moves into a “broken” state. If the machine breaks down while it is processing one or two parts, the robot discards these unprocessed parts into a recycle bin. If a machine breaks while it is holding already processed parts, the processed parts are moved forward in the production line. The robot will never move any part into a broken machine. Once the broken machine is completely empty, an operator eventually repairs it and restarts it. While one of the machines is broken, the other one may continue to work.

You should submit a Petri net incorporating all three requirements. Requirements #1 and #2 are worth one point each, while requirement #3is worth two points. The solution will be assessed both in terms of correctness and simplicity.

Part B. Properties of Petri nets and BPMN models (2 points)

As seen in the lecture, a BPMN process model with one start event and one end event can be translated into a Petri net with one single source place (i.e. a place with no incoming arc, hereby called S) and one single sink place (i.e. a place with no ongoing arc, hereby called E). The initial marking of this Petri net is the one that contains a token in S and no other token elsewhere.

A BPMN process model has a deadlock if in the corresponding Petri net, there exists a firing sequence starting from the initial marking and leading to a marking M, such that from marking M there is no firing sequence leading to a place where there is a token in place E. In other words, the execution of the process is blocked before the end event is reached.

A BPMN model is safe if there does not exist any firing sequence starting from the initial marking and leading to a marking M in which there is more than one token in the same place.

A cycle in a BPMN process model is a sequence of arcs[1] such that the target of the last arc is the source of the first arc, and the target of every other arc is equal to the source of the next arc in the sequence.A BPMN process model is cyclic if it contains at least one cycle, otherwise it is acyclic.

  • Draw an acyclic BPMN process model that has a deadlock and is not safe.
  • Draw a cyclic BPMN process model that has a deadlock, and such that if we remove the arc in the BPMN model that causes the cycle (i.e. we made the model acyclic by removing one arc), the resulting BPMN model does not have a deadlock.

[1]An arc is called a sequence flow in the BPMN terminology.