Exercises on stochastic timed automata with Poisson clock structure

(1)

Exercises on stochastic timed automata with Poisson clock structure

Exercise 1

Consider the queueing system depicted in the figure.

M

1

M

2

Arriving parts may need preprocessing in M

1

with probability p = 1/3, otherwise they go directly to M

2

. When a part arrives and the corresponding server is not available, the part is rejected.

Between M

1

and M

2

there is a buffer with only one place. When M

1

terminates preprocessing of a part and M

2

is busy, the part is moved to the buffer, if it is empty. Otherwise, the part is kept in M

1

, that therefore remains unavailable for a new job until M

2

terminates its job. Parts arrive according to a Poisson process with expected interarrival time equal to 5 min, whereas service times in M

1

and M

2

follow exponential distributions with rates µ

1

= 0.5 services/min and µ

2

= 0.8 services/min, respectively.

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

0

, F ), assuming the system initially empty.

2. Assume that M

¹

is idle, the buffer is full, and M

²

is busy. Compute the probability that the two parts in the system exit the system before the acceptance of other parts.

3. Assume that M

1

is busy, the buffer is empty and M

2

is idle. Compute the expected time to the start of a job in M

²

.

4. Compute the probability that the first arriving part needs preprocessing in M

1

and no arriving parts go directly to M

2

while the first is being preprocessed.

Exercise 2

A simple manufacturing system is composed of a buffer with unitary storage capacity and a machine.

Parts processed in the machine turn out to be defective with probability p =

¹8

. Any defective part after the first processing, is immediately reprocessed. If a part is still defective after the second processing, it is rejected. Parts are delivered one at a time to the manufacturing system by a mobile robot equipped with a mechanical arm. Executing this task takes a random duration following an exponential distribution with expected value

¹_λ

= 4 minutes. Arrival of new parts is suspended while the manufacturing system is full. Processing of a part has a random duration following an exponential distribution with expected value

¹_µ

= 2 minutes.

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

0

, F ), assuming that the system is initially empty.

2. Assume that only one part is in the system, and this part is being processed for the first time.

Compute the probability that the part is rejected before the arrival of a new part.

3. Compute the probability distribution function of the total time Z which a generic part spends

in the machine (i.e. including the possible reprocessing).

(2)

Exercise 3

A small bank office has only one desk and a waiting room with 5 chairs. The desk opens at 9 AM, but customers may enter the waiting room starting from 8:30 AM. Customers arrive as generated by a Poisson process with average rate λ = 4 arrivals/hour, whereas the service time at the desk follows an exponential distribution with expected value 20 minutes.

1. Model the bank office starting from the opening of the desk through a stochastic timed automaton (E, X , Γ, f, p

0

, F ).

2. Compute the probability that the second customer arriving after the opening of the desk finds at least one available place in the waiting room.

Exercise 4

A manufacturing cell is composed of two one-place buffers B

1

and B

2

and one assembling machi- ne M , as shown in the figure.

M B

₁

B

₂

Arrivals of raw parts are generated by a Poisson process with rate 10 arrivals/hour. Arriving parts are of type 1 with probability p = 1/2 and of type 2 otherwise. Type 1 parts are stored in buffer B

¹

, whereas type 2 parts are stored in buffer B

²

. An arriving part is rejected if the corresponding buffer is full. Machine M assembles one type 1 part and one type 2 part to make a finished product.

Assembling starts instantaneously as soon as parts of both types are available in the buffers and M is ready. Assembling times have an exponential distribution with expected value 5 minutes. The manufacturing cell is initially empty.

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

0

, F ).

2. Assume that M is working and both buffers are full. Compute the probability that the manufacturing cell is empty

(a) when a new part arrives;

(b) when a new part is accepted.

3. Compute the average state holding time when B

1

is full, B

2

is empty and M is working.

4. Assume that M is working and both buffers are full. Compute the probability that two

products are finished within T = 10 minutes, and no arrival of type 1 parts occurs.

(3)

Exercise 5

A minibus has a maximum capacity of 9 passengers. A bus stop has a waiting room with a maximum capacity of 4 seats. Passengers arriving at the waiting room and finding it full, are routed to another line. When the minibus arrives at the bus stop, the number of passengers in the minibus is a random variable following a discrete uniform distribution over {0, 1, . . . , 9}. None of the passengers gets off the minibus at the bus stop. Waiting passengers are admitted on the minibus so as to not exceed its maximum capacity. Non-admitted passengers keep waiting for the next minibus. Assume that the duration of a stop is negligible.

1. Model the system above through a state automaton (E, X , Γ, p, x

0

), assuming that the waiting room is initially empty.

Assume that the minibus arrives at the bus stop every T = 15 min, and arrivals of passengers at the waiting room are generated by a Poisson process with average interarrival time of 5 min.

2. Compute the average number of passengers arriving at the waiting room between a transit of the minibus and the next.

3. Compute the probability that the waiting room is empty after the first transit of the minibus.

4. Compute the probability that, the first time the minibus arrives, exactly one waiting passenger gets on the minibus.

Then, assume that arrivals of the minibus at the bus stop are now generated by a Poisson process with rate 4 arrivals/hour.

5. Assuming that two passengers are sitting in the waiting room, compute the probability that the waiting room is empty when the next passenger arrives.

6. Compute the probability that there are at least three arrivals of any type (both passengers

and minibus) in one hour.

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)