Exercises on timed automata
Exercise 1
The production system in the figure is composed of two machines M1 and M2 connected in series, both without waiting space. If a part arrives and M1 is busy, the part is rejected. If M1 terminates a job and M2 is busy, M1 keeps the part until M2 terminates its job as well. It is assumed that the arrivals of parts are deterministic, with constant interarrival times ta= 1.0 min.
M1 M2
i) Describe the production system through a state automaton (E, X , Γ, f, x0), assuming that both machines are initially idle.
ii) A total of 6 parts arrive at the production system. Determine the sample path of the pro- duction system corresponding to the following clock sequences (expressed in minutes) for the jobs in M1 and M2, respectively: Vd1 = {0.8, 0.7, 0.8, 1.2}, Vd2 = {1.5, 0.9, 1.0, 1.3}. How long does it take to process all the parts admitted into the production system? What is the average time spent by a generic part in the system?
Exercise 2
The production station in the figure is composed of a one-place buffer B, and a machine M . An arriving raw part is accepted in the production station if the buffer is empty, otherwise it is rejected.
B
l M
A mobile robot is used to move parts from B to M along the path l. The logic of the robot is as follows:
i) If the robot arrives at the buffer, and the buffer is full, the robot loads immediately the raw part from the buffer, and carries it to the machine. Otherwise, it waits for the arrival of a raw part. When the part arrives, the robot loads it immediately, and carries it to the machine.
ii) If the robot arrives at the machine, and the machine is idle, the robot unloads immediately the part into the machine, and returns to the buffer. Otherwise, it waits for the termination of the job in the machine. Then, the robot unloads immediately the part into the machine, and returns to the buffer.
Jobs in the machine have deterministic durations equal to 5 min. The mobile robot moves with constant speed v1= 0.2 m/s when it goes from the buffer to the machine, and v2 = 0.4 m/s when it goes from the machine to the buffer. The length of path l is 24 m.
1. Model the production station through a state automaton with outputs (E, X , Γ, f, x0,Y, g), choosing the total number of parts in the production station as the output.
2. Assuming that arrivals of raw parts occur at times 2.0, 4.5 and 13.0 min, determine the sample path of the total number of parts in the production station in the interval [0, 15] min.
Consider loading and unloading times to be negligible.
3. Compute the average number of parts in the production station during the interval considered in point 2.
Exercise 3
Suggestion: In this exercise you have to understand priorities between the events (needed to deal with cases when the smallest residual lifetime corresponds to two or more events) from the problem description.
A wireless sensor is powered by a battery of capacity 5 Ah. The sensor can be asked either to acquire a new measurement or to acquire a new measurement and transmit the measurement record via wireless to a data collector. In case of acquisition only, the battery discharge amounts to 1 Ah, whereas in case of both acquisition and transmission, it amounts to 2 Ah1. It is assumed that a request is accepted even if the remaining battery capacity is not sufficient to satisfy the request. The durations of both acquisition and transmission are assumed to be negligible. When the battery is too low, it is put on charge. During the charge, the wireless sensor is deactivated (meaning that all requests are rejected). The requests of acquisition arrive every 10 minutes, the requests of both acquisition and transmission arrive every 25 minutes, and the battery charge takes 18 minutes. The battery is initially full.
1. Compute the discharge time of the battery in steady state.
2. Compute the fractions of the two types of requests that are accepted in steady state.
Exercise 4
A machine can be in one of three states (idle, busy, and down). The machine breaks down after 10 hours of operation (i.e., in state busy). When the machine breaks down, the ongoing job is lost.
Repairing the machine takes 2 hours. After the repair, the machine is idle, waiting for a new job.
1. Model the machine through a a state automaton (E, X , Γ, f, x0), assuming that the machine is initially idle.
2. Assuming that: the machine spends in state idle 3.0, 0.6, 1.0, 0.8, and 1.2 hours; the first five jobs require 1.8, 2.4, 2.2, 2.6, and 2.5 hours to be completed, determine how many jobs are completed before the machine breaks down for the first time.
1These values are not realistic.
1
2
3
4
