代写program、代做Java/Python程序设计

日期：2024-02-15 11:09

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 λ =

1

θ

.

4