## 这是一篇来自德国的关于离散事件系统的一个分级作业代写

**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 ISIS webpage, as a single
**PDF file**, before the end of the deadline date (**03.03.2023**). 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 instal 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/

**System Description **

Consider a manufacturing system consisting of three machines of unitary capacity, *M*1, *M*2, and *M*3, and a deposit of infinite capacity where both raw and finished products are kept. Three types of products are processed in the plant, according to different processing steps:

- products of type A are first processed in
*M*1 and then in*M*2, - products of type B are first processed in
*M*1 and then in*M*3, and - products of type C are first processed in
*M*2 and then in*M*1.

The production sequence is summarized in Figure 1, and processing times are reported in Table 1. Deposit and machines are placed such that they form the vertices of a rhombus (or diamond, as in Figure 1), where each side has a length of 10 m and the longer diagonal, which connects the deposit and machine *M*2, has a length of 16 m.

Products are transported from the deposit to the appropriate sequence of machines and then back to the deposit by means of autonomous guided vehicles (AGVs), each of which has a maximal speed of 1 m s*−*1 and unitary capacity. There are in total six AGVs in the system, two for each product type, and they are denoted by AGVX*i *,where X *∈ {*A*,*B*,*C*} *and *i **∈ {*1*,*2*} *indicate, respectively, the type of products that the AGV transports and the vehicle number. For all *i **∈ {*1*,*2*}*, vehicle AGVX *i *can only transport pieces of type X *∈ {*A*,*B*,*C*}*, and, while a product is being processed in a machine, the AGV that transported it there waits for the process to finish before transporting the product to the next machine or to the deposit. Assume that no collision among AGVs can occur,that AGVs always move in straight lines towards their destination at maximum speed, and that the time to load or unload a product onto or from an AGV is negligible.

Initially (i.e., at time 0 s),

- AGVA

1 , AGVB 1 , and AGVC

1 are waiting for raw products of the respective types to arrive at the deposit,

- AGVA

2 has been transporting a product from machine *M*2 to the deposit for 1 s (i.e., it will reach the deposit at time 15 s),

- a product of type B has just been loaded onto AGVB 2 from machine
*M*1, - AGVC 2 has been transporting a product from the deposit to machine
*M*2 for 14 s.

**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.

b) (2 points) For safety reasons, at any time, at most one AGV should be transporting a product of type B from machine *M*1 to machine *M*3. Suppose that the only controllable (i.e., preventible) and observable events in the system are the loading of products from the deposit onto AGVs and the start of processes in machines.

Find an implementable controller that enforces the safety measure.

**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 *M**i *, *i **∈ {*1*,*2*,*3*}*, is an infinite sequence *w**M**i *of types of products that are processed consecutively in *M**i *. For instance, a possible schedule for machine *M*2 is *w**M*2 = (AC) *ω *= ACACAC *. . . *, 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 product types to be processed; the meaning is that machine *M*2 is forced to first process a product of type A, then one of type C, then again one of type A, and so on. In other words, after processing a product of type A, another product of type A can be processed only after one of type C.

Observe that, once we fix a schedule *w**M**i *for each machine *M**i **∈ {**M*1*,M*2*,M*3*} *(i.e., a triplet of schedules of the form (*w**M*1 *,w**M*2 *,w**M*3 )), 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) = *A*0*x*(*k *+ 1) *⊕ **A*1*x*(*k*) *⊕ **B*0*u*(*k *+ 1)

for all *k **≥ *1*, y*(*k*) = *C*0*x*(*k*)

*x*(1) = *A*0*x*(1) *⊕ *∆(*e . . . e*) *′ **⊕ **B*0*u*(1) *,*

where *u*(*k*) = (*u*A(*k*) *u*B(*k*) *u*C(*k*))*′ *and *y*(*k*) = (*y*A(*k*) *y*B(*k*) *y*C(*k*))*′ *represent, respectively, the times at which the *k*-th raw and finished products of each type enter the deposit. 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

*θ *=1/*λ **,*

where *λ *is the maximal mean weight of all circuits in *G*(*A**∗ *0*A*1).

Suppose that you are required to analyze the following three triplets of schedules:

a) (3 points) Draw the timed event graphs corresponding to triplets Ψ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 ?

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 arrival of the first raw products of each type in the deposit, such that the second finished product of type C is unloaded into the deposit at time 60 s, and supposing that the second, third, *. . . *raw products of each type arrive periodically at the deposit with period *λ *= 1/*θ *.