Exam of Discrete Event Systems - 04.02.2016

(1)

Exam of Discrete Event Systems - 04.02.2016

Exercise 1

A molecule can switch among three equilibrium states, denoted by A, B and C. Feasible state transitions are from A to B, from C to A, and from B to both other states. The initial state is A.

1. Assume that state holding times in B are all equal to t

B

> 0, and transitions from B to A and from B to C alternate (the first time from B to A, the second time from B to C, the third time from B to A, and so on). Moreover, assume that state holding times in A take values 8.0, 3.0, 5.0, 12.0, 8.0, 6.0, 5.0, 8.0, 4.0 and 9.0 ms, and state holding times in C take values 10.0, 6.0, 9.0, 6.0 and 8.0 ms. Determine t

_B

so that the fraction of time spent by the molecule in B over a time horizon of length T = 100 ms is 40%.

Now assume that, whenever the molecule leaves B, transition to A occurs with probability q = 1/3.

Moreover, state holding times in A follow a uniform distribution over the interval [6, 12] ms, state holding times in B are all equal to 8 ms, and state holding times in C follow a uniform distribution over the interval [5, 10] ms.

2. Model the dynamics of the molecule through a stochastic timed automaton (E, X , Γ, p, x

0

, F ).

3. Compute the probability that, after the sixth event, the molecule is in A.

4. Assume that the molecule enters B from A. Compute the probability that the molecule returns to A within T = 15 ms.

5. Compute the probability that the molecule is in A at time t = 18 ms.

Exercise 2

A manufacturing cell is composed by two machines M

¹

and M

²

, as shown in the figure.

M

1

M

2

Arrivals of raw parts are generated by a Poisson process with rate 8 arrivals/hour. Raw parts arriving when M

1

is busy, are rejected. Raw parts are processed in M

1

. When M

1

terminates a job:

• if M

2

is available, the finished product leaves the system with probability q = 9/10, otherwise it is sent to M

2

for inspection;

• if M

2

is busy, the finished product leaves the system.

After inspection in M

2

, inspected products turn out to be non-defective with probability p = 15/16, and leave the system. Defective products are sent again to M

1

for rectification. If M

1

is busy, the defective product is kept by M

2

until M

1

terminates the ongoing job. Processing of a part in M

1

takes a random time following an exponential distribution with expected value 5 minutes.

Inspections in M

²

have random durations following an exponential distribution with expected value

3 minutes. The manufacturing cell is initially empty.

(2)

1. Model the manufacturing cell through a stochastic timed automaton (E, X , Γ, p, x

⁰

, F ).

2. Assume that M

1

is processing a part and M

2

is inspecting a product. Compute the probability that the manufacturing cell is emptied while avoiding a situation where M

1

is idle and M

2

is inspecting a product.

Only first part

3. Compute the average state holding time when M

1

is processing a part and M

2

is inspecting a product.

4. Assume that M

1

is idle and M

2

is inspecting a product. Compute the probability that the inspection terminates successfully within T = 5 minutes, and exactly one arrival of a raw part occurs.

Exercise 3

Consider the system of Exercise 2.

1. Verify the condition λ

_{ef f}

= µ

_{ef f}

for the system at steady-state.

2. Compute the utilization of M

1

and M

2

at steady state.

3. Compute the average time spent by a generic product in M

²

upon a single inspection at steady state.

Exercise 4

A small shop keeps a stock of a maximum of three smartphones. The daily demand D of smart- phones follows a Poisson distribution

P (D = n) = λ

ⁿ

n! e

^−λ

, n = 0, 1, 2, 3, . . .

where λ = 0.5. Demand exceeding the availability is not satisfied. Every morning, at opening, the shop manager checks the availability of smartphones, and orders three of them if and only if the stock is empty. Delivery of the new smartphones occurs the morning after with probability p = 0.7, and the second day otherwise.

1. Model the stock size at shop opening through a discrete-time homogeneous Markov chain.

Assume the stock initially full.

2. Assume that the stock is full. Compute the probability that no order of smartphones is carried out during the next five days.

3. Assume that the stock is full. Determine how often, on average, the shop manager carries

out an order of smartphones.

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)