Fachgebiet Regelungssysteme
Fakultat IV Elektrotechnik und Informatik ¨
Technische Universitat Berlin ¨
Course “Discrete Event Systems”
CSG Fachgebiet
Regelungssysteme
Control
Systems
Graded homework in course “Discrete Event Systems”
Hand-out date: 19.01.2024
Hand-in deadline: 01.03.2024
Instructions
• The students can choose to perform the solution of this homework either individually or in groups of 2 or 3.
Groups consisting of more than 3 students will not be accepted.
• The solution of the homework must be submitted through the indicated assignment on the course’s ISISwebpage, as a single PDF file, before the end of the deadline date (01.03.2024). For those who choose to
complete the homework in groups, only one member of the group needs to submit the solution. The PDF file
must contain the name and Matrikelnummer of (all) the respective student(s). It must be clearly indicated
which part of the document corresponds to the answer to each task.
• The solutions must be presented in English.
• Maximum score: 20 points
• Correction criteria: The completeness and correctness of the solution corresponds to 15 points. The remaining 5 points concern the presentation of the solution, based on criteria such as clarity of exposition,
succinctness, and organization.
• The use of Python, together with the PetriTUB toolbox, is suggested in order to perform the necessary computations. Any other computational tool of choice can also be utilized. All capabilities of the chosen tool can be
freely employed to solve the homework; it should then be indicated in the solution which macros/procedures
from the tool are utilized at each step.
• The PetriTUB toolbox can be used, with no installations required, from the following link: https://
morbo.control.tu-berlin.de/hub/user-redirect/git-pull?repo=https%3A%2F%
2Fgit.tu-berlin.de%2Fcontrol%2Fteaching%2Fdes%2Fdes-notebooks&urlpath=
tree%2Fdes-notebooks%2FScript+for+graded+homework.ipynb&branch=main.
• Alternatively, it can be downloaded for free from the following link: https://git.tu-berlin.de/
control/discrete-event-systems/petritub. To install the toolbox, follow Section Getting
started → Installing the toolbox of the documentation.
• The documentation of the toolbox can be found here: https://control.gitlab-pages.
tu-berlin.de/discrete-event-systems/petritub/
1
System Description1
A manufacturing system consists of six devices: two mills (M1 and M2), a lathe (L), a robot (R), a buffer, and an
assembly machine (AM). It produces two types of products from raw blocks and pegs: blocks with a conical pin on
top (product of type A) and blocks with a cylindrical pin on top (product of type B). In the following, raw blocks
and pegs designated to become products of type A and B will be simply called blocks and pegs of type A and B,
respectively. Each block is first processed in one of the two mills; after milling, the robot puts the completed block
into the buffer waiting for assembly. Pegs are initially delivered to the lathe, which cuts them to become either
a conical or a cylindrical pin (depending on the peg type), and are then placed into the buffer by the robot. The
assembly machine takes from the buffer a block (of type A) and a conical pin to manufacture a product of type A,
and it takes a block (of type B) and a cylindrical pin to manufacture a product of type B. Each machine in the plant
can perform one operation at a time, and no buffer is present between the mills and the robot and between the lathe
and the robot. This means that, before a mill/lathe can start working on a new raw part, it must wait for the robot to
pick up the last processed part. The buffer between the robot and the assembly machine is assumed to have capacity
for infinitely many blocks and pins. Figure 1 schematically represents the manufacturing system.
Block A
Block B
Peg A
Peg B
Mill 1
Mill 2
Lathe
Robot
Buffer Assembly
machine
Product A
Product B
Figure 1: Production sequence for products of type A (in blue, continuous arcs) and B (in red, dashed arcs).
mX lX r
b
X
r
p
X
aX
A 10 5 4 3 6
B 10 3 4 3 11
Table 1: Time (in seconds) to execute tasks mX, lX, r
b
X
, r
p
X
, and aX for all X ∈ {A,B}.
We use the following notation: for all X ∈ {A,B}, task mX indicates the milling of a block of type X, task lX
denotes the processing of a peg of type X in the lathe, task r
b
X
indicates the transportation of a block of type X from
one of the mills into the buffer, task r
p
X
denotes the transportation of a pin of type X from the lathe into the buffer,
and task aX refers to the assembly of a block with a pin of type X. Table 1 reports the time to execute each one of
these tasks.
Initially (i.e., at time 0 s), the mill M1 has been processing a block of type B for 5 s. Therefore, according to Table 1,
the block is going to be completed at time 5 s. All the other machines as well as the buffer are empty at time 0 s.
1This example was inspired from the flexible manufacturing system described by de Queiroz, Cury, and Wonham in ”Multitasking supervisory control of discrete-event systems” (2005), published in Discrete Event Dynamic Systems.
2
Tasks
Task 1 (6 points)
a) (4 points) Draw a timed Petri net with holding times representing the manufacturing system. Indicate the
time tags of all initial tokens, and briefly describe the meaning of the firing of each transition in the Petri net.
Hint: it is possible to represent the beginning of the milling process (in any of the two mills) for a block of
type X ∈ {A,B} using only one transition. Similar reasoning applies to the end of the milling process.
b) (2 points) The robot is programmed to work at the maximum speed; therefore, a controller cannot prevent it
from picking up a processed block/pin from a mill/lathe and depositing it into the buffer. On the other hand,
all the other events in the system are controllable and observable.
Suppose that, at any time, at most one block of type B should be in the buffer. Find an implementable and
minimally restrictive controller that enforces this specification.
Task 2 (9 points)
In the remainder of the homework, assume (if you solved Task 1 b)) that the controller from Task 1 is active. A
schedule for a certain machine Y ∈ {M1, M2, L, R, AM} of the manufacturing system is an infinite sequence wY
of tasks that are executed consecutively by the machine Y. For instance, a possible schedule for the mill M1 is
wM1 = (mBmA)
ω = mBmAmBmAmBmA . . . , where v
ω
indicates the schedule obtained by concatenating string
v with itself an infinite number of times, and a string is a finite sequence of tasks; the meaning is that machine M1
is forced to first process a block of type B (starting from the one that is already being processed at time 0 s), then
one of type A, then again one of type B, and so on. In other words, after processing a block of type B, another
block of type B can be processed in M1 only after one of type A.
Observe that, once we fix a schedule wY for each machine Y ∈ {M1, M2, L, R, AM} (i.e., a 5-tuple of schedules
of the form (wM1,wM2,wL,wR,wAM)), the system can be conveniently modeled by a timed event graph whose
transitions’ earliest firing times are determined by equations of the following form:
for all k ≥ 1, x(k + 1) = A0x(k + 1) ⊕ A1x(k) ⊕ B0u(k + 1)
for all k ≥ 1, y(k) = C0x(k)
x(1) = A0x(1) ⊕ ∆(e . . . e)
represents the times at which the k-th blocks and pegs of each type
enter a mill/lathe, and y(k) = (yA(k) yB(k))′
represents the times at which the k-th finished products of each type
exit the assembly machine.
For a system evolving according to (1), the maximum throughput (i.e., the maximum processing rate) θ, corresponding to the highest firing rate (number of firings per time unit) that can be achieved by the “slowest” transition
in the timed event graph, can be computed by
where λ is the maximal mean weight of all circuits in the precedence graph G(A∗
0A1).
Suppose that you are required to analyze the following three 5-tuples of schedules:
a) (3 points) Draw the timed event graphs corresponding to 5-tuples Ψ1
, Ψ2
, Ψ3
.
b) (1 points) Analyze the liveness of each transition of the timed event graph corresponding to Ψ1
. On the
basis of this analysis, what is the maximum throughput θ1 of the manufacturing system when following the
schedules specified by Ψ1
?
3
c) (2 points) Using (2), compute the maximum throughputs θ2 and θ3 in the case the machines follow schedules
specified by Ψ2
and Ψ3
.
d) (3 points) Consider the triplet of schedules among Ψ1
, Ψ2
, Ψ3
that corresponds to the largest maximum
throughput θ. Determine the largest (i.e., latest) possible times for the entrance of the first raw blocks and pegs
of each type in the mills/lathe, such that the second finished product of type B exits the assembly machine
at time 60 s, and supposing that the second, third, . . . raw blocks/pegs of each type enter periodically the
mills/lathe with period λ =